最大閉合權(quán)圖

1、最大閉合權(quán)圖最大閉合權(quán)圖一些符號和定義一些符號和定義n最大權(quán)閉合圖：在一個圖中，我們選取一些點構(gòu)最大權(quán)閉合圖：在一個圖中，我們選取一些點構(gòu)成集合，記為成集合，記為V，且集合中的出邊，且集合中的出邊(即集合中的點即集合中的點的向外連出的弧的向外連出的弧)，所指向的終點，所指向的終點(弧頭弧頭)也在也在V中，中，則我們稱則我們稱V為閉合圖。最大權(quán)閉合圖即在所有閉為閉合圖。最大權(quán)閉合圖即在所有閉合圖中，集合中點的權(quán)值之和最大的合圖中，集合中點的權(quán)值之和最大的V，我們稱，我們稱V為最大權(quán)閉合圖。為最大權(quán)閉合圖。 n割：使得從源點到匯點的路集為空集時，一些弧割：使得從源點到匯點的路集為空集時，一些弧的集

2、合的集合 n簡單割：割集的每條邊都與簡單割：割集的每條邊都與S或或T關(guān)聯(lián)。關(guān)聯(lián)。 n最小割：圖中所有的割中，邊權(quán)值和最小的割。最小割：圖中所有的割中，邊權(quán)值和最小的割。解決方法解決方法n建圖建圖:構(gòu)造一個源點構(gòu)造一個源點S，匯點，匯點T。我們將。我們將S與所有權(quán)與所有權(quán)值為正的點連一條容量為其權(quán)值的邊，將所有權(quán)值為正的點連一條容量為其權(quán)值的邊，將所有權(quán)值為負的點與值為負的點與T連一條容量為其權(quán)值的絕對值的連一條容量為其權(quán)值的絕對值的邊，原來的邊將其容量定為正無窮。邊，原來的邊將其容量定為正無窮。 n把最大閉合權(quán)圖變成了最小割把最大閉合權(quán)圖變成了最小割n再把最小割轉(zhuǎn)換成了最大流再把最小割轉(zhuǎn)換成了

3、最大流相關(guān)證明相關(guān)證明n1.最小割為簡單割最小割為簡單割 n2.閉合圖是簡單割閉合圖是簡單割 n3.簡單割是閉合圖簡單割是閉合圖 n4.證明最小割所產(chǎn)生的兩個集合中，其源點證明最小割所產(chǎn)生的兩個集合中，其源點S所所在集合在集合(除去除去S)為最大權(quán)閉合圖。為最大權(quán)閉合圖。/到此為止，最大閉合權(quán)圖即是最小割到此為止，最大閉合權(quán)圖即是最小割n5.最小割是最大流最小割是最大流(最小割最大流定理最小割最大流定理)/到此為止，最大閉合權(quán)圖即是最大流到此為止，最大閉合權(quán)圖即是最大流最小割為簡單割最小割為簡單割n因為除因為除S和和T之外的點間的邊的容量是正無窮，最之外的點間的邊的容量是正無窮，最小割的容量不

4、可能為正無窮。所以，得證。小割的容量不可能為正無窮。所以，得證。 閉合圖是簡單割閉合圖是簡單割n利用反證法利用反證法n如果閉合圖不是簡單割。那么說明有一條邊是容如果閉合圖不是簡單割。那么說明有一條邊是容量為正無窮的邊，則說明閉合圖中有一條出邊的量為正無窮的邊，則說明閉合圖中有一條出邊的終點不在閉合圖中，矛盾。終點不在閉合圖中，矛盾。 所以，得證。所以，得證。簡單割為閉合圖簡單割為閉合圖n因為簡單割不含正無窮的邊，所以不含有連向另因為簡單割不含正無窮的邊，所以不含有連向另一個集合（除一個集合（除T）的點，所以其出邊的終點都在）的點，所以其出邊的終點都在簡單割中，滿足閉合圖定義。所以，得證。簡單割

5、中，滿足閉合圖定義。所以，得證。證明最小割所產(chǎn)生的兩個割集中，其源點證明最小割所產(chǎn)生的兩個割集中，其源點s所在集合（除所在集合（除去去S）為最大閉合權(quán)圖（說實話，這里我也沒太明白）為最大閉合權(quán)圖（說實話，這里我也沒太明白）n首先我們記一個簡單割的容量為首先我們記一個簡單割的容量為C,且且S所在集合為所在集合為N，T所在集合為所在集合為M。n則則C=M中所有權(quán)值為正的點的權(quán)值中所有權(quán)值為正的點的權(quán)值(即即S與與M中點相連的邊的容中點相連的邊的容量量)+N中所有權(quán)值為負的點權(quán)值的絕對值中所有權(quán)值為負的點權(quán)值的絕對值(即即N中點與中點與T中點相連邊的中點相連邊的容量容量)。記。記(C=x1+y1);

6、(很好理解，不理解畫一個圖或想象一下就明很好理解，不理解畫一個圖或想象一下就明白了白了)。n我們記我們記N這個閉合圖的權(quán)值和為這個閉合圖的權(quán)值和為W。n則則W=N中權(quán)值為正的點的權(quán)值中權(quán)值為正的點的權(quán)值-N中權(quán)值為負的點的權(quán)值的絕對值。中權(quán)值為負的點的權(quán)值的絕對值。記記(W=x2-y2);n則則W+C=x1+y1+x2-y2。n因為明顯因為明顯y1=y2，所以，所以W+C=x1+x2;nx1為為M中所有權(quán)值為正的點的權(quán)值，中所有權(quán)值為正的點的權(quán)值，x2為為N中權(quán)值為正的點的權(quán)值。中權(quán)值為正的點的權(quán)值。n所以所以x1+x2=所有權(quán)值為正的點的權(quán)值之和所有權(quán)值為正的點的權(quán)值之和(記為記為TOT).

7、n所以我們得到所以我們得到W+C=TOT.整理一下整理一下W=TOT-C.n到這里我們就得到了閉合圖的權(quán)值與簡單割的容量的關(guān)系。到這里我們就得到了閉合圖的權(quán)值與簡單割的容量的關(guān)系。n 因為因為TOT為定值，所以我們欲使為定值，所以我們欲使W最大，即最大，即C最小，即此時這個簡單最小，即此時這個簡單割為最小割，此時閉合圖為其源點割為最小割，此時閉合圖為其源點S所在集合所在集合(除去除去S)。得證。得證。到此為止，最大閉合權(quán)圖即是最小割到此為止，最大閉合權(quán)圖即是最小割證明最小割就是最大流（最小割最大流定理）證明最小割就是最大流（最小割最大流定理）n從從s運送到運送到t的物品必然通過跨越的物品必然通

8、過跨越S和和T的邊，所以從的邊，所以從S到到T的的凈流量等于凈流量等于|f|=f（S,T）= =c(S,T)n這里的割（這里的割（S,T）是任意取得，所以得到了一個重要的結(jié)論：）是任意取得，所以得到了一個重要的結(jié)論：對于任意對于任意s-t流流f和任意和任意s-t割（割（S,T），有），有|f| c（S,T）。）。n下面來看殘量網(wǎng)絡中沒有增廣路的情形。下面來看殘量網(wǎng)絡中沒有增廣路的情形。n既然不存在增廣路，在殘量網(wǎng)絡中既然不存在增廣路，在殘量網(wǎng)絡中s和和t并不連通。當并不連通。當BFS沒沒有找到任何有找到任何s-t道路時，把以標號的節(jié)點（道路時，把以標號的節(jié)點（au0的結(jié)點的結(jié)點u）集合看成集合看成S，另，另T=V-S，則殘量網(wǎng)絡中的，則殘量網(wǎng)絡中的S和和T分離，因此分離，因此在原圖中跨越在原圖中跨越S和和T所有弧均滿載（這樣的邊才不會存在于所有弧均滿載（這樣的邊才不會存在于殘量網(wǎng)絡中），且沒有從殘量網(wǎng)絡中），且沒有從T回到回到S的流量，因此的流量，因此|f| c（S,T）成立。）成立。(u,v),fu S v Tc(u,v),u S v T證明最小割就是最大流（最小割最大流定理）證明最小割就是最大流（最小割最大流定理）n前面說過，對于任意的前面說過，對于任意的f和（和（S,T），都有），都有|f|= c（S,T）。而我們又找到了一組讓等