1、網(wǎng)絡的最大流,如何制定一個運輸計劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個網(wǎng)絡最大流問題。,網(wǎng)絡的最大流,基本概念： 1. 容量網(wǎng)絡：隊網(wǎng)絡上的每條弧(vi,vj)都給出一個最大的通過能力，稱為該弧的容量，簡記為cij。容量網(wǎng)絡中通常規(guī)定一個發(fā)點(也稱源點，記為s)和一個收點(也稱匯點，記為t)，網(wǎng)絡中其他點稱為中間點。,s,t,4,8,4,4,1,2,2,6,7,9,網(wǎng)絡的最大流,2. 網(wǎng)絡的最大流 是指網(wǎng)絡中從發(fā)點到收點之間允許通過的最大流量。,3. 流與可行流 流是指加在網(wǎng)絡各條弧上的實際流量，對加在弧(vi,vj)上的負載量記為fij。若fij=0，稱為零流。 滿足以下條件的一組流

2、稱為可行流。,容量限制條件。容量網(wǎng)絡上所有的弧滿足：0fijcij 中間點平衡條件。,若以v(f)表示網(wǎng)絡中從st的流量，則有：,網(wǎng)絡的最大流,結(jié)論：任何網(wǎng)絡上一定存在可行流。（零流即是可行流）,網(wǎng)絡最大流問題： 指滿足容量限制條件和中間點平衡的條件下，使v(f)值達到最大。,網(wǎng)絡的最大流,割與割集,割是指容量網(wǎng)絡中的發(fā)點和收點分割開，并使st的流中斷的一組弧的集合。割容量是組成割集合中的各條弧的容量之和，用 表示。,如下圖中，AA將網(wǎng)絡上的點分割成 兩個集合。并有 ，稱弧的集合(v1,v3),(v2,v4)是一個割，且 的流量為18。,網(wǎng)絡的最大流,s,t,v1,v3,v2,v4,8(8),

3、9(5),5(5),10(9),6(0),2(0),9(9),5(3),7(6),A,A,B,B,網(wǎng)絡的最大流,定理1 設網(wǎng)絡N中一個從 s 到 t 的流 f 的流量為v(f )， (V, V)為任意一個割集，則 v(f ) = f(V, V) f(V, V),推論1 對網(wǎng)絡 N中任意流量v(f )和割集 (V, V)，有 v(f ) c(V, V),證明 w= f(V, V) f(V, V) f(V, V) c(V, V),推論2 最大流量v (f )不大于最小割集的容量，即： v (f ) minc(V, V),定理2 在網(wǎng)絡中st的最大流量等于它的最小割集的容量， 即： v (f ) =

4、 c (V, V),網(wǎng)絡的最大流,增廣鏈 在網(wǎng)絡的發(fā)點和收點之間能找到一條鏈，在該鏈上所有指向為st的弧，稱為前向弧，記作+,存在f0，則稱這樣的鏈為增廣鏈。例如下圖中，sv2v1v3v4t。,定理3 網(wǎng)絡N中的流 f 是最大流當且僅當N中不包含任何增廣鏈,網(wǎng)絡的最大流,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(4),7(5),網(wǎng)絡的最大流,求網(wǎng)絡最大流的標號算法： 基本思想 由一個流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個增流過程，直至不存在增廣鏈。,基本方法,找出第一個可行流，（例如所有弧的流量fij =0。） 用

5、標號的方法找一條增廣鏈,首先給發(fā)點s標號(),標號中的數(shù)字表示允許的最大調(diào)整量。 選擇一個點 vi 已標號并且另一端未標號的弧沿著某條鏈向收點檢查：,網(wǎng)絡的最大流,如果弧的起點為vi，并且有fij0，則vj標號(fji),(3) 重復第(2)步，可能出現(xiàn)兩種結(jié)局：,標號過程中斷，t無法標號，說明網(wǎng)絡中不存在增廣鏈，目前流量為最大流。同時可以確定最小割集，記已標號的點集為V,未標號的點集合為V,(V,V)為網(wǎng)絡的最小割。 t得到標號，反向追蹤在網(wǎng)絡中找到一條從s到t得由標號點及相應的弧連接而成的增廣鏈。繼續(xù)第(4)步,網(wǎng)絡的最大流,(4) 修改流量。設原圖可行流為f，令,得到網(wǎng)絡上一個新的可行流

6、f。,(5) 擦除圖上所有標號，重復(1)-(4)步，直到圖中找不到任何增廣鏈，計算結(jié)束。,網(wǎng)絡的最大流,例6.10 用標號算法求下圖中st的最大流量，并找出最小割。,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),網(wǎng)絡的最大流,解：(1) 先給s標號(),s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(),網(wǎng)絡的最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5)

7、,(),(2) 檢查與s點相鄰的未標號的點，因fs1cs1，故對v1標號=min, cs1-fs1=1,(1),網(wǎng)絡的最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(6),(),(1),(2) 檢查與v1點相鄰的未標號的點，因f13c13，故對v3標號=min1, c13-f13= min1, 6= 1,(1),網(wǎng)絡的最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(),(1),(1),(3) 檢查與v3點相鄰的未標號的點，因f3tc

8、3t，故對vt標號=min1, c3t-f3t= min1, 1= 1,(1),找到一條增廣鏈sv1v3t,網(wǎng)絡的最大流,(4) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(3),7(5),(),(1),(1),(1),網(wǎng)絡的最大流,(5) 擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(0),2(0),9(9),5(3),7(5),(),(1),(1),(1),網(wǎng)絡的最大流,(5) 擦除所

9、有標號，重復上述標號過程，尋找另外的增廣鏈。,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(3),7(5),(),(2),(2)=min,2=2,(2),(1)=min2,3=2,(3)=min2,5=2,(2),(1),(4)=min2,1=1,(1),(t)=min1,2=1,網(wǎng)絡的最大流,(6) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(3),7(5),(),(2),(2),(2),(1),(1),網(wǎng)絡

10、的最大流,s,t,v1,v3,v2,v4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(2),7(6),(),(2),(2),(2),(1),(1),(7) 擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。,網(wǎng)絡的最大流,s,t,v1,v3,v2,v4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(2),7(6),(),(1),(1),(1),(7) 擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。,(2)=min,1=1,(1)=min1,2=1,(3)=min1,4=1,網(wǎng)絡的最大流,例6.9 求下圖st的最大流，并找出最小割

11、,網(wǎng)絡的最大流,解: (1) 在已知可行流的基礎上，通過標號尋找增廣鏈。,(),(2)=min,6=6,(6),(3)=min6,2=2,(2),(t)=min2,5=2,(2),存在增廣鏈sv2v3 t,網(wǎng)絡的最大流,(2) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。,(),(6),(2),(2),網(wǎng)絡的最大流,(3) 擦除原標號，重新搜尋增廣鏈。,(),(6),(2),(2),網(wǎng)絡的最大流,(4) 重新搜尋增廣鏈。,(),(2)=min,4=4,(4),(1),(5)=min4,1=1,(3)=min1,2=1,(1),(1),(t)=min1,3=1,存在增廣鏈：sv2v

12、5v3 t,網(wǎng)絡的最大流,(5) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。,(),(4),(1),(1),(1),網(wǎng)絡的最大流,(6) 擦除原標號,(),(4),(1),(1),(1),網(wǎng)絡的最大流,(),(1),(1),(1),(5)=min,1=1,(5)=min1,1=1,(5)=min1,2=1,(7) 重新搜尋增廣鏈。,存在增廣鏈：sv5v3 t,網(wǎng)絡的最大流,(8) 調(diào)整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流,(),(1),(1),(1),網(wǎng)絡的最大流,(),(1),(1),(1),(9) 擦除原標號,網(wǎng)絡的最大流,(10) 重新標號，搜索增廣鏈,(),(1)=min,1=1,(1),(5)=min1,1=1,(1),(4)=min1,1=1,(1),(t)=min1,1=1,(1),存在增廣鏈：sv1v5v4t,網(wǎng)絡的最大流,(),(1),(1)