管道網路中每條邊的最大通過能力（容量）是有限的，實際流量不超過容量。
最大流問題(maximum flow problem)，一種組合最最佳化問題，就是要討論如何充分利用裝置的能力，使得運輸的流量最大，以取得最好的效果。求最大流的標號算法最早由福特和福克遜於1956年提出，20世紀50年代福特(Ford)、福克遜(Fulkerson)建立的“網路流理論”，是網路套用的重要組成成分。
基本介紹
- 中文名：最大流問題
- 外文名：Maximum flow problem
- 別名：網路最大流問題
- 套用學科：運籌學、圖論
- 功能：組合最最佳化
- 時間：1956年
發現簡史,數學模型,網路流概念,圖和收發點,容量和流量,可行流,割（截）集,最小割定理,定理一,定理二,前後向弧,可增廣鏈,標號算法,算法思路,算法步驟,
發現簡史
最大流問題是一類套用極為廣泛的問題，例如在交通網路中有人流、車流、貨物流，供水網路中有水流，金融系統中現金流，等等。求最大流的標號算法最早由福特和福克遜於1956年提出，20世紀50年代福特(Ford)、福克遜(Fulkerson)建立的“網路流理論”，是網路套用的重要組成成分。
數學模型
最大流問題，是網路流理論研究的一個基本問題，求網路中一個可行流f*，使其流量v(f)達到最大， 這種流f稱為最大流，這個問題稱為(網路)最大流問題。最大流問題是一個特殊的線性規劃問題，就是在容量網路中，尋找流量最大的可行流。
最大流問題可以建立如下形式的線性規劃數學模型：
式中v(f)稱為這個可行流的流量、發點的淨輸出量或收點的淨輸出量。∞一般用標號法尋求有向最大流比用求線性規劃問題的一般方法要方便得多。
最大的標號算法還用於解決多發點多收點網路的最大問題，設容量網路G有若干個發點x1,x2,...,xm；若干收點y1,y2,...,yn，可以添加兩個新點vs,vt，用容量為∞的有向邊分別連線兩個新點vs與點x1,x2,...,xm，點y1,y2,...,yn與vt，得到新的網路G‘。G’是一個只有一個收點和發點的網路，求解最大流問題即可都得到G的解。
網路流概念
圖和收發點
一個圖是由點集V={vi}和V中元素的無序對的一個集合E={ek}所構成的二元組，記為G=(V,E)，V中的元素vi叫做頂點，E中的元素ek，叫做邊。
容量和流量
設有向連通圖G=(V,E)，G的每條邊(vi,vj)上的非負數cij稱為邊的容量。對任一G中的邊(vi,vj)有流量fij，稱集合f={fij}為網路G上的一個流。右圖即為一個有向連通圖，括弧中第一個數字代表容量，第二個數字代表流量。
可行流
稱滿足下列兩個條件的流為可行流：
1.容量限制條件：對G中的每條邊(vi,vj)，有0≤fij≤cij；即每條邊上的流量非負而且最大也只能達到容量的限制。
2.平衡條件：對中間點vi，有
，即物資的輸入量和輸出量相等。
對發、收點vs,vt,，有
，fij為網路流的總流量。
一個流f={fij}，當fij=cij，則稱流f對邊(vi,vj)是飽和的，否則稱f對(vi,vj)不飽和。
割（截）集
容量網路G=(V,E,C),vs,vt為發、收點，若有邊集E‘為E的子集，將G為兩個子圖G1,G2，即點集V被剖分其為兩個頂點集合分別記
，必有
。若有邊集E'為E的子集，滿足下列兩個的性質，則稱E’為G的割集（也稱截集），記
。
1.若把整個截集的弧從網路G=(V,E,C)中丟去，則不存在從vs和vt的有向路，即圖(V,E-E')不連通。
2.只要沒把整個截集刪去，就存在從vs和vt的有向路，即當E’‘為E的真子集，圖G(V,E-E'')仍連通。
由此可知，截集是從起點vs到終點vt的必經之路。
割集
中所有始點在S，終點在
的邊的容量之和，稱為
的割集容量，記為
。容量網路G的割集有很多個，其中割集容量最小這成為網路G的最小割集容量（簡稱最小割）。
最小割定理
由割集的定義不難看出，無論拿掉那個割集，發點vs到收點vt便不再相通，所以任何一個可行流都會經過割集，且不會超過任一割集的容量。最小割如同瓶頸一般，即使是最大流也無法超過最小割，網路的最大流與最小割容量滿足下面的定理（證明略）。
定理一
設f為網路G=(V,E,C)的任一可行流，流量為v(f)， 是分離vs,vt的任一割集，則有
。
定理二
由定理一可知，最大流的流量v(f)和某一割集K的容量相等，而且最大流的流量本身也不帶任一割集的容量，因此割集一定是最小的割集。
任一網路G中，從vs到vt的最大流的流量等於分離vs、vt的最小割的容量（最小的割集的容量）。
前後向弧
一條從起點vs到終點vt的鏈μ，規定從vs到vt的方向為鏈μ的方向，鏈上與μ方向一致的邊叫前向弧（邊），記作μ-；與μ方向相反的邊稱為後向弧（邊），記作μ+。
可增廣鏈
f是一個可行流，fij表示由i點指向j點的流量，如果滿足前向弧的流量非負且小於容量，或後向弧的流量大於0且不超過容量：
則稱μ為從vs到vt的關於f的可增廣鏈。
可增廣鏈的實際意義是：沿著這條從vs到vt輸送的流，仍有潛力可挖，只要前向弧的流量增加或後向弧的流量減少，就可以將截集的流量提高。調整後的流，在各點仍滿足平衡條件及容量限制條件，仍為可行流。
從另一個角度來說，可以提高流量的可行流也不是最大流，因此可行流f是最大流的充要條件是不存在從vs到vt的可增廣鏈。
標號算法
算法思路
從可行流和可增廣鏈關係來看，就可以知道一種尋求最大流的方法：從一個可行流開始，尋求關於這個可行流的可增廣鏈，若存在，則可以經過調整，得到一個新的可行流，其流量比原來的可行流要大，重複這個過程，直到不存在關於該流的可增廣鏈時就得到了最大流。v這種算法由Ford 和 Fulkerson於1956年提出，故又稱 Ford-Fulkerson標號法。
算法步驟
標號的方法可分為兩步：第一步是標號過程，通過標號來尋找可增廣鏈；第二步是調整過程，沿可增廣鏈調整f以增加流量。
1.標號過程
（1）給發點（始點）以標號(△,+∞)或(0,+∞)。
（2）選擇一個已標號的頂點vi，對於vi的所有未給標號的鄰接點vj按下列規則處理：
(a)若後向邊(vj,vi)∈E，且fji>0時，則令δj=min(fji,δi)，並給vj以標號(-vi,δj)，這表明vj點的vi點的邊最多可以減少δj的流量以提高整個網路的流量。
(b)若前向邊(vi,vj)∈E，且fij>cij時，令δj=min(cij-fij,δi)，並給vj以標號(+vi,δj)，這表明vi點到vj點的邊最多可以增加δj的流量以提高整個網路的流量。
括弧內的第一個數字表示這個節點得到的得到標號前的第一個結點的代號，第二個數字表示從上個標號節點到這個標號節點允許的最大調整量δ，假定發點的調整量不限，所以標記為+∞。
（3）重複（2）直到收點vt被標號或不再有頂點可被標號為止。
若vt沒有得到標號，說明標號過程已無法進行，可行流f已是最大流。若vt得到標號，說明存在一條可增廣鏈，轉入調整過程。標號若有多條增廣鏈時，不用刻意考慮哪種調整更適合，只需一條一條地轉入調整過程，不用全盤考慮。
2.調整過程
（1）令這條被找到的增廣鏈中所有的前向弧全部加上δj的流量，所有的後向弧全部減去δj的流量，至於不在增廣鏈之中的邊的流量則不需要調整。
（2）去掉所有標號，回到第1步，對可行流f’重新標號。
