第六章圖與網(wǎng)絡(luò)分析2ppt課件

1、F1.圖的基本概念圖的基本概念F2.樹樹F3.最短路最短路F4.最大流問題最大流問題F5.最小費用最大流最小費用最大流F6.中國郵遞員問題中國郵遞員問題運籌學(xué)F問題提出問題提出F運用：生產(chǎn)組織，郵遞員問題，通訊網(wǎng)運用：生產(chǎn)組織，郵遞員問題，通訊網(wǎng)絡(luò)等。絡(luò)等。F哥尼斯堡七橋問題哥尼斯堡七橋問題運籌學(xué)ABCDF哥尼斯堡七橋問題哥尼斯堡七橋問題F在圖中找一條經(jīng)過每邊一次且僅一次的在圖中找一條經(jīng)過每邊一次且僅一次的路路歐拉回路。歐拉回路。ADBC由點和邊組成運籌學(xué)F“環(huán)球旅行環(huán)球旅行問題問題F在圖中找一條經(jīng)過每個點一次且僅一次在圖中找一條經(jīng)過每個點一次且僅一次的路的路哈密爾頓回路。哈密爾頓回路。F“中

2、國郵路問題中國郵路問題”F在圖中找一條經(jīng)過每邊的最短路在圖中找一條經(jīng)過每邊的最短路類類似帶權(quán)的歐拉回路。似帶權(quán)的歐拉回路。F“貨郎擔(dān)問題貨郎擔(dān)問題”F在圖中找一條經(jīng)過每個點一次且僅一次的最在圖中找一條經(jīng)過每個點一次且僅一次的最短路短路帶權(quán)的哈密爾頓回路。帶權(quán)的哈密爾頓回路。運籌學(xué) 例例 1: 鐵路交通圖鐵路交通圖 例例 2: 球隊比賽圖球隊比賽圖點點: 表示研究對象表示研究對象.連線：表示兩個對象之間的某種特定關(guān)系連線：表示兩個對象之間的某種特定關(guān)系。關(guān)系的對稱性：兩對象之間的關(guān)系可互換關(guān)系的對稱性：兩對象之間的關(guān)系可互換。運籌學(xué)F邊：不帶箭頭的聯(lián)線，表示對稱關(guān)系。邊：不帶箭頭的聯(lián)線，表示對稱

3、關(guān)系。F?。簬Ъ^的聯(lián)線，表示不對稱關(guān)系?；。簬Ъ^的聯(lián)線，表示不對稱關(guān)系。F無向圖：簡稱圖，有點和邊組成。無向圖：簡稱圖，有點和邊組成。F 表示為：表示為： G=（V，E）F V-點集合點集合 E-邊集合邊集合F例：右圖例：右圖V=v1，v2，v3，v4 E=e1，e2，,e7e1=v1,v2e2=v1,v2, ,e7=v4,v41v2v3v4v1e2e3e4e5e6e7e運籌學(xué)F 有向圖：由點和弧組成。表示為：有向圖：由點和弧組成。表示為：F D=（V，A）F V-點集合點集合 A-弧集合弧集合F點數(shù)點數(shù): p(G) 或或 p(D)F邊數(shù)邊數(shù): q(G)F弧數(shù)弧數(shù):q(D)v1v2v3v4

4、v5例：右圖V=v1，v2,v5A=a1，a2,a7a1=v1,v5,a2=v5,v4,a7=v1,v4運籌學(xué)F端點端點: e=u,vE, : e=u,vE, 則則u,vu,v是是e e的端點的端點, , 稱稱u,vu,v相鄰相鄰. .F關(guān)聯(lián)邊關(guān)聯(lián)邊: e: e是點是點u,vu,v的關(guān)聯(lián)邊的關(guān)聯(lián)邊. .F環(huán)環(huán): : 若若u=v, eu=v, e是環(huán)是環(huán). .F多重邊多重邊: : 兩點之間多于一條邊兩點之間多于一條邊. .F簡單圖簡單圖: : 無環(huán)無環(huán), ,無多重邊的圖無多重邊的圖. .F多重圖多重圖: : 無環(huán)無環(huán), ,允許有多重邊的圖允許有多重邊的圖. .運籌學(xué)1v2v3v4v1e2e3e4

5、e5e6e5vF次或度）次或度）: : 以點以點v v為端點的邊的個數(shù)稱為端點的邊的個數(shù)稱為為v v的次的次. . 表示為表示為: d(v): d(v)F懸掛點懸掛點: : 次為次為1 1的點的點. .F懸掛邊懸掛邊: : 懸掛點的關(guān)聯(lián)邊懸掛點的關(guān)聯(lián)邊. .F孤立點孤立點: : 次為次為0 0的點的點. .F奇點奇點: : 次為奇數(shù)的點次為奇數(shù)的點. .F偶點偶點: : 次為偶數(shù)的點次為偶數(shù)的點. .孤立點懸掛邊12( )3, ()3d vd v運籌學(xué)F定理1: 圖G=(V,E)中,所有點的次之和是邊數(shù)的兩倍, 即:F定理2: 任意一圖中, 奇點的個數(shù)為偶數(shù).F 證明:設(shè) V1-奇點的集合,F

6、 V2-偶點的集合qvdVv2)(qvdvdvdVvVvVv2)()()(21偶數(shù)偶數(shù)偶數(shù)運籌學(xué)F鏈：點邊交錯系列，鏈：點邊交錯系列， 記為：記為：F圈：圈： 的鏈。的鏈。 F初等鏈：點初等鏈：點 均不相同。均不相同。F初等圈：點初等圈：點 均不相同。均不相同。F簡單鏈：鏈中邊均不相同。簡單鏈：鏈中邊均不相同。F簡單圈：圈中邊均不相同。簡單圈：圈中邊均不相同。F例：右圖例：右圖 ),.,(1211kkkiiiiiivevvevkiivv1kiiivvv,.,21121,.,kiiivvv1v2v3v4v1e2e3e4e5e6e7e無重復(fù)點,無重復(fù)邊有重復(fù)點,無重復(fù)邊運籌學(xué)F連通圖：任意兩點之間

7、至少有一條鏈。連通圖：任意兩點之間至少有一條鏈。F不連通圖：不連通圖：F連通分圖：對不連通圖，每一連通的部連通分圖：對不連通圖，每一連通的部分稱為一個連通分圖。分稱為一個連通分圖。F支撐子圖：對支撐子圖：對G=（V，E），若），若G=(V,E), 使使V=V, E E, 則則G是是G的的一個支撐子圖生成子圖）一個支撐子圖生成子圖）.FG-v: 圖圖G去掉點去掉點v及及v的關(guān)聯(lián)邊的圖的關(guān)聯(lián)邊的圖.運籌學(xué)F基礎(chǔ)圖基礎(chǔ)圖: 對對D=(V, A), 去掉圖上的箭頭去掉圖上的箭頭.F始點和終點始點和終點: 對弧對弧a=(u,v), u為為a的始點的始點, v為為a的終點的終點.F鏈鏈: 點弧交錯序列點弧

8、交錯序列, 若在其基礎(chǔ)圖中對應(yīng)若在其基礎(chǔ)圖中對應(yīng)一條鏈一條鏈, 則稱為則稱為 D的一條鏈的一條鏈.F圈圈, 初等鏈初等鏈,初等圈初等圈: 類似定義類似定義.方向可以不同運籌學(xué)F道路道路:假設(shè)假設(shè) 是是D中的一條鏈，且中的一條鏈，且 ，t=1,2,k-1,稱之為從稱之為從 到到 的一條道路。的一條道路。F回路回路: 的路的路.F初等路初等路: 道路中點不相同道路中點不相同.F初等回路初等回路: 回路中點不相同回路中點不相同.F簡單有向圖簡單有向圖: 無自環(huán)無自環(huán), 無多重弧無多重弧.F多重有向圖多重有向圖: 有多重弧有多重弧.),.,1112211kkkiiiiiiivavavav（kiivv1

9、),(1tttiiivva1ivkiv方向相同運籌學(xué)F設(shè)圖設(shè)圖G=（V，E），其中），其中Fn階方陣階方陣 稱為的鄰接矩陣，其中稱為的鄰接矩陣，其中12,nVv vv()ijAa10ijaij或權(quán)值，若(v ,v ) E或 ，否則運籌學(xué)F歐拉圖：具有歐拉回路的圖F定理3 一個連通圖 為歐拉圖的充要條件是 的每一個結(jié)點的度均為偶數(shù)。F例如，哥尼斯堡七橋不存在一條歐拉回路，所以哥尼斯堡七橋問題的回答是否定的。GG運籌學(xué)F哈密頓回路：經(jīng)過圖的每個結(jié)點一次且哈密頓回路：經(jīng)過圖的每個結(jié)點一次且僅一次的回路。僅一次的回路。F類似于確定哈密頓回路的問題是流動售類似于確定哈密頓回路的問題是流動售貨員的問題，流

10、動售貨員要從公司出發(fā)貨員的問題，流動售貨員要從公司出發(fā)走銷附近的所有城鎮(zhèn)，然后返回所在地走銷附近的所有城鎮(zhèn)，然后返回所在地，那么如何安排他的路線，使得旅行的，那么如何安排他的路線，使得旅行的總距離最小?？偩嚯x最小。運籌學(xué)F2.1 樹及其性質(zhì)樹及其性質(zhì)F2.2 圖的支撐樹生成樹）圖的支撐樹生成樹）F2.3最小支撐樹問題最小支撐樹問題F2.4 根樹及其應(yīng)用根樹及其應(yīng)用運籌學(xué)例例: 電話線架設(shè)、比賽程序、組織結(jié)構(gòu)等。電話線架設(shè)、比賽程序、組織結(jié)構(gòu)等。 樹樹:連通的無圈的無向圖稱為樹。連通的無圈的無向圖稱為樹。運籌學(xué) 圖圖G=G=（V V，E E），），p p個點、個點、q q條邊下列說法是等價的條邊

11、下列說法是等價的（1 1G G是一個樹是一個樹（2 2G G連通，且恰有連通，且恰有p-1p-1條邊。條邊。（3 3G G無圈，且恰有無圈，且恰有p-1p-1條邊。條邊。（4 4G G連通，但每舍去一邊就不連通。連通，但每舍去一邊就不連通。（5 5G G無圈，但每增加一邊即得唯一一個圈。無圈，但每增加一邊即得唯一一個圈。 （6 6G G中任意兩點之間恰有一條鏈中任意兩點之間恰有一條鏈( (簡單鏈簡單鏈) )。運籌學(xué)F定義定義: :設(shè)圖設(shè)圖T=(VT=(V，E) E) 是圖是圖G=(V,E)G=(V,E)的支的支撐子圖撐子圖, ,如果如果T T是一個樹是一個樹, , 則稱則稱T T是是G G的一

12、的一個支撐樹。個支撐樹。F定理定理5 5：圖：圖G=G=（V V，E E有支撐樹的充分必有支撐樹的充分必要條件是要條件是G G是連通的。是連通的。運籌學(xué)F求支撐樹的破圈法求支撐樹的破圈法運籌學(xué)F求支撐樹的避圈法求支撐樹的避圈法深探法廣探法運籌學(xué)F賦權(quán)圖賦權(quán)圖( (網(wǎng)絡(luò)）網(wǎng)絡(luò)）: : 給圖給圖G=(V,E), G=(V,E), 對對G G中的中的每一條邊每一條邊vi,vj, vi,vj, 相應(yīng)地有一個數(shù)相應(yīng)地有一個數(shù)wij, wij, 則稱這樣的圖為賦權(quán)圖則稱這樣的圖為賦權(quán)圖, wij , wij 稱為邊稱為邊vi,vjvi,vj上的權(quán)上的權(quán). .F支撐樹的權(quán)支撐樹的權(quán): :若若T=(V,E)

13、T=(V,E) 是是G G的一個支撐的一個支撐樹樹, E, E中的所有邊的權(quán)之和稱為支撐樹中的所有邊的權(quán)之和稱為支撐樹的權(quán)的權(quán), , 記為記為w(T):w(T):TvvijjiwTw,)(運籌學(xué)F定義定義: : 最小支撐樹最小支撐樹( (最小樹最小樹)T)T* *: :F求最小樹的求最小樹的 避圈法避圈法: : 例例: : 圖圖8-278-27F求最小樹的求最小樹的 破圈法破圈法: : 例例: : 圖圖8-28 8-28 )()(min*TwTwT運籌學(xué)有向樹中根樹有向樹中根樹在計算機科學(xué)、決策論的應(yīng)用在計算機科學(xué)、決策論的應(yīng)用F有向樹：有向樹：F根樹：有向樹根樹：有向樹T，恰有一個結(jié)，恰有一

14、個結(jié)點入次為點入次為0，其余各點入次為，其余各點入次為1，則稱，則稱T為根樹。為根樹。FM叉樹：叉樹：F二叉樹：結(jié)點的出度都小于二叉樹：結(jié)點的出度都小于等于等于2。根葉分點枝第一層第三層第二層三叉樹運籌學(xué)F帶權(quán)的二叉樹帶權(quán)的二叉樹T：有：有s個葉子，權(quán)分別為個葉子，權(quán)分別為pi，F(xiàn)根到各葉子的距離層次為根到各葉子的距離層次為F二叉樹的總權(quán)數(shù)二叉樹的總權(quán)數(shù)F最優(yōu)二叉樹（最優(yōu)二叉樹（ Huffman樹）：總權(quán)數(shù)最小的二叉樹樹）：總權(quán)數(shù)最小的二叉樹F算法步驟：算法步驟：Huffman算法算法F將將s個葉子按權(quán)由小到大排列，個葉子按權(quán)由小到大排列，F(xiàn)將兩個最小的葉子合并為一個分枝點，其權(quán)為兩者將兩個最

15、小的葉子合并為一個分枝點，其權(quán)為兩者之和，將新的分枝點作為一個葉子，轉(zhuǎn)上一步，直之和，將新的分枝點作為一個葉子，轉(zhuǎn)上一步，直到結(jié)束。到結(jié)束。), 2 , 1( ,silisiiilpTm1)(運籌學(xué)F例例1、s=6，其權(quán)分別為，其權(quán)分別為4，3，2，2，1，求最優(yōu)二叉樹。求最優(yōu)二叉樹。123243365運籌學(xué)F例例1、s=6，其權(quán)分別為，其權(quán)分別為4，3，2，2，1，求最優(yōu)二叉樹。求最優(yōu)二叉樹。123243396515123243396515運籌學(xué)F例例2、最優(yōu)檢索問題。、最優(yōu)檢索問題。F 使用計算機進行圖書分使用計算機進行圖書分 類。現(xiàn)有五類類?，F(xiàn)有五類圖書共圖書共100萬冊，其中有萬冊，其

16、中有A類類50萬冊，有萬冊，有B類類20萬冊，萬冊，C類類5萬冊，萬冊，D類類10萬冊，萬冊，E類類15萬冊，問如何安排分檢過程，可使總?cè)f冊，問如何安排分檢過程，可使總的運算比較次數(shù)最??？的運算比較次數(shù)最??？運籌學(xué)F例例3：P235、例、例110.050.450.050.080.120.25一等品一等品五等品五等品四等品四等品三等品三等品二等品二等品等外品等外品0.100.300.180.551.0測試順序運籌學(xué)3.1 引例引例單行線交通網(wǎng)：單行線交通網(wǎng)：v1到到v8使總費用最小的旅行使總費用最小的旅行路線。路線。最短路問題的一般描述：最短路問題的一般描述： 對對D=（V，A），）， a=（v

17、i，vj），），wa）=wij，P是是vs到到vt的路，定義路的路，定義路P的權(quán)的權(quán)是是P中所有弧的權(quán)的和，記為中所有弧的權(quán)的和，記為wP）運籌學(xué)F路路P0的權(quán)稱為從的權(quán)稱為從vs到到vt的距離，記為：的距離，記為：Fd（ vs，vt ）F3.2最短路算法最短路算法FDijkstra算法算法 ：有向圖：有向圖 ，wij0F一般結(jié)論一般結(jié)論)()(min0PwPwP 的最短路到的最短路到isjsvvisvvjisvvvvv,.,.,.,則最短路問題為：則最短路問題為：運籌學(xué)Dijkstra算法基本思想P標(biāo)號：已確定出最短路的節(jié)點的距離。T標(biāo)號：為確定出最短路的節(jié)點，但表示其距離的上限。Si：P標(biāo)

18、號節(jié)點的集合。(v)：最短路中前一個節(jié)點的編號。初始值： () () ()0sssTvvvvsvvv 運籌學(xué)例:011122330 1 ()0 ()0 () ()1 () ()1 . . iSvkP vvT vvT vv 99 () ()1T vv 運籌學(xué) 12112222131133331411444( ,):()066() ()6 ()1 ( ,):()033() ()3 ()1 ( ,):()011() ()v vP vwT vT vvv vP vwT vT vvv vP vwT vT v423456789411441 ()1min (),(),(),(),(), (),(),()()

19、1 , ()1 4vT vT vT vT vT vT vT vT vT viSv vP vk運籌學(xué) 3 3)( , 2 )()(),( ),(),(),(),(),( min4)( 11)( )(11101)(: ),(334123987653266646464kvPvvvSivTvTvTvTvTvTvTvTvvTvTwvPvv運籌學(xué) 2 5)( , 3 )()(),(),( ),(),(),( min3)( 5)( 6)(523)(: ),(223413298765222232323kvPvvvvSivTvTvTvTvTvTvTvvTvTwvPvv運籌學(xué) 252255555678954143

20、255(,):()5 16() ()6 ()2min (), (), (), (), ()() 4 , ()6 5v vP vwT vT vvT vT vT vT vT vT viSv v v v vP vk 運籌學(xué) 7 9)( , 5 )()(),(),( ),(min5)( 12)( )(1266)(: ),( 5)( 9)( )(936)(: ),( 5)( 10)( )(1046)(: ),(77523415798768845858577757575610656565kvPvvvvvvSivTvTvTvTvTvvTvTwvPvvvvTvTwvPvvvvTvTwvPvv運籌學(xué) 78778

21、88856896614325766( ,): ( )9 413( )12 ( ) =12 ( )min ( ), ( ), ( )( ) 6 , , , ( )10 6v vP vwT vT vvvT vT vT vT viSv v v v v v vP vk 運籌學(xué) 6689871432576888899,min (),()() 7 , ()12 8,min() () . vST vT vT viSvvvvvvvvP vkvST vT v 無 指 向 不 屬 于的 點 轉(zhuǎn) 向 無 指 向 不 屬 于的 點 轉(zhuǎn) 向 算 法 終 止運籌學(xué)總結(jié): 算法步驟:MvvTvvPvvPvvPvvPvvPv

22、vPvvPvvP)( )(5)( 12)(5)( 9)(5)( 10)(2)( 6)(1)( 1)(1)( 3)(3)( 5)(0)( 0)(998877665544332211運籌學(xué)FDijkstra算法算法 ：無向圖求最短鏈，：無向圖求最短鏈，wij0F存在負(fù)權(quán)時求最短路問題存在負(fù)權(quán)時求最短路問題 ),(: ),(:jijjkjijjkvSvEvvvSvAvv的點且考察修改為的點且考察算法修改運籌學(xué)4.1基本概念和基本定理基本概念和基本定理網(wǎng)絡(luò)與流網(wǎng)絡(luò)與流定義定義: 對有向圖對有向圖D=(V,A):vs 源源 vt 匯匯 其他其他 - 中間點中間點c(vi,vj) - 弧弧(vi,vj)的

23、容量的容量, 簡寫為簡寫為cijD=(V,A,C) - 網(wǎng)絡(luò)網(wǎng)絡(luò) fij - 弧弧(vi,vj)上的流量上的流量運籌學(xué)運籌學(xué)F可行流與最大流可行流與最大流F可行流滿足可行流滿足:稱為可行流的流量有對有對有對平衡條件（對容量限制條件)()( :)( :0:,:)20 ),:) 1),(),(),(),(),(),(fvfvffvfvffvfftsivcfAvvAvvjtAvvtjtAvvjsAvvsjsAvvjiAvvijiijijjitjjtsjjsijji流入量=流出量流出量流入量運籌學(xué)最大流問題tifvfftsiffsifvffAvvcffvAvvjtAvvtjAvvjiAvvijAvvj

24、sAvvsjjiijijtjjtijjisjjs )(, 0 )( ),( 0)(max),(),(),(),(),(),(運籌學(xué)F增廣鏈增廣鏈: F幾個概念幾個概念: 對可行流對可行流F例例:圖圖10-23其全體記為后向弧反弧的方向與鏈的方向相其全體記為前向弧致弧的方向與鏈的方向一網(wǎng)絡(luò)中的一條鏈非零流弧零流弧非飽和弧飽和弧- ),.,( 0 0 tsijijijijijijvvffcfcfijff 運籌學(xué)增廣鏈: 設(shè)f是一可行流, 時從始點到終點的一條鏈, 若滿足下列條件,稱其為一條增廣鏈.例: 圖10-24截集和截量設(shè) 把始點在S,終點在T中的所有弧構(gòu)成的集合, 記為(S,T).非零流弧對

25、后向弧非飽和弧對前向弧ijijijijcfcf0:0:TSVTS,可增加流量的鏈運籌學(xué)F定義定義: 截集截集F定義定義: 截量截量 .),(,),( _11_11_11稱為截集則把弧集且和被分為兩個非空集合若對網(wǎng)絡(luò)VVVvVvVVVCAVDts),(),(_11_11_11_11),( :),(,),( VVvvijjicVVcVVcVV即記為簡稱截量集的容量為截中所有弧的容量之和稱把截集運籌學(xué)F幾點結(jié)論幾點結(jié)論最小截集容量最大流量最大流量最小截集定理的增廣鏈不存在關(guān)于是最大流可行流 : ) 3 2),()( ) 1*_11ffVVcfv運籌學(xué)F網(wǎng)絡(luò)中的點分為網(wǎng)絡(luò)中的點分為:F標(biāo)號點標(biāo)號點F標(biāo)

26、號未檢查點標(biāo)號未檢查點F標(biāo)號已檢查點標(biāo)號已檢查點F未標(biāo)號點未標(biāo)號點運籌學(xué)F1) 標(biāo)號過程標(biāo)號過程., .,),(min)( :),(,( 0,),(),(min)( :),(,( ,),()(,), 0( 停止則已得到最大流沒有得到標(biāo)號若進入調(diào)整過程已找到一條增廣鏈已標(biāo)號若其中標(biāo)號給非零流弧后向弧對其中標(biāo)號給非飽和弧若前向弧對標(biāo)號未檢查點對一般地標(biāo)上給ttjiijjijjiijijijijjijijijjiisvvfvlvlvlvvfvvfcvlvlvlvvcfvvvv運籌學(xué)F 2) 調(diào)整過程調(diào)整過程: 沿增廣鏈調(diào)整流量沿增廣鏈調(diào)整流量.F例例: 圖圖10-25運籌學(xué)F定義定義: 對對D=(V

27、,A,C), 給定一個單位流量給定一個單位流量的費用的費用bij0, 最小費用最大流即最小費用最大流即:求一最求一最大流大流f, 使使F 對增廣鏈對增廣鏈, 若調(diào)整流量若調(diào)整流量=1, 那么新可行那么新可行流流f的費用比原可行流的費用比原可行流f的費用增加的費用增加:Avvijijjifbfb),()(min運籌學(xué)F此為增廣鏈此為增廣鏈的費用的費用.F最小費用最大流的求解最小費用最大流的求解F構(gòu)造賦權(quán)有向圖構(gòu)造賦權(quán)有向圖w(f), 定義定義:ijijbbfbfb)()(0 0 ijijijjiijijijijijijffbwcfcfbw運籌學(xué)在w(f)中找最小費用增廣鏈, 直至沒有最小費用增廣

28、鏈為止.若存在最小費用增廣鏈, 調(diào)整流量如下: ),( ),( ),( )(min),(minmin)1()1()1()1()1(jikijjikijjikijkijkijkijijvvfvvfvvffffc運籌學(xué)初初始始網(wǎng)網(wǎng)絡(luò)絡(luò)數(shù)數(shù)值值VsV1 V2 V3 Vt 運籌學(xué)(4,10)(1, 8)(2, 4)(1, 7)(2, 5)(6, 2)(4,10)bij Cij初初始始網(wǎng)網(wǎng)絡(luò)絡(luò)數(shù)數(shù)值值VsV1 V2 V3 Vt 運籌學(xué)取初始取初始可行流可行流f (0) =0V1 V2 V3 Vs Vt 運籌學(xué)(4,0)(1, 0)(2, 0)(1, 0)(2, 0)(6, 0)(4,0)取初始取初始可行

29、流可行流f (0) =0V1 V2 V3 Vs Vt bij fij運籌學(xué)(4,0)(1, 0)(2, 0)(1, 0)(2, 0)(6, 0)(4,0)取初始取初始可行流可行流f (0) =0構(gòu)造賦構(gòu)造賦權(quán)圖權(quán)圖W(f (0)V1 V2 V3 Vs Vt 0 0 ijijijjiijijijijijijffbwcfcfbw運籌學(xué)(4,0)(1, 0)(2, 0)(1, 0)(2, 0)(6, 0)(4,0)取初始取初始可行流可行流f (0) =0構(gòu)造賦構(gòu)造賦權(quán)圖權(quán)圖W(f (0)V1 V2 V3 Vs Vt 運籌學(xué)(4,0)(1, 0)(2, 0)(1, 0)(2, 0)(6, 0)(4,0

30、)取初始取初始可行流可行流f (0) =0構(gòu)造賦構(gòu)造賦權(quán)圖權(quán)圖W(f (0)( +, 0 )V1 V2 V3 Vs Vt 運籌學(xué)(4,0)(1, 0)(2, 0)(1, 0)(2, 0)(6, 0)(4,0)在初始在初始賦權(quán)圖賦權(quán)圖W(f (0)上求出上求出最短路最短路V1 V2 V3 Vs Vt 運籌學(xué)(4,0)(1, 5)(2, 0)(1,5)(2, 5)(6, 0)(4,0)在最短在最短路上增路上增加流量加流量V1 V2 V3 Vs Vt ),( ),( ),( )(min),(minmin)0()0()0()1()0()0(jiijjiijjiijijijijijvvfvvfvvfff

31、fc運籌學(xué)(4,0)(2, 0)(6, 0)(4,0)在最短在最短路上增路上增加流量加流量原流量原流量如圖所如圖所示示V1 V2 V3 Vs Vt (1, 0)(1, 0)(2, 0)運籌學(xué)(4,0)(2, 0)(6, 0)(4,0)求求增增加加的的流流量量V1 V2 V3 Vs Vt 8 - 0 5 - 0 7 - 0最小最小f (0) (1, 0)(1, 0)(2, 0)運籌學(xué)(4,0)(1, 5)(2, 0)(1,5)(2, 5)(6, 0)(4,0)在最短在最短路上增路上增加流量加流量 = 5得到新得到新的流量的流量f (1)=5V1 V2 V3 Vs Vt 運籌學(xué)(4,0)(1, 5

32、)(2, 0)(1,5) (2, 5)(6, 0)(4,0)依據(jù)新依據(jù)新的流量的流量構(gòu)造又構(gòu)造又一賦權(quán)一賦權(quán)圖圖W(f (1)*只對只對增廣鏈增廣鏈V1 V2 V3 Vs Vt 80 0 ijijijjiijijijijijijffbwcfcfbw運籌學(xué)(4,0)(2, 0)(1,5) (2, 5)(6, 0)(4,0)賦賦權(quán)權(quán)圖圖W(f (1)的構(gòu)造的構(gòu)造*只對只對增廣鏈增廣鏈V1 V2 V3 Vs Vt 8(-1, 5)(1, 5)運籌學(xué)(4,0)(2, 0)(1,5)(2, 5)(6, 0)(4,0)賦賦權(quán)權(quán)圖圖W(f (1)的構(gòu)造的構(gòu)造*只對只對增廣鏈增廣鏈V1 V2 V3 Vs Vt

33、 8 5(-1, 5)(1, 5)0 0 ijijijjiijijijijijijffbwcfcfbw運籌學(xué)(4,0)(2, 0)(1,5)(6, 0)(4,0)賦賦權(quán)權(quán)圖圖W(f (1)的構(gòu)造的構(gòu)造*只對只對增廣鏈增廣鏈V1 V2 V3 Vs Vt 8 5(-2, 5) 7(-1,5)(-1, 5)(1, 5)運籌學(xué)(4,0)(2, 0)(1,5)(6, 0)(4,0)構(gòu)造的構(gòu)造的賦權(quán)賦權(quán)圖圖W(f (1)*只對只對增廣鏈增廣鏈V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-1, 5)(1, 5)運籌學(xué)(4,0)(2, 0)(1,5)(6, 0)(4,0)在賦在賦權(quán)圖權(quán)圖W(f

34、(1)上求出上求出最短路最短路V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-1, 5)(1, 5)運籌學(xué)Vs (4,0)(1, 5)(2, 0)(1,5)(2, 5)(6, 0)(4,0)在最短在最短路上增路上增加流量加流量V1 V2 V3 Vs Vt 7 - 5 = 2 10 - 0 最小最小運籌學(xué)Vs (4,2)(1, 5)(2, 0)(1,7)(2, 5)(6, 0)(4,0) = 2得到新得到新的流量的流量f (2)=7新的流新的流量圖如量圖如圖所示圖所示V1 V2 V3 Vs Vt 運籌學(xué)依據(jù)新依據(jù)新的流量的流量構(gòu)造又構(gòu)造又一賦權(quán)一賦權(quán)圖圖W(f (2)*只對只對增廣鏈

35、增廣鏈V1 (4,0)(1, 5)(2, 0)(1,5)(6, 0)(4,0)V1 V2 V3 Vs Vt (-1, 5)(-2, 5)(-1,5)運籌學(xué)對最短對最短路上求路上求新的權(quán)新的權(quán)值值V1 (4,2)(1, 5)(2, 0)(1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-1, 5)(-2, 5) 100 0 ijijijjiijijijijijijffbwcfcfbw運籌學(xué)賦賦權(quán)權(quán)圖圖的構(gòu)造的構(gòu)造W(f (2)*只對只對增廣鏈增廣鏈V1 (4,2)(1, 5)(2, 0)(1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-1, 5)(-2, 5)(-4

36、,2)0 0 ijijijjiijijijijijijffbwcfcfbw運籌學(xué)賦賦權(quán)權(quán)圖圖的構(gòu)造的構(gòu)造W(f (2)*只對只對增廣鏈增廣鏈V1 (4,2)(-1, 5)(2, 0)(1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (1, 5)(-2, 5) 7(-4,2)0 0 ijijijjiijijijijijijffbwcfcfbw運籌學(xué)賦賦權(quán)權(quán)圖圖的構(gòu)造的構(gòu)造W(f (2)*只對只對增廣鏈增廣鏈V1 (4,2)(2, 0)(-1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-2, 5)(-4,2)(-1, 5)(1, 5)運籌學(xué)新新賦賦權(quán)權(quán)圖圖W(f (2)

37、*只對只對增廣鏈增廣鏈V1 (4,2)(2, 0)(-1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-2, 5)(-4,2)(-1, 5)(1, 5)運籌學(xué)在賦在賦權(quán)圖權(quán)圖W(f (2)上求出上求出最短路最短路V1 (4,2)(2, 0)(-1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-2, 5)(-4,2)(-1, 5)(1, 5)運籌學(xué)(4,2)(1, 5)(2, 0)(1,7)(2, 5)(6, 0)(4,0)在最短在最短路上增路上增加流量加流量 = 3V1 V2 V3 Vt 8 - 5 = 3 最小最小 10 - 0 4 - 0運籌學(xué)(4,2)(1,

38、8)(2, 3)(1,7)(2, 5)(6, 0)(4,3)在最短在最短路上增路上增加流量加流量 = 3得到新得到新的流量的流量f (3)=10V1 V2 V3 Vt 運籌學(xué)依據(jù)新依據(jù)新的流量的流量構(gòu)造又構(gòu)造又一賦權(quán)一賦權(quán)圖圖W(f (3)*只對只對增廣鏈增廣鏈V1 (4,2)(2, 3)(-1,7)(6, 0)(4,3)V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-4,2)(1, 8) 8 10 4運籌學(xué)賦賦權(quán)權(quán)圖圖W(f (3)的構(gòu)造的構(gòu)造*只對只對增廣鏈增廣鏈V1 (4,2)(2, 3)(-1,7)(6, 0)(4,3)V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-4,2)(-1, 8)(-4,3)(-2, 3)運籌學(xué)在賦權(quán)在賦權(quán)圖圖W(f (3)上求出上求出最短路最短路V1 (4,2)(2, 3)(-1,7)(6, 0)(4,3)V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-4