圖論簡明索引
0. 前言
圖論作為計算機專業離散數學系列課程的重要一環，在本科時我就上過一學期的課程。研究生剛好碰到機會重新速覽了一遍圖論，在此做一個筆記，叫做簡明索引。簡明是因為內容淺嘗輒止，只涉及到最基本的概念和最常見的問題，我認為可以看作是算法和數據結構知識的理論導引；索引是因為這裡只是概念、問題和解決方案的羅列，省去了嚴格的證明，甚至對於（我認為）常見的、著名的算法，也略去不表。
我以這樣的方式來組織這個索引：概念定義(Concept Definition)和問題(Problem)。這也和圖論的歷史發展和課程組織有關，它們往往是問題驅動的，從一個非常實際的問題出發，抽象出概念，然後從數學上解決，最終又應用於實際。這也是為什麼圖在算法和數據結構裏面佔據非常重要的地位，因為其對客觀事物的抽象涵蓋得太廣，應用得太廣。
1.概念
1.1 圖的基本概念
圖將客觀事物抽象成節點，將事物間的關係抽象成邊。
Definition 1.1.1 (圖) 圖 \(G\) 由非空結點集合 \(V=\{v_1,v_2,…,v_n\}\) 和邊集合 \(E=\{e_1,e_2,…,e_m\}\) 組成，其中每條邊可用一個結點對表示，即 \(e_i=(v_{i1},v_{i2}),i=1,2,…,m\) . 這樣的一個圖 \(G\) 可表示為 \(G=<V,E>\) .
由這個定義我們引出一系列術語：
- 有向邊和無向邊：若表示邊的節點對是有序對，則稱該邊是有向邊；若是無序對，則稱該邊是無向邊。
- 有向圖和無向圖：若圖的所有邊都是有向邊，則稱該圖為有向圖；若所有邊都是無向邊，則稱該圖為無向圖。
- 關聯：稱邊與表示其的節點對中的每個節點相關聯。
- 鄰接：稱關聯於同一條邊的兩個節點相鄰接；稱關聯於同一個節點的兩條邊相鄰接。
- 環：稱兩端關聯於同一節點的邊為環。
- 孤立點：稱不與任何節點鄰接的節點為孤立點。
Definition 1.1.2 (子圖) 兩個圖 \(G=<V,E>,G’=<V’,E’>\) 如果滿足 \(V’\subseteq V, E’\subseteq E\) , 則稱 \(G’\) 是 \(G\) 的子圖。如果 \(V’\subset V, E’\subset E\) ，則稱 \(G’\) 是 \(G\) 的真子圖。如果 \(V’=V, E’\subseteq E\) ，則稱 \(G’\) 是 \(G\) 的生成子圖。
Definition 1.1.3 (圖的同構) 兩個圖 \(G=<V,E>,G’=<V’,E’>\) ，如果他們的節點間存在一一映射，且該映射也反映在表示邊的節點對中，則稱兩圖是同構的。
Definition 1.1.4 (節點的度) 在有向圖中，以節點 \(v\) 為起點的邊的條數稱為 \(v\) 的出度；以 \(v\) 為終點的邊的條數稱為 \(v\) 的入度；入度與出度之和稱為度。在無向圖中，與 \(v\) 關聯的邊的條數稱為度。
1.2 圖的分類
除1.1中按邊的類型可將圖分為有向圖和無向圖外，我們還可以按照其他標準對圖進行分類：
- 多重圖和簡單圖：如果一個節點對對應多條邊，則稱這些邊為多重邊。包含多重邊的圖稱為多重圖；不包含多重邊的圖稱為簡單圖。
- 有權圖和無權圖：如果圖中的邊附有權值，則稱該圖為有權圖；否則稱為無權圖。
1.3 通路與迴路
路是一組比較容易混淆的概念，是否允許重複邊，是否允許重複節點，需要辨析清楚，因為有一系列的問題其實就是在探討符合某種特殊要求的路是否存在，如果存在怎麼求。
Definition 1.3.1 (通路) 在圖 \(G=<V,E>\) 種，邊序列 \((v_0,v_1),(v_1,v_2),(v_2,v_3),…,(v_{k-1},v_k)\) 稱作一條通路，簡記作 \((v_0,v_1,…,v_k)\) 。
對應地，針對上述定義也延伸出一系列術語：
- 起點和終點： \(v_0\) 稱作通路的起點， \(v_k\) 稱作通路的終點。
- 長度：通路中邊的數目稱為通路的長度。
對於普通的通路而言，我們對其中的邊和點的重複性沒有任何限制。為引出這些限制，我們特別定義：
- 簡單通路：沒有重複邊的通路稱為簡單通路。
- 基本通路：沒有重複節點的通路稱為基本通路。
基本通路一定是簡單通路，反之不成立。
Definition 1.3.2 (迴路) 起點和終點相同的通路稱為迴路。
同樣，普通的迴路對邊和點沒有重複性的要求，我們特別定義：
- 簡單迴路：沒有重複邊的迴路稱為簡單迴路。
- 基本迴路：除起點和終點外沒有重複點的迴路稱為基本迴路。
特別地，我們除了一些重複性要求外，還關注着路對於圖的遍歷性質，比如走遍圖的每個點或每條邊。尋找這些有趣的性質的路則催生了一系列的問題。
Definition 1.3.3 (歐拉通路) 如果一個通路通過 \(G\) 中的每條邊恰好一次，稱該通路為歐拉通路。
歐拉通路其實就是遍歷所有邊的簡單通路。特別地，如果一個歐拉通路恰好是一個迴路，那麼稱其為歐拉迴路。存在歐拉迴路的圖叫歐拉圖。
Definition 1.3.4 (漢密爾頓通路) 如果一個通路通過 \(G\) 中的每個節點恰好一次，稱該通路為漢密爾頓通路。
漢密爾頓通路其實就是遍歷左右節點的基本通路，且注意漢密爾頓通路不需要經過所有的邊。特別地，如果一個漢密爾頓通路恰好是一個迴路（起點/終點認為只經過一次），那麼稱其為漢密爾頓迴路。存在漢密爾頓迴路的圖叫漢密爾頓圖。
1.4 連通性
Definition 1.4.1 (可達性) 從節點 \(v_i\) 到節點 \(v_j\) 間如果存在一條通路，則稱從 \(v_i\) 到 \(v_j\) 是可達的。
Definition 1.4.2 (連通性) 如果圖的任意兩點間可達，則稱該圖為連通圖，否則稱為非連通圖。
對於無向圖來說，連通性的概念比較簡單，而對於有向圖，由於可達性本身是有方向的，連通性則根據其方向也可以具體分為不同的連通程度。
- 強連通：任何兩節點間雙向可達。
- 單向連通：任何兩節點間至少一個方向可達。
- 弱連通：任何兩節點間只有忽略了所有邊的方向性才可達。
無向圖中的連通性可以看作是節點的一個等價類劃分。
同樣連通的圖，脆弱性（或說健壯性）還有區別，這種脆弱性體現在一些關鍵的節點或邊上。
Definition 1.4.3 (割點) 若刪去一個點後，圖的連通分支數增加，則稱該點為圖的一個割點
Definition 1.4.4 (點割集) 若刪去一個點集後，圖的連通分支數增加，則稱該點集為圖的一個點割集。含有k割頂點的點割集稱為k-點割集。若該點集中減少任何一個點都不再是點割集，則稱其為極小點割集。圖中含點數最少的點割集稱為圖的最小點割集
Definition 1.4.5 (連通度) 一個圖的連通度定義為最小點割集的點的個數。即最少需要去掉多少個點才能增加連通分支的個數
同樣的，割邊、邊割集、邊連通度的定義類似。
1.5 樹
Definition 1.5.1 (樹) 無迴路的連通圖稱為樹。
對於無迴路的非聯通圖，每個連通分支可以看作一個樹，因此稱為森林。
樹中度為1的節點稱為葉節點，度大於1的節點稱為分支結點。
對於樹，有非常多的等價表述
Theorem 1.5.1 對於圖 \(G=<V,E>, |V|=n, |E|=m\) 下面的命題互相等價：
- \(G\) 是樹 ( \(G\) 連通且無迴路)
- \(G\) 的每對節點間恰有一條基本通路
- \(G\) 連通且 \(m=n-1\)
- \(G\) 無迴路且 \(m=n-1\)
- \(G\) 連通且 \(G\) 的每一條邊都是割邊
- \(G\) 無迴路且在\(G\) 的任何不鄰接的節點之間加上一條邊，則恰形成一個迴路
- \(G\) 連通且\(G\) 的每個度大於1的節點都是割點
上面定義的樹並沒有根的概念，但一般我們會引入根以及節點之間的層級關係(親子關係)。
Definition 1.5.2 (有向樹) 有向圖形成的樹稱為有向樹。
Definition 1.5.3 (外向樹) 滿足以下條件的有向樹 \(T\) 稱為外向樹：
- \(T\) 有且只有一個入度為0的節點，稱為\(T\) 的根
- \(T\) 的其他節點入度均為1
\(T\) 中出度為0的節點稱為葉節點
隨之而來的還有其他的術語，例如樹的高度，節點的深度，二叉樹，完全樹等，這裡略。
1.6 二分圖
Definition 1.6.1 (二分圖) 設無向圖 \(G=<V,E>\) 中， \(V\) 的兩個非空子集 \(V_1, V_2\) 滿足
- \(V_1\cap V_2=\empty, V_1\cup V_2=V\)
- \(\forall e=(v_i,v_j)\in E, v_i\in V_1, v_j\in V_2\)
則稱 \(G\) 為二分圖。
如果 \(E=V_1\times V_2\) ，則稱 \(G\) 為完全二分圖，記作 \(K_{|V_1|,|V_2|}\) 。
很多二分圖長得並不像二分圖，例如節點數大於1的樹就是二分圖，其奇數層和偶數層節點形成了劃分。那麼有沒有更直接的辦法判斷一個圖是不是二分圖呢？
Theorem 1.6.1 (二分圖的充要條件) 圖 \(G\) 是二分圖 充分必要條件是 \(G\) 的所有迴路長度是偶數。
二分圖的應用問題往往涉及到另一概念，二分圖的匹配。
Definition 1.6.2 (匹配) 設 \(G=<V,E>\) 是二分圖， \(V_1, V_2\) 是兩個互補的節點集合， \(V_1=\{v_1,…,v_k\}\) ，若 \(V_2\) 存在 \(k\) 個不同的節點 \(\{v_1′,…,v_k’\}\subseteq V_2\) ，使得邊 \((v_i,v_i’)\in E (i=1,…,k)\) ，則稱 \(E’=\{(v_1,v_1′),…,(v_k,v_k’)\}\subseteq E\) 是 \(V_1\) 到 \(V_2\) 的一個匹配。特別地，如果有 \(|V_1|=|V_2|\) ，則該匹配稱為完美匹配。
1.7 平面圖
Definition 1.7.1 (平面圖) 一個圖可以畫在平面上並且使得不同的邊互不交疊，那麼稱該圖為平面圖；否則稱為非平面圖。
\(K_5\) ，\(K_{3,3}\) 是最重要的非平面圖，證明略。
Definition 1.7.2 (平面圖的面) 設 \(G\) 是平面圖，則 \(G\) 把整個平面劃分成若干區域，這些區域稱為 \(G\) 的平面 (也稱為域)。其中面積無限的面稱為無限面或外部面，其餘的稱為有限面或內部面。面的集合一般表示為 \(F\) .
對平面圖 \(G\) 的每一個面 \(f\in F\) ，圍繞 \(f\) 的邊界所構成的閉路長度稱為面 \(f\) 的度，記作 \(d(f)\) .
關於平面圖最重要的結論就是歐拉公式
Theorem 1.7.1 (歐拉公式) 設 \(G=<V,E>\) 是連通平面圖，其中 \(|V|=n,|E|=m,|F|=r\) 則 \(n-m+r=2\) .
由歐拉公式我們可以得到兩個關於平面圖的性質，若 \(G\) 是連通平面圖\(|V|=n,|E|=m\) ：
-
若 \(n\ge 3\) ，則 \(m\le 3n-6\)
-
若 \(G\) 無環無多重邊，則 \(min_{v\in V} d(v) \lt 5\)
Definition 1.7.3 (同胚) 設 \(G_1,G_2\) 是兩個圖，若 \(G_1,G_2\) 在增加或忽略一些次數為2的點後同構，則稱 \(G_1,G_2\) 同胚
Definition 1.7.4 (對偶圖) 給定平面圖 \(G=<V,E>\) 具有面 \(F=\{f_1,…,f_n\}\) ，若有圖 \(G^*=<V^*,E^*>\) 滿足下面的條件：
- 對於 \(G\) 的任意麵 \(f_i\) 的內部有且僅有一個節點 \(v_i^*\in V^*\)
- 對於 \(G\) 的面 \(f_i,f_j\) 的公共邊界 \(e_k\) ，有且僅有一條邊 \(e_k^*\in E^*\) ，使得 \(e_k^*=(v_i^*,v_j^*)\) ，且 \(e_k^*\) 與 \(e_k\) 相交. (\(v_i^*\) 在 \(f_i\) 內，\(v_j^*\) 在 \(f_j\) 內)
- 當且僅當 \(e_k\) 只是一個面 \(f_i\) 的邊界時， \(v_i^*\) 上有且僅有一個環 \(e_k^*\in E^*\) 且與 \(e_k\) 相交
則稱 \(G^*\) 是 \(G\) 的對偶圖
對偶圖其實就是把平面圖的面作為節點構造出來的，它具有以下特徵
- 任何平面圖的對偶圖必然是連通圖
- 平面圖的對偶圖也是平面圖
1.8 有向無環圖
Definition 1.8.1 (DAG) 無環的有向圖稱為有向無環圖，簡稱DAG
Definition 1.8.2 (AOV，AOE) 用頂點表示活動，用弧表示活動間優先關係的有向圖稱為Activity On Vertex network (AOV網)；用帶權邊表示活動的則稱為Activity On Edge network (AOE網)
Definition 1.8.3 (關鍵路徑AOE) AOE網表達的活動完成的整個實踐取決於從源點到匯點的最長路徑長度，該長度最長的路徑叫做關鍵路徑
1.9 網絡流
Definition 1.9.1 (網絡流圖) 設 \(G=<V,E>\) 是一個帶權有向圖，稱其為網絡流圖，如果其滿足以下條件：
- 僅有一個入度為0的頂點 \(s\) ，稱為源點或出發點
- 僅有一個出度為0的頂點 \(t\) ，稱為匯點或結束點
- 每條邊 \((u,v)\in E\) 有一個非負權值 \(c(u,v)\) ，稱為該邊的容量
網絡流圖來源於實際問題中的網絡流，因此也有一系列與實際對應非常強烈的術語：
- 流量：流網絡的每條邊上給定一個實數 \(0\le f(u,v) \le c(u,v)\) ，稱為該邊上的流量
- 飽和：滿足 \(f(u,v)=c(u,v)\) 的邊稱為飽和邊
- 可行流：如果有一組流量滿足條件：(1) 源點的流出量=匯點的流入量=整個網絡的流量 (2) 每個中間點的流入量等於流出量；那麼該組流量稱為整個網絡的一個可行流
- 最大流：所有可行流中，總流量最大的一個流叫做最大流
- 割：流網絡中頂點的一個劃分稱為割，如果源點和匯點分屬兩個劃分出的點集，記作 \(CUT(S,T)\)
- 正向割邊，逆向割邊：在割 \(CUT(S,T)\) 中，從 \(S\) 的某點到 \(T\) 的某點的邊稱為正向割邊，反之稱為逆向割邊
- 割的容量：割中所有正向割邊的容量之和
Definition 1.9.2 (殘留網絡) 給定一個流網絡 \(G\) 及其上的流量 \(f\) ，網絡 \(G\) 關於 \(f\) 的殘留網絡 \(G^*\) 與 \(G\) 有相同的頂點集，而網絡 \(G\) 中的每一條邊對應於 \(G^*\) 中的1條邊或2條邊：設 \((v,w)\) 是 \(G\) 的一條邊，則
- 若 \(f(v,w) \gt 0\) ，則 \((w,v)\) 是 \(G^*\) 中的一條邊，該邊的容量為 \(c^*(w,v)=f(u,v)\)
- 若 \(f(v,w)\lt c(u,v)\) ，則 \((v,w)\) 是 \(G^*\) 中的一條邊，該邊的容量為 \(c^*(v,w)=c(v,w)-f(v,w)\)
殘留網絡中的術語：
- 增廣路徑：從源點到匯點的一條簡單路徑稱為增廣路徑
- 正向邊，逆向邊：方向與增廣路徑一致，稱該邊為正向邊，反之稱為逆向邊
2. 問題
2.1 一筆畫問題 (歐拉圖)
一筆畫問題被抽象為尋找歐拉迴路的問題。
Problem 2.1 (一筆畫問題) 給定無向連通圖 \(G\) ，判斷 \(G\) 是否為歐拉圖。若是，找出一條歐拉迴路。
該問題已經從圖論的角度徹底解決，首先我們解決存在性。
Theorem 2.1.1 (歐拉迴路的存在性) 無向連通圖 \(G\) 是歐拉圖的充分必要條件是 \(G\) 的每個頂點的度都是偶數。
找到一條歐拉迴路的算法也已經被發現。
Theorem 2.1.2 (歐拉迴路的構造算法; Fleury算法) 從任一節點出發， 反覆地根據下面的條件從未經過的邊集合中選取邊：
- 與當前節點關聯。
- 除非無別的邊可選，否則不選取使得經過的邊集成為割的邊；如果選了這樣的邊，則算法終止。
一個簡單的推論是兩不同節點間存在歐拉通路的充分必要條件是這兩個節點的度為基數，其餘節點的度為偶數。這個問題可通過在兩節點之間加一條邊化歸為一筆畫問題。
2.2 中國郵遞員問題
Problem 2.2 (中國郵遞員問題) 給定非負有權無向連通圖 \(G\) ，找到一條迴路 \(C\) ，使其通過每條邊最少一次，且權值和最小。
該問題是一筆畫問題的擴展。如果圖是歐拉圖，則歐拉迴路就是最優迴路。
如果不存在歐拉迴路，則其中必存在有奇數度的節點，且這類的節點一定大於等於2個。因此有些邊需要再重複一次，使奇數邊的端點變為偶數邊的節點。
管梅谷首次提出基於上述想法的奇偶點圖上作業法(1962), Edmonds Johnson給出複雜度為 \(O(|V|^2|E|)\) 的有效算法，這裡略去。
2.3 漢密爾頓圖問題
Problem 2.3 (漢密爾頓圖) 給定無向連通圖 \(G\) ，判斷 \(G\) 是否為漢密爾頓圖。若是，找出一條漢密爾頓迴路。
目前漢密爾頓迴路的存在性還沒有得到有效的充分必要條件，且已經證明該問題是一個NP-hard問題。但是有非常多的相關定理給出一些充分條件或必要條件，這裡略去。
2.4 旅行售貨員問題 (TSP)
Problem 2.4 (Traveling Salesman Problem) 在非負加權無向完全圖中求最短長度的漢密爾頓圈。
該問題是漢密爾頓圖問題的擴展。該問題同樣是NP-hard問題。
2.5 圖的遍歷問題
Problem 2.5 (圖的遍歷) 給定連通圖 \(G\) 和出發點 \(v\) ，訪遍圖中所有的頂點，且每個頂點只訪問一次。
分為深度優先遍歷(DFS)和廣度優先遍歷(BFS)，在圖的搜索算法中還有基於啟發式的遍歷方法，但是基本思想都可以歸類到DFS或BFS。具體算法略。
2.6 圖的表示
總的來說，圖在數據結構里有鄰接矩陣，鄰接表等。鄰接矩陣雖然從存儲的角度來看效率並不高，但是在數學的角度上看有很多有趣的性質。例如，對角線可以判斷環是否存在， \(l\) 次冪的對角線可以判斷 \(l\) 長通路/迴路的個數，行和/列和可以計算出度/入度，可達性矩陣等。
還有其他的矩陣可以刻畫圖，例如：
- 關聯矩陣：與鄰接矩陣等價，刻畫點與邊之間的關聯關係。
- 拉普拉斯矩陣： \(L=D-W\) ，其中 \(D\) 是圖的度矩陣（對角矩陣，對角線上的元素是節點的度）， \(W\) 是圖的鄰接矩陣。
- 相似矩陣：任意兩點之間的權重值組成的矩陣，權重來源於距離度量，有\(\epsilon\) 鄰近法， \(K\) 鄰近法和全連接法。可以選擇不同的核函數定義權重，最常見的是全連接+高斯徑向核RBF。
2.7 樹的遍歷問題
圖的遍歷在樹上的特化，這裡延伸出了先序、中序、後序三種遍歷手段，略。
2.8 最小生成樹問題
Problem 2.8 (最小生成樹問題) 在帶權連通圖中求權值和最小的生成樹
兩個方向的貪心算法：加邊，破圈。
2.9 二分圖的匹配問題
Problem 2.9 (二分圖的匹配問題) 給定二分圖 \(G\) ，找出其中的一個最大匹配
匹配的存在性是一個重要的課題，這裡給出一個充分必要條件和一個充分條件。
Theorem 2.9.1 (匹配存在的充要條件) 二分圖 \(G\) 中存在從 \(V_1\) 到 \(V_2\) 的匹配，當且僅當 \(V_1\) 中任意 \(K\) 個頂點與 \(V_2\) 中的 \(K\) 個頂點都相鄰，其中 \(K=1,2,…,|V_1|\) .
Theorem 2.9.2 (匹配存在的充分條件) 二分圖 \(G\) 如果存在正整數 \(t\) 滿足：
- \(\forall v\in V_1, d(v)\ge t\)
- \(\forall v\in V_2, d(v) \le t\)
則 \(G\) 中存在 \(V_1\) 到 \(V_2\) 的匹配。
匹配的存在性解決後，則是尋找匹配的算法，即匈牙利算法，此處略。
2.10 圖的平面性判定問題
Problem 2.10 (圖的平面性判定問題) 判斷一個連通圖是否是平面圖
理論上有一個充要條件，但是實際應用困難
Theorem 2.10.1 (平面性的充要條件；Kuratowski定理) 一個圖是非平面圖當且僅當它包含與 \(K_5\) 或者 \(K_{3,3}\) 同胚的子圖
實際操作起來，我們先進行一些預處理：
- 若 \(G\) 非連通，只需檢驗每個連通分支
- 若 \(G\) 中存在割點 \(v\) ，可把 \(G\) 從割點處分離，構成若干個不含割點的連通子圖，稱為塊。 \(G\) 是平面圖當且僅當每個塊是平面圖
- 移去環和重邊
- 「消去」度為2的節點
經過這一系列預處理後：
- 若 \(m \lt 9\) 或 \(n \le 5\) ，則 \(G\) 是平面圖
- 若 \(m \gt 3n-6\) ，則 \(G\) 是非平面圖
- 否則用DMP算法進一步判斷
DMP算法此處略。
2.11 最短路徑問題
Problem 2.11 (最短路徑問題) 求帶權連通圖中任意兩點之間的最短路徑。
對於權值非負的連通圖，運用Dijkstra算法。
對於一般的圖，運用Bellman-Ford算法。
2.12 拓撲排序問題
Problem 2.12 (拓撲排序問題) 給定有向無環圖 \(G=<V,E>\) ，找到一個頂點序列，使得 \(\forall e=(u,v)\in E\) ， \(u\) 在序列中的位置先於 \(v\)
拓撲排序可以由貪心算法完成，反覆選擇入度為0的頂點並刪除之。
2.13 最大流問題
Problem 2.13 (最大流問題) 給定流網絡 \(G\) ，找到一個最大可行流
最大流問題的理論依據是最大流定理
Theorem 2.13.1 (最大流定理) 可行流 \(f\) 為最大流，當且僅當不存在關於 \(f\) 的增廣路徑
根據最大流定理可設計出一個最基本的求最大流的方法 (Ford-Fulkerson方法)：
- 初始時將 \(f\) 設置為零流
- 構建殘留網絡，尋找增廣路徑增廣，再修改殘留網絡，重複此過程直至無法找到增廣路徑
2.14 最小割問題
Problem 2.14 (最小割問題) 給定流網絡 \(G\) ，找到一個容量最小的割
該問題的求解涉及到割與流的關係
Theorem 2.14.1 若 \(f\) 是流網絡的一個流， \(CUT(S,T)\) 是任意一個割，那麼 \(f\) 的值等於正向割邊的流量與負向割邊的流量之差
該定理的推論：網絡的任何流不超過任何割的容量。
進一步地，
Theorem 2.14.2 在任何網絡中，如果 \(f\) 是一個流， \(CUT(S,T)\) 是一個割，且 \(f\) 的值等於 \(CUT(S,T)\) 的容量，那麼 \(f\) 是一個最大流，且 \(CUT(S,T)\) 是一個最小割
Theorem 2.14.3 (最大流最小割定理) 在任何網絡中，最大流的值等於最小割的容量
