最大流 最小割.ppt

《最大流 最小割.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、最大流最小割定理割的定義割是網(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,2,3},T={4,5}構(gòu)成一個(gè)割。框外是容量，框內(nèi)是流量s-t圖1.一個(gè)源點(diǎn)和一個(gè)匯點(diǎn)2.有向邊，是從i到j(luò)的3.每一條邊都有一個(gè)非負(fù)的權(quán)值4.容量cap(i,j)等于零，說明不存在邊s-t切割的代價(jià)1.S,T的容量是所有容量函數(shù)的總和2.最小割是S-T切割中所有可能的S-T切割的能量最小的割跨越S-T切割的流值是所有f(i,j)-f(j,i)的值注意：源點(diǎn)和匯點(diǎn)不能屬于同一個(gè)頂點(diǎn)集合。頂點(diǎn)集S={1,3,5}和T

2、={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的割邊是逆向割邊。割CUT（S,T）中所有正向割邊的容量和，稱為割CUT（S,T）的容量。不同割的容量不同。最小割，就是指所有割中權(quán)重之和最小的一個(gè)割。網(wǎng)絡(luò)流和割的關(guān)系定理一：如果f是網(wǎng)絡(luò)中的一個(gè)流，CUT(S,T)是任意一個(gè)割，那么f的值等于正向割邊的流量與負(fù)向割邊的流量之差。推論一：如果f是網(wǎng)絡(luò)中的一個(gè)流，CUT(S,T)是一個(gè)割，那么f的值不超過割CUT(S,T)的容量。推論二：網(wǎng)絡(luò)中的最大流不超過任何割的容量。定理

3、二：在網(wǎng)絡(luò)中，如果f是一個(gè)流，CUT(S,T)是一個(gè)割，且f的值等于割CUT(S,T)的容量，那么f是一個(gè)最大流，CUT(S,T)是一個(gè)最小割。最大流最小割定理在任何網(wǎng)絡(luò)中，最大流的值等于最小割的容量。結(jié)論一：最大流時(shí)，最小割cut(S,T)中，正向割邊的流量=容量，逆向割邊的流量為0。結(jié)論二：在最小割cut(S,T)中:1.源點(diǎn)s屬于S2.如果i屬于S，結(jié)點(diǎn)j滿足：有弧,并且c[i,j]>f[i,j],或者有弧,并且f[i,j]>0,那么j屬于S。//否則不是最小割。即，從s出發(fā)能找到的含有殘留的點(diǎn)組成集合S，其余的點(diǎn)組成集合T。形象的比喻：水流管道的最大流量由最細(xì)的管子

4、容量決定。網(wǎng)絡(luò)的最大流量由最小割決定。