資源描述：
《教程：最大流-最小割定理.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、最大流最小割定理網(wǎng)絡(luò)流之二一、割的有關(guān)概念和定量1、割的定義：割（CUT）是網(wǎng)絡(luò)中頂點的一個劃分，它把網(wǎng)絡(luò)中的所有頂點劃分成兩個頂點集合S和T，其中源點s∈S，匯點t∈T。記為CUT（S,T）。如右圖：源點：s=1；匯點：t=5。框外是容量，框內(nèi)是流量12435642345412124352331st1）、頂點集合S={1，2，3}和T={4，5}構(gòu)成一個割。12435642345412124352331st12435642345412124352331st2）、頂點集合S={1，3}，T={2，4，5}構(gòu)成一個割。12
2、435642345412124352331st3）、頂點集合S={1，3，5}，T={2，4}不能構(gòu)成一個割。？◆如果一條弧的兩個頂點分別屬于頂點集S和T（一個頂點在S，另一個在T），那么這條弧稱為割CUT（S,T）的一條割邊。◆從S指向T的割邊是正向割邊；◆從T指向S的割邊是逆向割邊。如：頂點集合S={1，3}，T={2，4，5}構(gòu)成一個割。12435642345412124352331st正向割邊：1?2;3?5逆向割邊：2?3◆割CUT（S,T）中所有正向割邊的容量和稱為割CUT（S,T）的容量。不同割的容量不同。
3、12435642345412124352331st容量為：3+4=712435642345412124352331st割的容量：4+4=8割的正向流量：4+2=6逆向割的流量：12、網(wǎng)絡(luò)流與割的關(guān)系：12435642345412124352331st網(wǎng)絡(luò)流量：51234割正逆161250350450割的流量定理一：如果f是網(wǎng)絡(luò)中的一個流，CUT（S,T）是任意一個割，那么f的值等于正向割邊的流量與負向割邊的流量之差。證明：設(shè)X和Y是網(wǎng)絡(luò)中的兩個頂點集合，用f（X,Y）表示從X中的一個頂點指向Y的一個頂點的所有?。ɑ∥苍赬
4、中，弧頭在Y中：X?Y）的流量和.只需證明：f=f(S,T)-f(T,S)即可。如果X∩Y=，那么：f(X,(Y1∪Y2))=f(X,Y1)+f(X,Y2)f((X1∪X2),Y)=f(X1,Y)+f(X2,Y)成立。下列結(jié)論成立：根據(jù)網(wǎng)絡(luò)流的特點：如果V既不是源點也不是匯點，那么：f({V},S∪T)-f(S∪T,{V})=0;任何一個點，流入的與流出的量相等。如果V是源，那么：f({V},S∪T)-f(S∪T,{V})=f對于S中的所有點V都有上述關(guān)系式，相加得到：f(S,S∪T)-f(S∪T,S)=f又因為：f(S
5、,S∪T)-f(S∪T,S)=(f(S,S)+f(S,T))-(f(S,S)+f(T,S))=f(S,T)-f(T,S)所以：f=f(S,T)-f(T,S)定理得證推論1：如果f是網(wǎng)絡(luò)中的一個流，CUT（S,T）是一個割，那么f的值不超過割CUT（S,T）的容量。f=f(S,T)-f(T,S)<=f(S,T)<=割CUT（S,T）的容量推論2：網(wǎng)絡(luò)中的最大流不超過任何割的容量定量2：在任何網(wǎng)絡(luò)中，如果f是一個流，CUT（S,T）是一個割，且f的值等于割CUT（S,T）的容量，那么f是一個最大流，CUT（S,T）是一個最小
6、割（容量最小的割）。令割CUT（S,T）的容量為C，所以流f的流量也為C。假設(shè)另外的任意流f1，流量為c1，根據(jù)流量不超過割的容量，則c1<=c,所以f是最大流。假設(shè)另外的任意割CUT（S1,T1），容量為c1，根據(jù)流量不超過割的容量，所以有c1>=c,故，CUT（S,T）是最小割。證明：定量3：最大流最小割定量：在任何的網(wǎng)絡(luò)中，最大流的值等于最小割的容量。12435642345212124354234522211122最大流：7S={1,2,3},T={4,5}Cut(S,T)是最小割，容量＝３＋４＝７結(jié)論1：最大流時
7、，最小割cut（S，T）中，正向割邊的流量=容量，逆向割邊的流量為0。否則還可以增廣。結(jié)論2：在最小割中cut（S，T）中：①源點s∈S。②如果i∈S，結(jié)點j滿足：有弧,并且c[I,j]>f[I,j]或者有弧并且f[j,i]>0,那么j∈S。//否則不是最小割即從s出發(fā)能找到的含有殘留的點組成集合S。其余的點組成集合T。怎樣求集合S？數(shù)組b[i]記錄增廣路徑上結(jié)點i的前驅(qū)結(jié)點。初始值b[]=-1，b[1]=0；假設(shè)1是源點。如果b[i]〉-1（有前驅(qū)，能從源點1找到的點），那么，i∈S。怎樣求正向割邊
8、和逆向割邊？水流管道的最大流量由最細的管子容量決定的二、最大流最小割定量的應(yīng)用1、太空飛行計劃問題【問題描述：】W教授正在為國家航天中心計劃一系列的太空飛行。每次太空飛行可進行一系列商業(yè)性實驗而獲取利潤。現(xiàn)已確定了一個可供選擇的實驗集合E={E1，E2，…，Em}，和進行這些實驗需要使用的全部儀器的集合I={I1，I
