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

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

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

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

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

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

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

1步是標(biāo)號過程，通過標(biāo)號來尋找可增廣鏈；第2

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

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

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

b)若邊，且時，令并給以標(biāo)號第十二頁，共二十八頁，編輯于2023年，星期五

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

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

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