第四節(jié)最大流問(wèn)題

第四節(jié)最大流問(wèn)題第一頁(yè)，共二十八頁(yè)，2022年，8月28日第二頁(yè)，共二十八頁(yè)，2022年，8月28日定義20設(shè)有向連通圖的每條邊上有非負(fù)數(shù)稱為邊容量，僅有一個(gè)r入次為0的點(diǎn)稱為發(fā)點(diǎn)（源），一個(gè)出次為0的點(diǎn)稱為收點(diǎn)（匯），其余點(diǎn)為中間點(diǎn)，這樣的網(wǎng)絡(luò)G稱為容量網(wǎng)絡(luò)，常記做。對(duì)任一G中的邊有流量，稱集合為G的一個(gè)流。稱滿足下列條件的流為可行流：（1）容量限制條件：對(duì)G中每條邊，有（2）平衡條件：對(duì)中間點(diǎn)，有（即中間點(diǎn)的物資的輸入量與輸出量相等）對(duì)收、發(fā)點(diǎn)有（即從點(diǎn)發(fā)出的物資總量等于點(diǎn)輸入量）W為網(wǎng)絡(luò)流的總流量。第三頁(yè)，共二十八頁(yè)，2022年，8月28日可行流總是存在的，例如就是一個(gè)流量為0的可行流。所謂最大流問(wèn)題就是在容量網(wǎng)絡(luò)中，尋找流量最大的可行流。一個(gè)流，當(dāng)則稱流對(duì)邊是飽和的，否則稱對(duì)不飽和。最大流問(wèn)題實(shí)際是個(gè)線性規(guī)劃問(wèn)題，但是利用它與圖的緊密關(guān)系，能更為直觀簡(jiǎn)便地求解。定義21容量網(wǎng)絡(luò)為發(fā)、收點(diǎn)，若有邊集為E的子集，將G分為兩個(gè)子圖其頂點(diǎn)集合分別記分別屬于，滿足：①不連通；②為的真子集，而仍連通，則稱為G的割集，記。

第四頁(yè)，共二十八頁(yè)，2022年，8月28日割集中所有始點(diǎn)在S，終點(diǎn)在的邊的容量之和，稱為的割集容量，記為。如圖5-41中，邊集和邊集都是G的割集，它們割集容量分別為9和11。容量網(wǎng)絡(luò)G的割集有多個(gè)，其中割集容量最小者稱為網(wǎng)絡(luò)G的最小割集容量（簡(jiǎn)稱最小割）。二、最大流-最小割定理由割集的定義不難看出，在容量網(wǎng)絡(luò)中割集是由到的必經(jīng)之路，無(wú)論拿掉哪個(gè)割集，到便不再相通，所以任何一個(gè)可行流的流量不會(huì)超過(guò)任一割集的容量，也即網(wǎng)絡(luò)的最大流與最小割容量（最小割）滿足下面定理。第五頁(yè)，共二十八頁(yè)，2022年，8月28日定理10

設(shè)f為網(wǎng)絡(luò)G=(V,E,C)的任一可行流，流量為是分離的任一割集，則有由此可知，若能找到一個(gè)可行流一個(gè)割集，使得的流量，則一定是最大流，而就是所有割集中容量最小的一個(gè)。下面證明最大流-最小割定理，定理的證明實(shí)際上就是給出了尋找最大流的方法。定理11（最大流-最小割定理）任一網(wǎng)絡(luò)G中，從到的最大流的流量等于分高的最小割的容量。第六頁(yè)，共二十八頁(yè)，2022年，8月28日證明設(shè)是一個(gè)最大流，流量為W，用下面的方法定義點(diǎn)集令若點(diǎn)且則令若點(diǎn)且則令在這種定義下，一定不屬于，若否，則得到一條從到的鏈，規(guī)定到為鏈的方向，鏈上與方向一致的邊叫前向邊，與方向相反的邊稱為后向邊，即如圖5-42中為前向邊為后向邊。根據(jù)的定義，中的前向邊上必有，后向邊上必有第七頁(yè)，共二十八頁(yè)，2022年，8月28日第八頁(yè)，共二十八頁(yè)，2022年，8月28日

令當(dāng)為前向邊當(dāng)為后向邊取，顯然。我們把修改為：為上前向邊為后向邊其余不難驗(yàn)證仍為可行流（即滿足容量限制條件與平衡條件），但是的總流量等于的流加，這與為最大流矛盾，所以不屬于。第九頁(yè)，共二十八頁(yè)，2022年，8月28日令，則。于是得到一個(gè)割集，對(duì)割集中的邊顯然有但流量W又滿足所以最大流的流量等于最小割的容量，定理得到證明。定義22容量網(wǎng)絡(luò)G，若為網(wǎng)絡(luò)中從到的一條鏈，給定向?yàn)閺牡?上的邊凡與同向稱為前向邊，凡與反向稱為后向邊，其集合分別用和表示，f是一個(gè)可行流，如果滿足第十頁(yè)，共二十八頁(yè)，2022年，8月28日

則稱為從到的（關(guān)于f的）可增廣鏈。推論可行流f是最大流的充要條件是不存在從到的（關(guān)于f的）可增廣鏈?？稍鰪V鏈的實(shí)際意義是：沿著這條鏈從到輸送流，還有潛力可挖，只需按照定理證明中的調(diào)整方法，就可以把流量提高，調(diào)整后的流，在各點(diǎn)仍滿足平衡條件及容量限制條件，即仍為可行流。這樣就得到了一個(gè)尋求最大流的方法：從一個(gè)可行流開始，尋求關(guān)于這個(gè)可行流的可增廣鏈，若存在，則可以經(jīng)過(guò)調(diào)整，得到一個(gè)新的可行流，其流量比原來(lái)的可行流要大，重復(fù)這個(gè)過(guò)程，直到不存在關(guān)于該流的可增廣鏈時(shí)就得到了最大流。第十一頁(yè)，共二十八頁(yè)，2022年，8月28日

三、求最大流的標(biāo)號(hào)算法設(shè)已有一個(gè)可行流f，標(biāo)號(hào)的方法可分為兩步：第

1步是標(biāo)號(hào)過(guò)程，通過(guò)標(biāo)號(hào)來(lái)尋找可增廣鏈；第2

步是調(diào)整過(guò)程，沿可增廣鏈調(diào)整f以增加流量。

1.標(biāo)號(hào)過(guò)程（1）給發(fā)點(diǎn)以標(biāo)號(hào)（2）選擇一個(gè)已標(biāo)號(hào)的頂點(diǎn)，對(duì)于的所有未標(biāo)號(hào)的鄰接點(diǎn)按下列規(guī)則處理：

a)若邊，且則令，并給以標(biāo)號(hào)。

b)若邊，且時(shí)，令并給以標(biāo)號(hào)第十二頁(yè)，共二十八頁(yè)，2022年，8月28日

（3）重復(fù)（2）直到收點(diǎn)被標(biāo)號(hào)或不再有頂點(diǎn)可標(biāo)號(hào)時(shí)為止。如若得到標(biāo)號(hào)，說(shuō)明存在一條可增廣鏈，轉(zhuǎn)（第2步）調(diào)整過(guò)程。若未獲得標(biāo)號(hào)，標(biāo)號(hào)過(guò)程已無(wú)法進(jìn)行時(shí)，說(shuō)明f已是最大流。

2.調(diào)整過(guò)程若是可增廣鏈上的前向邊（1）令若是可增廣鏈上的后向邊若不存在可增廣鏈上（2）去掉所有標(biāo)號(hào)，回到第1步，對(duì)可行流重新標(biāo)號(hào)。第十三頁(yè)，共二十八頁(yè)，2022年，8月28日例5.17圖5-43表明一個(gè)網(wǎng)絡(luò)及初始可行流，每條邊上的有序數(shù)表示，求這個(gè)網(wǎng)絡(luò)的最大流。先給標(biāo)以。檢查的鄰接點(diǎn)發(fā)現(xiàn)點(diǎn)滿足且令，給以標(biāo)號(hào)。同理給點(diǎn)以標(biāo)號(hào)。檢查點(diǎn)的尚未標(biāo)號(hào)的鄰接點(diǎn)發(fā)現(xiàn)滿足且令給以標(biāo)號(hào)。第十四頁(yè)，共二十八頁(yè)，2022年，8月28日第十五頁(yè)，共二十八頁(yè)，2022年，8月28日檢查與點(diǎn)鄰接的未標(biāo)號(hào)點(diǎn)有，發(fā)現(xiàn)點(diǎn)滿足且，令則給點(diǎn)以標(biāo)號(hào)。點(diǎn)未標(biāo)號(hào)，與鄰接，邊且所以令給以標(biāo)號(hào)。類似前面的步驟，可由得到標(biāo)號(hào)。由于已得到標(biāo)號(hào)，說(shuō)明存在增廣鏈，所以標(biāo)號(hào)過(guò)程結(jié)束，見圖5-44。第十六頁(yè)，共二十八頁(yè)，2022年，8月28日第十七頁(yè)，共二十八頁(yè)，2022年，8月28日轉(zhuǎn)入調(diào)整過(guò)程，令為調(diào)整量，從點(diǎn)開始，由逆增廣鏈方向按標(biāo)號(hào)找到點(diǎn)，令。再由點(diǎn)標(biāo)號(hào)找到前一個(gè)點(diǎn)，并令。按點(diǎn)標(biāo)號(hào)找到點(diǎn)。由于標(biāo)號(hào)為為反向邊，令由點(diǎn)的標(biāo)號(hào)在找到，令。由點(diǎn)找到，令調(diào)整過(guò)程結(jié)束，調(diào)整中的可增廣鏈見圖5-44，調(diào)整后的可行流見圖5-45。第十八頁(yè)，共二十八頁(yè)，2022年，8月28日第十九頁(yè)，共二十八頁(yè)，2022年，8月28日重新開始標(biāo)號(hào)過(guò)程，尋找可增廣鏈，當(dāng)標(biāo)到點(diǎn)為以后，與點(diǎn)鄰接的點(diǎn)都不滿足標(biāo)號(hào)條件，所以標(biāo)號(hào)無(wú)法再繼續(xù)，而點(diǎn)并為得到標(biāo)號(hào)，如圖5-45。這時(shí)，即為最大流的流量，算法結(jié)束。用標(biāo)號(hào)法在得到最大流的同時(shí)，可得到一個(gè)最小割。即圖5-45中虛線所示。標(biāo)號(hào)點(diǎn)集合為s，即未標(biāo)號(hào)點(diǎn)集合為此時(shí)割集第二十頁(yè)，共二十八頁(yè)，2022年，8月28日割集容量，與最大流的流量相等。由此也可以體會(huì)到最小割的意義，網(wǎng)絡(luò)從發(fā)點(diǎn)到收點(diǎn)的各通路中，由容量決定其通過(guò)能力，最小割則是這此路中的咽喉部分，或者叫瓶口，其容易最小，它決定了整個(gè)網(wǎng)絡(luò)的最大通過(guò)能力。要提高整個(gè)網(wǎng)絡(luò)的運(yùn)輸能力，必須首先改造這個(gè)咽喉部份的通過(guò)能力。求最大流的標(biāo)號(hào)算法還可用于解決多發(fā)點(diǎn)多收點(diǎn)網(wǎng)絡(luò)的最大劉問(wèn)題，設(shè)容量網(wǎng)絡(luò)G有若干發(fā)；若干個(gè)收點(diǎn)可以添加兩個(gè)新點(diǎn)，用容量為的有向邊分別連結(jié)得到新的網(wǎng)絡(luò)，為只有一個(gè)發(fā)點(diǎn)一個(gè)收點(diǎn)的網(wǎng)絡(luò)，求解的最大流問(wèn)題即可得到G的解。第二十一頁(yè)，共二十八頁(yè)，2022年，8月28日課堂練習(xí)1求下面網(wǎng)絡(luò)最大流，邊上數(shù)為vsv4v1v5v2vtv3(4,3)(10,4)(3,2)(1,1)(4,2)(3,2)(5,3)(4,3)(3,2)(7,6)(2,2)(8,3)第二十二頁(yè)，共二十八頁(yè)，2022年，8月28日最大匹配問(wèn)題：考慮工作分配問(wèn)題。有n個(gè)工人，m件工作，每個(gè)工人能力不同，各能勝任其中某幾項(xiàng)工作。假設(shè)每件工作只需要一人做，每人只做一件工作，怎樣分配才能盡量的工作有人做，更多的人有工作？這個(gè)問(wèn)題可以用圖的語(yǔ)言描述，如圖5-47。其中x1,x2,…,xn表示工人,y1,y2,…,ym表示工作，邊（xi,yj)表示第i個(gè)人能勝任第j項(xiàng)工作，這樣就得到了一個(gè)二部圖G，用點(diǎn)集X表示{x1,x2,…xn}，點(diǎn)集Y表示{y1,y2,…,ym},二部圖G=(X,Y,E)。上述的工作分配問(wèn)題就是要在圖G中找一個(gè)邊集E的子集，使得集中任何兩條邊沒(méi)有公共端點(diǎn)，最好的方案就是要使此邊集的邊數(shù)盡可能多，這就是匹配問(wèn)題。第二十三頁(yè)，共二十八頁(yè)，2022年，8月28日定義23

二部圖G=(X,Y,E)，M是邊集E的子集，若M中的任意兩條邊都沒(méi)有公共端點(diǎn)，則稱M為圖G的一個(gè)匹配（也稱對(duì)集）。M中任意一條邊的端點(diǎn)v稱為（關(guān)于M的）飽和點(diǎn)，G中其他定點(diǎn)稱為非飽和點(diǎn)。若不存在另一條匹配，則稱