網路流問題(network flow problem)一類重要的組合最佳化問題。研究網路流問題實際上是在研究最大流的問題。
基本介紹
- 中文名：網路流
- 外文名：Network flow
- 學科：數學、計算機科學
- 套用：通信
概念,最大流問題,最小割最大流定理,最小費用最大流問題,
概念
很多問題都可以轉化成網路流問題，如運輸貨物時的物流問題，水流問題，匹配問題等等。網路是一個各條邊都有權值和方向的圖。
網路流問題，一般情況下我們會把各種網路問題抽象成網路流問題，網路流是滿足以下性質的網路：每一條邊擁有一個最大的容量c，即該條邊可以容納的最大流量，f是流過該邊的實際流量，且總有f<=c。對於頂點（源點和匯點除外）都有流出的流量等於流入的流量。一個源點一個匯點，且對於源點來說其流入量為0，對於匯點來說流出量為0，源點的流出量等於匯點的流入量，對於最大流問題既是要找出流入匯點的最大流量值。
最大流問題
問題表述：給定一幅圖（n個結點，m條邊），每一條邊有一個容量，需要將一些物品從結點s（稱為源點）運送到結點t（稱為匯點），可以從其他結點中轉，求最大的運送量。
在介紹最大流問題的解決方法之前，先介紹幾個概念：反向弧，殘餘網路，增廣路徑，最大流定理。
反向弧：若從u到v的邊的容量為c ，這條邊上有流量 f 流過（稱為正向弧），則相當於v到u有一條容量為0的邊，其流量為- f ，這條邊就是反向弧。
反向弧的意義：反向弧的作用是起到有更優決策的時候會使當前選擇的弧會自動放棄。反向弧有流量的原因是因為如果剛剛選擇了正向弧，下一次如果存在更優策略使這f的流量流入匯點，就可以選擇反向弧，將流量 f 撤銷。
殘餘網路：計算出圖中的每條邊上容量與流量之差（稱為殘餘容量），即可得到殘餘網路。注意由於反向邊的存在，殘餘網路中的邊數可能到達原圖中邊數的兩倍。
舉例如下：觀察圖1，這種狀態下它的殘餘網路如圖2所示。
圖1 原圖
圖2 殘餘網路
最大流定理：如果殘留網路上找不到增廣路徑，則當前流為最大流；反之，如果當前流不為最大流，則一定有增廣路徑。
這樣的話，求解最大流就只需要在殘餘網路中尋找增廣路，直到不存在可以從s流向t 的增廣路，此時即為最大流。求解最大流問題的高效算法有 dinic,sap和isap。
最小割最大流定理
割：將圖1中所有頂點分成兩個集合S和 T = V - S ，其中源點s在集合S中，匯點t在集合T中。如果把 ” 起點在S中，終點在T中的邊全部刪除，就無法從s到達 t了。這樣的集合劃分（S,T）稱為一個割，它的容量定義為：∑(邊( u , v )的容量和)，其中 u ∈ S , v ∈ T ，即起點在 S 中，終點在 T 中的所有邊的容量和。（這裡所有的邊都不包括反向弧）
最小割：圖1中所有的割中，邊權值和最小的割為最小割。
最小割最大流定理：最大流的值為最小割的容量！
如何求最小割：求完最大流後，在殘留網路中從源點 s 開始 dfs ，將能到達的點標號（ c - f >0 的邊），已標號結點的集合為S，未標號結點集合為 T，則邊集[ S , T ]為最小割。
定理證明：
從s運送到t的物品必然通過跨越S和T的邊，所以從s到t的淨流量等於|f|=f（S,T）=∑f（u，v）≤∑c（u，v）=c（S,T）。(u∈S, v∈T)
注意這裡的割（S,T）是任取的，因此得到了一個重要的結論：對於任意s-t流和任意s-t割（S,T）,有|f|≤c（S,T）。
下面來看殘餘網路中沒有增廣路的情形。既然不存在增廣路，在殘餘網路中s和t並不連通。當BFS沒有找到任何s-t道路，把已標號結點集合看成S，令T=V-S，則在殘餘網路中S和T分離，因此在圖1中跨越S和T的所有弧滿載（這樣的邊才不會存在於殘餘網路中），且沒有從T回到S的流量，因此|f|= c（S,T）成立。
前面說過，對於任意的f和（S,T），都有|f|≤c（S,T）,而此處又找到了一組讓等號成立的f和（S,T）。這樣便證明了最小割最大流定理。
最小費用最大流問題
在保證最大流的情形下，網路中的邊，可能不只有流量還有費用，那么如果我們一方面希望網路擁有最大流，另一方面我們要求費用達到最小，這就是一個費用流的問題了，對於費用流的問題，事實上我們可以這么考慮，首先我們必須要找到的是最大流，另一方面我們需要費用最小，而在找最大流的時候我們總是在尋找增廣路來增廣，來使得我們能得到一個更大的流，那么另一方面要求費用最小，所以我們可以在尋找增廣路的時候找一條費用最小路來增廣，而費用我們也可以看成是距離類的東西，也就是這樣的話，我們可以用最短路，來找出這樣一個最小費用的路來進行增廣，而不斷增廣，即可得到最大流，這樣我們就可以得到最小費用最大流。
