網(wǎng)絡(luò)流問(wèn)題是圖論中一類常見(jiàn)的問(wèn)題窗宇。許多系統(tǒng)都包含了流量，例如瞳浦，公路系統(tǒng)中有車輛流担映，控制系統(tǒng)中有信息流，供水系統(tǒng)中有水流叫潦，金融系統(tǒng)中有現(xiàn)金流等等。先看一個(gè)運(yùn)輸方案設(shè)計(jì)的例子官硝。圖6.1(a)是連接產(chǎn)品產(chǎn)地Vs和銷售地Vt的交通網(wǎng)矗蕊，每一條弧代表兩點(diǎn)間的運(yùn)輸線，弧旁的數(shù)字表示這條運(yùn)輸線的最大通過(guò)能力∏饧埽現(xiàn)在要求制定一個(gè)運(yùn)輸方案傻咖，使得從Vs運(yùn)輸?shù)絍t的產(chǎn)品數(shù)量最多。
在上面的例子中岖研，任何一個(gè)方案都應(yīng)該滿足以下三點(diǎn)要求：
1)實(shí)際運(yùn)輸量不能是負(fù)的卿操；
2)每條弧的實(shí)際運(yùn)輸量不能大于該弧的容量；
3)除了Vs和Vt外孙援，對(duì)其它頂點(diǎn)來(lái)說(shuō)害淤，所有流入的運(yùn)輸量總和應(yīng)該等于所有流出的運(yùn)輸量總和。
好了拓售，我們現(xiàn)在面臨的就是一個(gè)典型的“最大流”問(wèn)題窥摄。怎么解決它呢？
還是用上面的例子础淤，看一個(gè)啟發(fā)性的問(wèn)題：
a崭放，b，c三條線把圖的頂點(diǎn)分成了兩部分鸽凶。注意紅色的a線b線與藍(lán)色的c線有所區(qū)別：紅線分割之后币砂，網(wǎng)絡(luò)流只會(huì)從源點(diǎn)Vs所在的一側(cè)流向目的地Vt所在的一側(cè)，而藍(lán)線不能保證這種性質(zhì)玻侥。我們把網(wǎng)絡(luò)流只會(huì)從源點(diǎn)Vs所在的一側(cè)流向目的地Vt所在一側(cè)的劃分線叫做網(wǎng)絡(luò)的割線决摧。由于貨物只會(huì)從割線的一側(cè)流到另一側(cè)，而絕對(duì)不會(huì)發(fā)生逆流，所以割線有個(gè)非常重要的性質(zhì)：割線上的流量是瓶頸蜜徽，整張圖上的最大流量不能超過(guò)任意一個(gè)割線上的流量祝懂。事實(shí)上，整張圖的流量等于割線上的最小流量拘鞋。這就是著名的最大流-最小割定理砚蓬。
知道了最大流的上限是最小割只能算是得到一個(gè)籠統(tǒng)的性質(zhì)，接下來(lái)還有兩個(gè)更重要的問(wèn)題：最小割是多少盆色？以及更重要的：與最小割對(duì)應(yīng)的通路是哪條灰蛙？
解決這些問(wèn)題需要用到一個(gè)重要的概念：增廣路。所謂增廣路隔躲，通俗的講就是從源點(diǎn)到目的地點(diǎn)摩梧，仍然有改進(jìn)余地的一條通路。嚴(yán)格的定義如下：
假設(shè)已經(jīng)存在一個(gè)從源點(diǎn)到目的地點(diǎn)的流量方案f宣旱，一個(gè)連接源點(diǎn)和目的地點(diǎn)的路徑P（注意從源點(diǎn)到目的地點(diǎn)仅父，P是有方向的）。對(duì)于P經(jīng)過(guò)的任意相鄰兩點(diǎn)間的弧t：
1）當(dāng)t與f流經(jīng)它的方向相同時(shí)浑吟，如果f的流量小于t的容量笙纤，或者
2）當(dāng)t與f流經(jīng)它的方向相反時(shí)，如果f的流量大于0.
則P稱為f的一條增廣路组力。
（上面的定義太枯燥了省容，我拿人話解釋一下：方向相同時(shí)，如果f的流量小于弧的容量燎字，表示沒(méi)有弧上還有潛在的運(yùn)輸能力可以使用腥椒；方向相反表示根本沒(méi)辦法這么分配，如果已經(jīng)犯錯(cuò)了分配了那就趕緊改過(guò)來(lái)）
根據(jù)定義可以推斷出來(lái)候衍，如果一個(gè)方案f中存在增廣路笼蛛，那么它就不是最優(yōu)的，我們需要把這條增廣路給修理好脱柱。于是就有了下面增廣路算法：為了得到最大流伐弹，可以從任何一個(gè)可行流開(kāi)始，沿著增廣路對(duì)網(wǎng)絡(luò)流進(jìn)行優(yōu)化修改榨为，直到網(wǎng)絡(luò)中不存在增廣路為止惨好，算法的基本流程是：
(1)取一個(gè)可行流f作為初始流（如果沒(méi)有給定初始流，則取零流f={ 0 }作為初始流）随闺；
(2)尋找關(guān)于f的增廣路P日川，如果找到，則沿著這條增廣路P將f改進(jìn)成一個(gè)更大的流矩乐；
(3)重復(fù)第(2)步直到f不存在增廣路為止龄句。
增廣路算法的關(guān)鍵是如何尋找增廣回论，目前已有幾種成熟的算法。今天太晚了分歇，我們明天介紹一下（受不了自己這么賣關(guān)子了~~）
