管道網(wǎng)絡(luò)中每條邊的最大通過能力（容量）是有限的，實(shí)際流量不超過容量。最大流問題(maximum flow problem)，一種組合最優(yōu)化問題，就是要討論如何充分利用裝置的能力，使得運(yùn)輸?shù)牧髁孔畲螅匀〉米詈玫男Ч?/p>
最大流問題是一類應(yīng)用極為廣泛的問題，例如在交通網(wǎng)絡(luò)中有人流、車流、貨物流，供水網(wǎng)絡(luò)中有水流，金融系統(tǒng)中現(xiàn)金流，等等。求最大流的標(biāo)號(hào)算法最早由福特和福克遜于1956年提出，20世紀(jì)50年代福特(Ford)、福克遜(Fulkerson)建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成成分。
數(shù)學(xué)模型
最大流問題，是網(wǎng)絡(luò)流理論研究的一個(gè)基本問題，求網(wǎng)絡(luò)中一個(gè)可行流f*，使其流量v(f)達(dá)到最大，這種流f稱為最大流，這個(gè)問題稱為(網(wǎng)絡(luò))最大流問題。最大流問題是一個(gè)特殊的線性規(guī)劃問題，就是在容量網(wǎng)絡(luò)中，尋找流量最大的可行流。
最大流問題可以建立如下形式的線性規(guī)劃數(shù)學(xué)模型：
式中稱為這個(gè)可行流的流量、發(fā)點(diǎn)的凈輸出量或收點(diǎn)的凈輸出量。∞一般用標(biāo)號(hào)法尋求有向最大流比用求線性規(guī)劃問題的一般方法要方便得多。
最大的標(biāo)號(hào)算法還用于解決多發(fā)點(diǎn)多收點(diǎn)網(wǎng)絡(luò)的最大問題，設(shè)容量網(wǎng)絡(luò)G有若干個(gè)發(fā)點(diǎn)；若干收點(diǎn)，可以添加兩個(gè)新點(diǎn)vs,vt，用容量為∞的有向邊分別連接兩個(gè)新點(diǎn)v與點(diǎn)，點(diǎn)與，得到新的網(wǎng)路G‘。G’是一個(gè)只有一個(gè)收點(diǎn)和發(fā)點(diǎn)的網(wǎng)絡(luò)，求解最大流問題即可都得到G的解。
網(wǎng)絡(luò)流概念
圖和收發(fā)點(diǎn)
一個(gè)圖是由點(diǎn)集和V中元素的無序?qū)Φ囊粋€(gè)集合所構(gòu)成的二元組，記為，V中的元素叫做頂點(diǎn)，E中的元素，叫做邊。
僅有一個(gè)入次為0的點(diǎn)稱為發(fā)點(diǎn)(源)，一個(gè)出次為0的點(diǎn)稱為收點(diǎn)(匯)，其余點(diǎn)為中間點(diǎn)，這樣的網(wǎng)絡(luò)G稱為容量網(wǎng)絡(luò)，常記做。
容量和流量
設(shè)有向連通圖，G的每條邊上的非負(fù)數(shù)稱為邊的容量。對(duì)任一G中的邊有流量，稱集合為網(wǎng)絡(luò)G上的一個(gè)流。右圖即為一個(gè)有向連通圖，括號(hào)中第一個(gè)數(shù)字代表容量，第二個(gè)數(shù)字代表流量。
可行流
稱滿足下列兩個(gè)條件的流為可行流：
1.容量限制條件：對(duì)G中的每條邊，有；即每條邊上的流量非負(fù)而且最大也只能達(dá)到容量的限制。
2.平衡條件：對(duì)中間點(diǎn)，有，即物資的輸入量和輸出量相等。
對(duì)發(fā)、收點(diǎn)，有，為網(wǎng)絡(luò)流的總流量。
一個(gè)流，當(dāng)，則稱流f對(duì)邊(是飽和的，否則稱f對(duì)不飽和。
割（截）集
容量網(wǎng)路,為發(fā)、收點(diǎn)，若有邊集E‘為E的子集，將G為兩個(gè)子圖，即點(diǎn)集V被剖分其為兩個(gè)頂點(diǎn)集合分別記，必有。若有邊集E'為E的子集，滿足下列兩個(gè)的性質(zhì)，則稱E’為G的割集（也稱截集），記。
1.若把整個(gè)截集的弧從網(wǎng)絡(luò)中丟去，則不存在從v和vt的有向路，即圖不連通。
2.只要沒把整個(gè)截集刪去，就存在從和的有向路，即當(dāng)E’‘為E的真子集，圖仍連通。
由此可知，截集是從起點(diǎn)到終點(diǎn)的必經(jīng)之路。
割集 中所有始點(diǎn)在S，終點(diǎn)在 的邊的容量之和，稱為 的割集容量，記為。容量網(wǎng)絡(luò)G的割集有很多個(gè)，其中割集容量最小這成為網(wǎng)絡(luò)G的最小割集容量（簡(jiǎn)稱最小割）。
最小割定理
由割集的定義不難看出，無論拿掉那個(gè)割集，發(fā)點(diǎn)到收點(diǎn)便不再相通，所以任何一個(gè)可行流都會(huì)經(jīng)過割集，且不會(huì)超過任一割集的容量。最小割如同瓶頸一般，即使是最大流也無法超過最小割，網(wǎng)絡(luò)的最大流與最小割容量滿足下面的定理（證明略）。
定理一
設(shè)f為網(wǎng)絡(luò)的任一可行流，流量為v(f)，是分離的任一割集，則有。
定理二
由定理一可知，最大流的流量和某一割集K的容量相等，而且最大流的流量本身也不帶任一割集的容量，因此割集一定是最小的割集。
任一網(wǎng)絡(luò)G中，從到的最大流的流量等于分離的最小割的容量（最小的割集的容量）。
前后向弧
一條從起點(diǎn)v到終點(diǎn)vt的鏈μ，規(guī)定從v到v的方向?yàn)殒湨痰姆较颍溕吓cμ方向一致的邊叫前向弧（邊），記作；與μ方向相反的邊稱為后向弧（邊），記作。
可增廣鏈
f是一個(gè)可行流，表示由i點(diǎn)指向j點(diǎn)的流量，如果滿足前向弧的流量非負(fù)且小于容量，或后向弧的流量大于0且不超過容量：
則稱μ為從v到v的關(guān)于f的可增廣鏈。
可增廣鏈的實(shí)際意義是：沿著這條從v到v輸送的流，仍有潛力可挖，只要前向弧的流量增加或后向弧的流量減少，就可以將截集的流量提高。調(diào)整后的流，在各點(diǎn)仍滿足平衡條件及容量限制條件，仍為可行流。
從另一個(gè)角度來說，可以提高流量的可行流也不是最大流，因此可行流f是最大流的充要條件是不存在從v到v的可增廣鏈。
標(biāo)號(hào)算法
算法思路
從可行流和可增廣鏈關(guān)系來看，就可以知道一種尋求最大流的方法：從一個(gè)可行流開始，尋求關(guān)于這個(gè)可行流的可增廣鏈，若存在，則可以經(jīng)過調(diào)整，得到一個(gè)新的可行流，其流量比原來的可行流要大，重復(fù)這個(gè)過程，直到不存在關(guān)于該流的可增廣鏈時(shí)就得到了最大流。 ? v這種算法由Ford 和 Fulkerson于1956年提出，故又稱 Ford-Fulkerson標(biāo)號(hào)法。
算法步驟
標(biāo)號(hào)的方法可分為兩步：第一步是標(biāo)號(hào)過程，通過標(biāo)號(hào)來尋找可增廣鏈；第二步是調(diào)整過程，沿可增廣連調(diào)整f以增加流量。
1.標(biāo)號(hào)過程
（1）給發(fā)點(diǎn)（始點(diǎn)）以標(biāo)號(hào)或。
（2）選擇一個(gè)已標(biāo)號(hào)的頂點(diǎn)v，對(duì)于v的所有未給標(biāo)號(hào)的鄰接點(diǎn)v按下列規(guī)則處理：
(a)若后向邊，且時(shí)，則令，并給v以標(biāo)號(hào)，這表明v點(diǎn)的v點(diǎn)的邊最多可以減少δ的流量以提高整個(gè)網(wǎng)絡(luò)的流量。
(b)若前向邊，且時(shí)，令，并給v以標(biāo)號(hào)，這表明v點(diǎn)到v點(diǎn)的邊最多可以增加δ的流量以提高整個(gè)網(wǎng)絡(luò)的流量。
括弧內(nèi)的第一個(gè)數(shù)字表示這個(gè)節(jié)點(diǎn)得到的得到標(biāo)號(hào)前的第一個(gè)結(jié)點(diǎn)的代號(hào)，第二個(gè)數(shù)字表示從上個(gè)標(biāo)號(hào)節(jié)點(diǎn)到這個(gè)標(biāo)號(hào)節(jié)點(diǎn)允許的最大調(diào)整量δ，假定發(fā)點(diǎn)的調(diào)整量不限，所以標(biāo)記為+∞。
（3）重復(fù)（2）直到收點(diǎn)v被標(biāo)號(hào)或不再有頂點(diǎn)可被標(biāo)號(hào)為止。
若v沒有得到標(biāo)號(hào)，說明標(biāo)號(hào)過程已無法進(jìn)行，可行流f已是最大流。若v得到標(biāo)號(hào)，說明存在一條可增廣鏈，轉(zhuǎn)入調(diào)整過程。標(biāo)號(hào)若有多條增廣鏈時(shí)，不用刻意考慮哪種調(diào)整更適合，只需一條一條地轉(zhuǎn)入調(diào)整過程，不用全盤考慮。
2.調(diào)整過程
（1）令這條被找到的增廣鏈中所有的前向弧全部加上δ的流量，所有的后向弧全部減去δ的流量，至于不在增廣鏈之中的邊的流量則不需要調(diào)整。
（2）去掉所有標(biāo)號(hào)，回到第1步，對(duì)可行流重新標(biāo)號(hào)。
參考資料 >