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

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

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

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

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

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

三、求最大流的標號算法設已有一個可行流f，標號的方法可分為兩步：第

1步是標號過程，通過標號來尋找可增廣鏈；第2

步是調整過程，沿可增廣鏈調整f以增加流量。

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

a)若邊，且則令，并給以標號。

b)若邊，且時，令并給以標號第十二頁，共二十八頁，2022年，8月28日

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

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

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