教程：最大流-最小割定理課件

最大流最小割定理網(wǎng)絡(luò)流之二一、割的有關(guān)概念和定量1、割的定義：割（CUT）是網(wǎng)絡(luò)中頂點(diǎn)的一個(gè)劃分，它把網(wǎng)絡(luò)中的所有頂點(diǎn)劃分成兩個(gè)頂點(diǎn)集合S和T，其中源點(diǎn)s∈S，匯點(diǎn)t∈T。記為CUT（S,T）。如右圖：源點(diǎn)：s=1；匯點(diǎn)：t=5?？蛲馐侨萘?，框內(nèi)是流量12435642345412124352331st1）、頂點(diǎn)集合S={1，2，3}和T={4，5}構(gòu)成一個(gè)割。12435642345412124352331st12435642345412124352331st3）、頂點(diǎn)集合S={1，3，5}，T={2，4}不能構(gòu)成一個(gè)割。？◆如果一條弧的兩個(gè)頂點(diǎn)分別屬于頂點(diǎn)集S和T（一個(gè)頂點(diǎn)在S，另一個(gè)在T），那么這條弧稱為割CUT（S,T）的一條割邊。◆從S指向T的割邊是正向割邊；◆從T指向S的割邊是逆向割邊。如：頂點(diǎn)集合S={1，3}，T={2，4，5}構(gòu)成一個(gè)割。12435642345412124352331st正向割邊：12;35逆向割邊：23◆割CUT（S,T）中所有正向割邊的容量和稱為割CUT（S,T）的容量。不同割的容量不同。12435642345412124352331st容量為：3+4=72、網(wǎng)絡(luò)流與割的關(guān)系：12435642345412124352331st網(wǎng)絡(luò)流量：51234割正逆161250350450割的流量如果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ò)流的特點(diǎn)：如果V既不是源點(diǎn)也不是匯點(diǎn)，那么：f({V},S∪T)-f(S∪T,{V})=0;任何一個(gè)點(diǎn)，流入的與流出的量相等。如果V是源，那么：f({V},S∪T)-f(S∪T,{V})=f對(duì)于S中的所有點(diǎn)V都有上述關(guān)系式，相加得到：f(S,S∪T)-f(S∪T,S)=f推論1：如果f是網(wǎng)絡(luò)中的一個(gè)流，CUT（S,T）是一個(gè)割，那么f的值不超過(guò)割CUT（S,T）的容量。f=f(S,T)-f(T,S)<=f(S,T)<=割CUT（S,T）的容量推論2：網(wǎng)絡(luò)中的最大流不超過(guò)任何割的容量定量2：在任何網(wǎng)絡(luò)中，如果f是一個(gè)流，CUT（S,T）是一個(gè)割，且f的值等于割CUT（S,T）的容量，那么f是一個(gè)最大流，CUT（S,T）是一個(gè)最小割（容量最小的割）。令割CUT（S,T）的容量為C，所以流f的流量也為C。假設(shè)另外的任意流f1，流量為c1，根據(jù)流量不超過(guò)割的容量，則c1<=c,所以f是最大流。假設(shè)另外的任意割CUT（S1,T1），容量為c1，根據(jù)流量不超過(guò)割的容量，所以有c1>=c,故，CUT（S,T）是最小割。證明：定量3：最大流最小割定量：在任何的網(wǎng)絡(luò)中，最大流的值等于最小割的容量。12435642345212124354234522211122最大流：7S={1,2,3},T={4,5}Cut(S,T)是最小割，容量＝３＋４＝７結(jié)論1：最大流時(shí)，最小割cut（S，T）中，正向割邊的流量=容量，逆向割邊的流量為0。否則還可以增廣。結(jié)論2：在最小割中cut（S，T）中：①源點(diǎn)s∈S。②如果i∈S，結(jié)點(diǎn)j滿足：有弧<i,j>,并且c[I,j]>f[I,j]或者有弧<j,i>并且f[j,i]>0,那么j∈S。//否則不是最小割即從s出發(fā)能找到的含有殘留的點(diǎn)組成集合S。其余的點(diǎn)組成集合T。怎樣求集合S？數(shù)組b[i]記錄增廣路徑上結(jié)點(diǎn)i的前驅(qū)結(jié)點(diǎn)。初始值b[]=-1，b[1]=0；假設(shè)1是源點(diǎn)。如果b[i]〉-1（有前驅(qū)，能從源點(diǎn)1找到的點(diǎn)），那么，i∈S。怎樣求正向割邊和逆向割邊？二、最大流最小割定量的應(yīng)用1、太空飛行計(jì)劃問(wèn)題【問(wèn)題描述：】W教授正在為國(guó)家航天中心計(jì)劃一系列的太空飛行。每次太空飛行可進(jìn)行一系列商業(yè)性實(shí)驗(yàn)而獲取利潤(rùn)?，F(xiàn)已確定了一個(gè)可供選擇的實(shí)驗(yàn)集合E={E1，E2，…，Em}，和進(jìn)行這些實(shí)驗(yàn)需要使用的全部?jī)x器的集合I={I1，I2，…In}。實(shí)驗(yàn)Ej需要用到的儀器是I的子集Rj。配置儀器Ik的費(fèi)用為ck美元。實(shí)驗(yàn)Ej的贊助商已同意為該實(shí)驗(yàn)結(jié)果支付pj美元。W教授的任務(wù)是找出一個(gè)有效算法，確定在一次太空飛行中要進(jìn)行哪些實(shí)驗(yàn)并因此而配置哪些儀器才能使太空飛行的凈收益最大。這里凈收益是指進(jìn)行實(shí)驗(yàn)所獲得的全部收入與配置儀器的全部費(fèi)用的差額。對(duì)于給定的實(shí)驗(yàn)和儀器配置情況，編程找出凈收益最大的試驗(yàn)計(jì)劃。第1行有2個(gè)正整數(shù)m和n。m是實(shí)驗(yàn)數(shù)，n是儀器數(shù)。接下來(lái)的m行，每行是一個(gè)實(shí)驗(yàn)的有關(guān)數(shù)據(jù)。第一個(gè)數(shù)贊助商同意支付該實(shí)驗(yàn)的費(fèi)用；接著是該實(shí)驗(yàn)需要用到的若干儀器的編號(hào)。最后一行的n個(gè)數(shù)是配置每個(gè)儀器的費(fèi)用。第1行是實(shí)驗(yàn)編號(hào)；第2行是儀器編號(hào)；最后一行是凈收益?！据斎耄骸俊据敵?】【樣例輸入:】2310122523567【樣例輸出:】1212317分析得出：任意一種實(shí)驗(yàn)方案所做的實(shí)驗(yàn)以及所需的儀器以及t構(gòu)成集合T，剩下的不做的實(shí)驗(yàn)以及不需要的儀器和s構(gòu)成集合S。T和S正好對(duì)應(yīng)與圖的一個(gè)割。StI1I2I3E1E25671025儀器實(shí)驗(yàn)∞∞∞∞如做實(shí)驗(yàn)E2：需要儀器I2和I3，與t組成集合T。S與不做的實(shí)驗(yàn)E1和沒(méi)用的儀器I1組成集合S。構(gòu)成割：CUT(S,T)凈收益：

E2:25-（6+7）=12同理:E1：10-（5+6）=-1E1+E2：（10+25）-（5+6+7）=17123123ts265394做實(shí)驗(yàn)1：凈收益：2-6=-4做實(shí)驗(yàn)1，2：凈收益：（2+5）-（6+3）=-2做實(shí)驗(yàn)2，3：凈收益：（5+9）-（3+4）=7=(2+5+9)-(5+9)-6=(2+5+9)-(5+9+6)=(2+5+9)-9-(6+3)=(2+5+9)-(9+6+3)=(2+5+9)-2-(3+4)=(2+5+9)-(2+3+4)StI1I2I3E1E25671025儀器實(shí)驗(yàn)∞∞∞∞最大凈收益：（10+25）-（5+6+7）=17123123ts265394最大凈收益：(2+5+9)–(2+3+4)=16–最大流9=7做實(shí)驗(yàn)2和3實(shí)驗(yàn)儀器和實(shí)驗(yàn)的輸出：構(gòu)造圖時(shí)要重新編號(hào)123123ts265394儀器：1-3中b[i]=-1的點(diǎn)。實(shí)驗(yàn)：4-6中b[j]=-1的點(diǎn)。割邊：如果存在弧<i,j>，滿足：i∈S,b[i]>=0,j∈T,b[j]=-1,那么弧<i,j>是一條割邊分析：令di=bi-ai，凈收益。A={i|di>=0}:可以獲得利潤(rùn)的項(xiàng)目集合。B={i|di<0}：虧損的項(xiàng)目集合。構(gòu)造網(wǎng)絡(luò)圖：G=（V，E，C）。1、兩類頂點(diǎn)：N+2個(gè)點(diǎn)：源點(diǎn)s個(gè)匯點(diǎn)