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

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

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

3、關(guān)系。F?。簬Ъ^的聯(lián)線，表示不對(duì)稱關(guān)系?；。簬Ъ^的聯(lián)線，表示不對(duì)稱關(guān)系。F無(wú)向圖：簡(jiǎn)稱圖，有點(diǎn)和邊組成。無(wú)向圖：簡(jiǎn)稱圖，有點(diǎn)和邊組成。F 表示為：表示為： G=（V，E）F V-點(diǎn)集合點(diǎn)集合 E-邊集合邊集合F例：右圖例：右圖V=v1，v2，v3，v4 E=e1，e2，,e7e1=v1,v2e2=v1,v2, ,e7=v4,v41v2v3v4v1e2e3e4e5e6e7e運(yùn)籌學(xué)F 有向圖：由點(diǎn)和弧組成。表示為：有向圖：由點(diǎn)和弧組成。表示為：F D=（V，A）F V-點(diǎn)集合點(diǎn)集合 A-弧集合弧集合F點(diǎn)數(shù)點(diǎn)數(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運(yùn)籌學(xué)F端點(diǎn)端點(diǎn): e=u,vE, : e=u,vE, 則則u,vu,v是是e e的端點(diǎn)的端點(diǎn), , 稱稱u,vu,v相鄰相鄰. .F關(guān)聯(lián)邊關(guān)聯(lián)邊: e: e是點(diǎn)是點(diǎn)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多重邊多重邊: : 兩點(diǎn)之間多于一條邊兩點(diǎn)之間多于一條邊. .F簡(jiǎn)單圖簡(jiǎn)單圖: : 無(wú)環(huán)無(wú)環(huán), ,無(wú)多重邊的圖無(wú)多重邊的圖. .F多重圖多重圖: : 無(wú)環(huán)無(wú)環(huán), ,允許有多重邊的圖允許有多重邊的圖. .運(yùn)籌學(xué)1v2v3v4v1e2e3e4

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

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

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

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

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

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

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

12、的一個(gè)支撐樹。個(gè)支撐樹。F定理定理5 5：圖：圖G=G=（V V，E E有支撐樹的充分必有支撐樹的充分必要條件是要條件是G G是連通的。是連通的。運(yùn)籌學(xué)F求支撐樹的破圈法求支撐樹的破圈法運(yùn)籌學(xué)F求支撐樹的避圈法求支撐樹的避圈法深探法廣探法運(yùn)籌學(xué)F賦權(quán)圖賦權(quán)圖( (網(wǎng)絡(luò)）網(wǎng)絡(luò)）: : 給圖給圖G=(V,E), G=(V,E), 對(duì)對(duì)G G中的中的每一條邊每一條邊vi,vj, vi,vj, 相應(yīng)地有一個(gè)數(shù)相應(yīng)地有一個(gè)數(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的一個(gè)支撐的一個(gè)支撐樹樹, E, E中的所有邊的權(quán)之和稱為支撐樹中的所有邊的權(quán)之和稱為支撐樹的權(quán)的權(quán), , 記為記為w(T):w(T):TvvijjiwTw,)(運(yùn)籌學(xué)F定義定義: : 最小支撐樹最小支撐樹( (最小樹最小樹)T)T* *: :F求最小樹的求最小樹的 避圈法避圈法: : 例例: : 圖圖8-278-27F求最小樹的求最小樹的 破圈法破圈法: : 例例: : 圖圖8-28 8-28 )()(min*TwTwT運(yùn)籌學(xué)有向樹中根樹有向樹中根樹在計(jì)算機(jī)科學(xué)、決策論的應(yīng)用在計(jì)算機(jī)科學(xué)、決策論的應(yīng)用F有向樹：有向樹：F根樹：有向樹根樹：有向樹T，恰有一個(gè)結(jié)，恰有一

14、個(gè)結(jié)點(diǎn)入次為點(diǎn)入次為0，其余各點(diǎn)入次為，其余各點(diǎn)入次為1，則稱，則稱T為根樹。為根樹。FM叉樹：叉樹：F二叉樹：結(jié)點(diǎn)的出度都小于二叉樹：結(jié)點(diǎn)的出度都小于等于等于2。根葉分點(diǎn)枝第一層第三層第二層三叉樹運(yùn)籌學(xué)F帶權(quán)的二叉樹帶權(quán)的二叉樹T：有：有s個(gè)葉子，權(quán)分別為個(gè)葉子，權(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個(gè)葉子按權(quán)由小到大排列，個(gè)葉子按權(quán)由小到大排列，F(xiàn)將兩個(gè)最小的葉子合并為一個(gè)分枝點(diǎn)，其權(quán)為兩者將兩個(gè)最

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

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

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

18、號(hào)節(jié)點(diǎn)的集合。(v)：最短路中前一個(gè)節(jié)點(diǎn)的編號(hào)。初始值： () () ()0sssTvvvvsvvv 運(yùn)籌學(xué)例:011122330 1 ()0 ()0 () ()1 () ()1 . . iSvkP vvT vvT vv 99 () ()1T vv 運(yùn)籌學(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運(yùn)籌學(xué) 3 3)( , 2 )()(),( ),(),(),(),(),( min4)( 11)( )(11101)(: ),(334123987653266646464kvPvvvSivTvTvTvTvTvTvTvTvvTvTwvPvv運(yùn)籌學(xué) 2 5)( , 3 )()(),(),( ),(),(),( min3)( 5)( 6)(523)(: ),(223413298765222232323kvPvvvvSivTvTvTvTvTvTvTvvTvTwvPvv運(yùn)籌學(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 運(yùn)籌學(xué) 7 9)( , 5 )()(),(),( ),(min5)( 12)( )(1266)(: ),( 5)( 9)( )(936)(: ),( 5)( 10)( )(1046)(: ),(77523415798768845858577757575610656565kvPvvvvvvSivTvTvTvTvTvvTvTwvPvvvvTvTwvPvvvvTvTwvPvv運(yùn)籌學(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 運(yùn)籌學(xué) 6689871432576888899,min (),()() 7 , ()12 8,min() () . vST vT vT viSvvvvvvvvP vkvST vT v 無(wú) 指 向 不 屬 于的 點(diǎn) 轉(zhuǎn) 向 無(wú) 指 向 不 屬 于的 點(diǎn) 轉(zhuǎn) 向 算 法 終 止運(yùn)籌學(xué)總結(jié): 算法步驟:MvvTvvPvvPvvPvvPvvPv

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

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

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

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

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

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

28、鏈為止.若存在最小費(fèi)用增廣鏈, 調(diào)整流量如下: ),( ),( ),( )(min),(minmin)1()1()1()1()1(jikijjikijjikijkijkijkijijvvfvvfvvffffc運(yùn)籌學(xué)初初始始網(wǎng)網(wǎng)絡(luò)絡(luò)數(shù)數(shù)值值VsV1 V2 V3 Vt 運(yùn)籌學(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 運(yùn)籌學(xué)取初始取初始可行流可行流f (0) =0V1 V2 V3 Vs Vt 運(yùn)籌學(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運(yùn)籌學(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運(yùn)籌學(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 運(yùn)籌學(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 運(yùn)籌學(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 運(yùn)籌學(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運(yùn)籌學(xué)(4,0)(2, 0)(6, 0)(4,0)在最短在最短路上增路上增加流量加流量原流量原流量如圖所如圖所示示V1 V2 V3 Vs Vt (1, 0)(1, 0)(2, 0)運(yùn)籌學(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)運(yùn)籌學(xué)(4,0)(1, 5)(2, 0)(1,5)(2, 5)(6, 0)(4,0)在最短在最短路上增路上增加流量加流量 = 5得到新得到新的流量的流量f (1)=5V1 V2 V3 Vs Vt 運(yùn)籌學(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)*只對(duì)只對(duì)增廣鏈增廣鏈V1 V2 V3 Vs Vt 80 0 ijijijjiijijijijijijffbwcfcfbw運(yùn)籌學(xué)(4,0)(2, 0)(1,5) (2, 5)(6, 0)(4,0)賦賦權(quán)權(quán)圖圖W(f (1)的構(gòu)造的構(gòu)造*只對(duì)只對(duì)增廣鏈增廣鏈V1 V2 V3 Vs Vt 8(-1, 5)(1, 5)運(yùn)籌學(xué)(4,0)(2, 0)(1,5)(2, 5)(6, 0)(4,0)賦賦權(quán)權(quán)圖圖W(f (1)的構(gòu)造的構(gòu)造*只對(duì)只對(duì)增廣鏈增廣鏈V1 V2 V3 Vs Vt

33、 8 5(-1, 5)(1, 5)0 0 ijijijjiijijijijijijffbwcfcfbw運(yùn)籌學(xué)(4,0)(2, 0)(1,5)(6, 0)(4,0)賦賦權(quán)權(quán)圖圖W(f (1)的構(gòu)造的構(gòu)造*只對(duì)只對(duì)增廣鏈增廣鏈V1 V2 V3 Vs Vt 8 5(-2, 5) 7(-1,5)(-1, 5)(1, 5)運(yùn)籌學(xué)(4,0)(2, 0)(1,5)(6, 0)(4,0)構(gòu)造的構(gòu)造的賦權(quán)賦權(quán)圖圖W(f (1)*只對(duì)只對(duì)增廣鏈增廣鏈V1 V2 V3 Vs Vt (-2, 5)(-1,5)(-1, 5)(1, 5)運(yùn)籌學(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)運(yùn)籌學(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 最小最小運(yùn)籌學(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 運(yùn)籌學(xué)依據(jù)新依據(jù)新的流量的流量構(gòu)造又構(gòu)造又一賦權(quán)一賦權(quán)圖圖W(f (2)*只對(duì)只對(duì)增廣鏈

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)運(yùn)籌學(xué)對(duì)最短對(duì)最短路上求路上求新的權(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運(yùn)籌學(xué)賦賦權(quán)權(quán)圖圖的構(gòu)造的構(gòu)造W(f (2)*只對(duì)只對(duì)增廣鏈增廣鏈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運(yùn)籌學(xué)賦賦權(quán)權(quán)圖圖的構(gòu)造的構(gòu)造W(f (2)*只對(duì)只對(duì)增廣鏈增廣鏈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運(yùn)籌學(xué)賦賦權(quán)權(quán)圖圖的構(gòu)造的構(gòu)造W(f (2)*只對(duì)只對(duì)增廣鏈增廣鏈V1 (4,2)(2, 0)(-1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-2, 5)(-4,2)(-1, 5)(1, 5)運(yùn)籌學(xué)新新賦賦權(quán)權(quán)圖圖W(f (2)

37、*只對(duì)只對(duì)增廣鏈增廣鏈V1 (4,2)(2, 0)(-1,7)(6, 0)(4,0)V1 V2 V3 Vs Vt (-2, 5)(-4,2)(-1, 5)(1, 5)運(yùn)籌學(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)運(yùn)籌學(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運(yùn)籌學(xué)(4,2)(1,

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