物流運籌學(xué)課件7

1、物流運籌學(xué)Logistics Operational Research,物流管理專業(yè)基礎(chǔ)課程,郭淑紅guoshuhong_1982@163.com13074553453,Chapter7 圖與網(wǎng)絡(luò)分析( Graph Theory and Network Analysis ),,圖的基本概念與模型樹與圖的最小樹最短路問題網(wǎng)絡(luò)的最大流,本章主要內(nèi)容：,圖的基本概念與模型,松 花,江,,呼,蘭,哈爾濱師范大學(xué)（江南）,呼蘭,

2、肇東,您能從哈爾濱師范大學(xué)大學(xué)出發(fā)走過每座橋且只走一次然后回到學(xué)校嗎?,河,,,,,,,,,,,,陸地A,陸地B,島D,島C,A·,D ·,·B,· C,,,,,,,,1736年瑞士數(shù)學(xué)家歐拉將兩岸和小島抽象為四個點，將橋抽象為七條邊，此問題歸結(jié)為一筆畫問題。,近代圖論的歷史可追溯到18世紀(jì)的七橋問題—哥尼斯堡城中有一條普雷格爾河，河上有七座橋?qū)⒑又械膬蓚€小島與河岸連接起來。人們提出了這樣

3、的問題：一個散步者能否從某地出發(fā)，走遍七橋且每座橋恰好經(jīng)過一次，最后回到原地？這就是著名的“哥尼斯堡 7 橋”難題。歐拉Euler1736年證明了不可能存在這樣的路線。,圖的基本概念與模型,圖的基本概念與模型,圖論中圖是由點和邊構(gòu)成，可以反映一些對象之間的關(guān)系。一般情況下圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的。,圖的定義：若用點表示研究的對象，用邊表示這些對象之間的聯(lián)系，則圖G可以定義為

4、點和邊的集合，記作：,其中: V——點集 E——邊集,※ 圖G區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個點以及哪些點之間有連線。,圖的基本概念與模型,可見圖論中的圖與幾何圖、工程圖是不一樣的。,例如：在一個人群中，對相互認(rèn)識這個關(guān)系我們可以用圖來表示。,圖的基本概念與模型,定義: 圖中的點用v表示，邊用e表示。對每條邊可用它所連接的點表示，記作：e1=[v1,v1]; e2=[v1,v2];,端點,關(guān)聯(lián)邊,相鄰,若有邊e可表示為e=

5、[vi,vj]，稱vi和vj是邊e的端點，反之稱邊e為點vi或vj的關(guān)聯(lián)邊。若點vi、vj與同一條邊關(guān)聯(lián)，稱點vi和vj相鄰；若邊ei和ej具有公共的端點，稱邊ei和ej相鄰。,圖的基本概念與模型,環(huán), 多重邊, 簡單圖,如果邊e的兩個端點相重，稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個點之間多于一條，稱為多重邊，如右圖中的e4和e5，對無環(huán)、無多重邊的圖稱作簡單圖。,圖的基本概念與模型,次，奇點，偶點，孤立點,與某一個點vi相關(guān)聯(lián)的邊的

6、數(shù)目稱為點vi的次（也叫做度），記作d(vi)。右圖中d(v1)＝４,d(v3)=5,d(v5)=1。次為奇數(shù)的點稱作奇點，次為偶數(shù)的點稱作偶點，次為1的點稱為懸掛點，次為0的點稱作孤立點。,圖的次: 一個圖的次等于各點的次之和。,圖的基本概念與模型,鏈，圈，連通圖,圖中某些點和邊的交替序列，若其中各邊互不相同，且對任意vi,t-1和vit均相鄰稱為鏈。用μ表示：,起點與終點重合的鏈稱作圈。如果每一對頂點之間至少存在一條鏈，稱這樣的圖為

7、連通圖，否則稱圖不連通。,圖的基本概念與模型,二部圖（偶圖）,圖G=(V,E)的點集V可以分為兩各非空子集X，Y，集X∪Y=V,X∩Y=Ø,使得同一集合中任意兩個頂點均不相鄰，稱這樣的圖為偶圖。,(a),(b),(c),,(a)明顯為二部圖，(b)也是二部圖，但不明顯，改畫為(c)時可以清楚看出。,圖的基本概念與模型,子圖，部分圖(支撐子圖),圖G1={V1、E1}和圖G2={V2，E2}如果有

8、 稱G1是G2的一個子圖。若有 ，則稱G1是G2的一個部分圖(支撐子圖)。,(a),(b),（G圖）,圖的基本概念與模型,網(wǎng)絡(luò)（賦權(quán)圖）,設(shè)圖G＝（V，E），對G的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊(vi,vj)的權(quán),賦予權(quán)的圖G稱為網(wǎng)絡(luò)(或賦權(quán)圖）。權(quán)可以代表距離、費用、通過能力(容量)等等。端點無序的賦權(quán)圖稱為無向網(wǎng)絡(luò)，端點有序的

9、賦權(quán)圖稱為有向網(wǎng)絡(luò)。,圖的基本概念與模型,出次與入次,有向圖中，以vi為始點的邊數(shù)稱為點vi的出次，用d+(vi)表示；以vi為終點的邊數(shù)稱為點vi 的入次，用表示d-(vi) ；vi 點的出次和入次之和就是該點的次。,※ 有向圖中，所有頂點的入次之和等于所有頂點的出次之和。,圖的基本概念與模型,圖的模型應(yīng)用,例7.1 有甲,乙,丙,丁,戊,己6名運動員報名參加A,B,C,D,E,F 6個項目的比賽。下表中打√的是各運動員報告參加的比

10、賽項目。問6個項目的比賽順序應(yīng)如何安排，做到每名運動員都不連續(xù)地參加兩項比賽。,圖的基本概念與模型,解：用圖來建模。把比賽項目作為研究對象，用點表示。如果2個項目有同一名運動員參加，在代表這兩個項目的點之間連一條線，可得下圖。,在圖中找到一個點序列，使得依次排列的兩點不相鄰，即能滿足要求。如：1) A,C,B,F,E,D2) D,E,F,B,C,A,圖的基本概念與模型,一個班級的學(xué)生共計選修A、B、C、D、E、F六門課程，其中一部分

11、人同時選修D(zhuǎn)、C、A，一部分人同時選修B、C、F，一部分人同時選修B、E，還有一部分人同時選修A、B，期終考試要求每天考一門課，六天內(nèi)考完，為了減輕學(xué)生負(fù)擔(dān)，要求每人都不會連續(xù)參加考試，試設(shè)計一個考試日程表。,思考題,圖的基本概念與模型,思考題解答： 以每門課程為一個頂點，共同被選修的課程之間用邊相連，得圖，按題意，相鄰頂點對應(yīng)課程不能連續(xù)考試，不相鄰頂點對應(yīng)課程允許連續(xù)考試，因此，作圖的補圖，問題是在圖中尋找一條哈密頓道路，如C—

12、E—A—F—D—B，就是一個符合要求的考試課程表。,圖的基本概念與模型,,,,,,,A,F,E,D,C,B,,,,,,,,,圖的基本概念與模型,,,A,F,E,D,C,B,,,,,,,,,,,,,,,,,,圖的基本概念與模型,圖的基本性質(zhì)：,定理1 任何圖中，頂點次數(shù)之和等于所有邊數(shù)的2倍。,定理2 任何圖中，次為奇數(shù)的頂點必為偶數(shù)個。,證明：由于每條邊必與兩個頂點關(guān)聯(lián)，在計算點的次時，每條邊均被計算了兩次，所以頂點次數(shù)的總和等于邊

13、數(shù)的2倍。,證明：設(shè)V1和V2分別為圖G中奇點與偶點的集合。由定理1可得：,2m為偶數(shù)，且偶點的次之和 也為偶數(shù)，所以 必為偶數(shù)，即奇數(shù)點的個數(shù)必為偶數(shù)。,樹與圖的最小樹,樹是圖論中結(jié)構(gòu)最簡單但又十分重要的圖。在自然和社會領(lǐng)域應(yīng)用極為廣泛。,例7.2 乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如下圖所示。,運動員,樹與圖的最小樹,例7.3 某企業(yè)的組織機構(gòu)圖也可用樹圖表示。,樹與圖的最小樹,樹：無

14、圈的連通圖即為樹,性質(zhì)1：任何樹中必存在次為1的點。性質(zhì)2：n 個頂點的樹必有n-1 條邊。性質(zhì)3：樹中任意兩個頂點之間，恰有且僅有一條鏈。性質(zhì)4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。性質(zhì)5：樹無回圈，但不相鄰的兩個點之間加一條邊，恰得到一個圈。,樹與圖的最小樹,圖的最小部分樹(支撐樹),如果G2是G1的部分圖，又是樹圖，則稱G2是G1的部分樹（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖G1含有多個部分樹，其中樹枝總長最小的部分

15、樹，稱為該圖的最小部分樹（或最小支撐樹）。,G1,G2,樹與圖的最小樹,樹與圖的最小樹,樹與圖的最小樹,樹與圖的最小樹,樹與圖的最小樹,樹與圖的最小樹,求樹的方法：破圈法和避圈法,破圈法,,,,樹與圖的最小樹,,部分樹,樹與圖的最小樹,避圈法,樹與圖的最小樹,賦權(quán)圖中求最小樹的方法：破圈法和避圈法,破圈法：任取一圈，去掉圈中最長邊，直到無圈。,,,,,,,,,,,v1,v2,v3,v4,v5,v6,4,3,5,2,1,,,,,,,,,,

16、,邊數(shù)＝n-1=5,樹與圖的最小樹,得到最小樹：,Min C(T)=15,樹與圖的最小樹,避圈法:去掉G中所有邊，得到n個孤立點；然后加邊。加邊的原則為：從最短邊開始添加，加邊的過程中不能形成圈，直到點點連通(即:n-1條邊)。,樹與圖的最小樹,,,,,,,,,,,,v1,v2,v3,v4,v5,v6,4,3,5,2,1,Min C(T)=15,樹與圖的最小樹,練習(xí)：應(yīng)用破圈法求最小樹,樹與圖的最小樹,樹與圖的最小樹,,,,,

17、,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,樹與圖的最小樹,

18、,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,15,9,16,25,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,9,16,25,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,

19、,,,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,9,25,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,9,3,28,17,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,9,3,28,17

20、,4,1,23,樹與圖的最小樹,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,9,3,17,4,1,23,min=1+4+9+3+17+23=57,樹與圖的最小樹,練習(xí)：應(yīng)用避圈法求最小樹,,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,樹與圖的最小樹,,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,

21、v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,樹與圖的最小樹,,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,樹與圖的最小樹,,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,樹與圖的最小樹,,,,,,,,,,,,,,,

22、,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,樹與圖的最小樹,,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,樹與圖的最小樹,,,,,,,,,,,,,,,,,,,,v1,v7,v4,v3,v2,v5,v6,20,15,9,16,25,3,28,17,4,1,23,36,mi

23、n=1+4+9+3+17+23=57,樹與圖的最小樹,課堂練習(xí)：,Min C(T)=12,Min C(T)=15,答案：,樹與圖的最小樹,,,,,,,,,,,3,4,1,2,2,3,2,3,2,4,2,Min C(T)=12,Min C(T)=18,最短路問題,如何用最短的線路將三部電話連起來？此問題可抽象為設(shè)△ABC為三角形，，連接三頂點的路線（稱為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個，其中最短路線者顯然是二邊之和（如AB∪AC）。,,,,A,

24、B,C,,最短路問題,,,,,,,A,B,C,P,但若增加一個周轉(zhuǎn)站（新點P），連接4點的新網(wǎng)絡(luò)的最短路線為PA＋PB＋PC。最短新路徑之長N比原來只連三點的最短路徑O要短。這樣得到的網(wǎng)絡(luò)不僅比原來節(jié)省材料，而且穩(wěn)定性也更好。,最短路問題,問題描述：就是從給定的網(wǎng)絡(luò)圖中找出一點到各點或任意兩點之間距離最短的一條路 .有些問題，如選址、管道鋪設(shè)時的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短路的問題。因此

25、這類問題在生產(chǎn)實際中得到廣泛應(yīng)用。,最短路問題,例7.4 渡河游戲一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過河到北岸，河上只有一條獨木舟，每次除了人以外，只能帶一樣?xùn)|西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，問應(yīng)該怎樣安排渡河，才能做到既把所有東西都運過河去，并且在河上來回次數(shù)最少？這個問題就可以用求最短路方法解決。,最短路問題,定義：1）人—M（Man），狼—W（Wolf）， 羊—G（Goat）， 草—H（H

26、ay）2） 點—— vi ,Uj表示河岸的狀態(tài)3） 邊—— ek 表示由狀態(tài) vi 經(jīng)一次渡河到狀態(tài) vj 4） 權(quán)——邊 ek 上的權(quán)定為 1,我們可以得到下面的加權(quán)有向圖,最短路問題,狀態(tài)說明：v1,u1 =( M,W,G,H ); v2,u2 =(M,W,G); v3,u3 =(M,W,H); v4,u4=(M,G,H); v5,u5 =(M,G),此游戲轉(zhuǎn)化為在下面的二部圖中求從 v1 到 u1 的最短路問題。,,v

27、1,v2,v3,v4,v5,u5,u4,u3,u2,u1,,,,,,,,,,,,,,,,,,,,,,,,,,最短路問題,求最短路有兩種算法:,狄克斯特拉(Dijkstra)標(biāo)號算法 逐次逼近算法,最短路問題,狄克斯特拉(Dijkstra)標(biāo)號算法的基本思路：若序列{ vs,v1…..vn-1,vn }是從vs到vt間的最短路，則序列{ vs,v1…..vn-1 } 必為從vs 到vn-1的最短路。,假定v1→v2 →v3 →v

28、4是v1 →v4的最短路，則v1 →v2 →v3一定是v1 →v3的最短路，v2 →v3 →v4也一定是v2 →v4的最短路。,最短路問題,求網(wǎng)絡(luò)圖的最短路，設(shè)圖的起點是vs,終點是vt ,以vi為起點vj為終點的弧記為 (i, j) 距離為dij,P標(biāo)號(點標(biāo)號)：P(vj) —起點vs到點vj的最短路長；T標(biāo)號(邊標(biāo)號)： T (Vi,Vj)k=P(i)+dij，,步驟：,1. 令起點的標(biāo)號；P(s)＝0。,2. 找出所有vi已

29、標(biāo)號vj未標(biāo)號的弧集合 B={(i, j)} 如果這樣的弧不存在或vt已標(biāo)號則計算結(jié)束；,3. 計算集合B中弧k(i，j)=P(i)+dij的標(biāo)號,4. 選一個點標(biāo)號 在終點vl處標(biāo)號P(l), 返回到第2步。,最短路問題,例7.5 求下圖v1到v7的最短路長及最短路線,0,8,6,2,,2,5,4,4,,11,14,7,5,10,

30、,7,12,11,,,v7已標(biāo)號，計算結(jié)束。從v1到v7的最短路長是 11,最短路線： v1→ v4 → v6 → v7,最短路問題,從上例知，只要某點已標(biāo)號，說明已找到起點vs到該點的最短路線及最短距離，因此可以將每個點標(biāo)號，求出vs到任意點的最短路線，如果某個點vj不能標(biāo)號，說明vs不可達vj 。,注：無向圖最短路的求法只將上述步驟2將弧改成邊即可。,最短路問題,例7.6 求下圖v1到各點的最短距離及最短路線。,0,4,5,2,

31、,2,3,10,,3,9,6,12,6,,4,11,,6,,6,18,8,12,24,,8,24,,18,所有點都已標(biāo)號，點上的標(biāo)號就是v1到該點的最短距離，最短路線就是紅色的鏈。,最短路問題,課堂練習(xí)：1. 用Dijkstra算法求下圖從v1到v6的最短距離及路線。,v3,v5,4,v1到v6的最短路為：,最短路問題,2. 求從v1到v8的最短路徑,最短路問題,v1到v8的最短路徑為v1→v4→v7→v5→v8，最短距離為10,最

32、短路問題,3. 求下圖中v1點到另外任意一點的最短路徑,,,,,,,,,,,v1,v2,v3,v4,v6,v5,3,2,2,7,6,2,1,3,3,最短路問題,,,,,,,,,,,v1,V2,V3,V4,V6,V5,3,2,2,7,6,2,1,3,3,0,2,4,7,1,4,最短路問題,,,,,,,,,,,v1,V2,V3,V4,V6,V5,3,2,2,7,6,2,1,3,3,,0,2,4,7,1,4,網(wǎng)絡(luò)的最大流,如何制定一個運輸計劃

33、使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個網(wǎng)絡(luò)最大流問題。,網(wǎng)絡(luò)的最大流,基本概念：1. 容量網(wǎng)絡(luò)：隊網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個最大的通過能力，稱為該弧的容量，簡記為cij。容量網(wǎng)絡(luò)中通常規(guī)定一個發(fā)點(也稱源點，記為s)和一個收點(也稱匯點，記為t)，網(wǎng)絡(luò)中其他點稱為中間點。,s,①,②,③,④,t,,,,,,,,,,,4,8,4,4,1,2,2,6,7,9,,,,網(wǎng)絡(luò)的最大流,2. 網(wǎng)絡(luò)的最大流是指網(wǎng)絡(luò)中從發(fā)點到收

34、點之間允許通過的最大流量。,3. 流與可行流 流是指加在網(wǎng)絡(luò)各條弧上的實際流量，對加在弧(vi,vj)上的負(fù)載量記為fij。若fij=0，稱為零流。滿足以下條件的一組流稱為可行流。,容量限制條件。容量網(wǎng)絡(luò)上所有的弧滿足：0≤fij≤cij 中間點平衡條件。,若以v(f)表示網(wǎng)絡(luò)中從s→t的流量，則有：,網(wǎng)絡(luò)的最大流,結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是可行流）,網(wǎng)絡(luò)最大流問題：指滿足容量限制條件和中間點平衡的條件

35、下，使v(f)值達到最大。,網(wǎng)絡(luò)的最大流,割與割集,割是指容量網(wǎng)絡(luò)中的發(fā)點和收點分割開，并使s→t的流中斷的一組弧的集合。割容量是組成割集合中的各條弧的容量之和，用 表示。,網(wǎng)絡(luò)的最大流,如圖中，AA′將網(wǎng)絡(luò)上的點分割成 兩個集合。并有 ，稱弧的集合{(v1,v3),(v2,v4)}是一個割，且 的流量為18。,網(wǎng)絡(luò)的最大流,定理1 設(shè)網(wǎng)絡(luò)N中一個從 s 到 t 的流 f

36、的流量為v(f )， (V, V´)為任意一個割集，則 v(f ) = f(V, V´) ? f(V´, V),推論1 對網(wǎng)絡(luò) 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 )

37、不大于最小割集的容量，即：v＊ (f ) ? min{c(V, V´)},定理2 在網(wǎng)絡(luò)中s→t的最大流量等于它的最小割集的容量， 即: v＊ (f ) = c ＊(V, V´),網(wǎng)絡(luò)的最大流,增廣鏈在網(wǎng)絡(luò)的發(fā)點和收點之間能找到一條鏈，在該鏈上所有指向為s→t的弧，稱為前向弧，記作μ+,存在f0，則稱這樣的鏈為增廣鏈。例如下圖中，s→v2→v1→v3→v4→t。,定理3 網(wǎng)絡(luò)N中的流 f 是

38、最大流當(dāng)且僅當(dāng)N中不包含任何增廣鏈.,網(wǎng)絡(luò)的最大流,●,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)絡(luò)的最大流,求網(wǎng)絡(luò)最大流的標(biāo)號算法：[基本思想] 由一個流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個增流過程，直至不存在增廣鏈。,[基本方法],找出第一個可行流，（例如所有弧的流量fij =0。）用標(biāo)號的方法找一條增廣鏈,首先給發(fā)

39、點s標(biāo)號(∞),標(biāo)號中的數(shù)字表示允許的最大調(diào)整量。 選擇一個點 vi 已標(biāo)號并且另一端未標(biāo)號的弧沿著某條鏈向收點檢查：,網(wǎng)絡(luò)的最大流,如果弧的起點為vi，并且有fij0，則vj標(biāo)號(fji),(3) 重復(fù)第(2)步，可能出現(xiàn)兩種結(jié)局：,標(biāo)號過程中斷，t無法標(biāo)號，說明網(wǎng)絡(luò)中不存在增廣鏈，目前流量為最大流。同時可以確定最小割集，記已標(biāo)號的點集為V,未標(biāo)號的點集合為V′,(V,V′)為網(wǎng)絡(luò)的最小割。 t得到標(biāo)號，反向追蹤在網(wǎng)絡(luò)中找到一

40、條從s到t得由標(biāo)號點及相應(yīng)的弧連接而成的增廣鏈。繼續(xù)第(4)步,網(wǎng)絡(luò)的最大流,(4) 修改流量。設(shè)原圖可行流為f，令,得到網(wǎng)絡(luò)上一個新的可行流f’。,(5) 擦除圖上所有標(biāo)號，重復(fù)(1)-(4)步，直到圖中找不到任何增廣鏈，計算結(jié)束。,網(wǎng)絡(luò)的最大流,例7.13 用標(biāo)號算法求下圖中s→t的最大流量，并找出最小割。,●,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5)

41、,網(wǎng)絡(luò)的最大流,解：(1) 先給s標(biāo)號(∞),●,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)絡(luò)的最大流,●,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(∞),(2) 檢查與s點相鄰的未標(biāo)號的點，因fs1<cs1，故對v1標(biāo)號=min{∞, cs1-fs1}=1

42、,,,(1),網(wǎng)絡(luò)的最大流,●,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點相鄰的未標(biāo)號的點，因f13<c13，故對v3標(biāo)號=min{1, c13-f13}= min{1, 6}= 1,(1),,網(wǎng)絡(luò)的最大流,●,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9)

43、,5(4),7(5),(∞),,(1),(1),,(3) 檢查與v3點相鄰的未標(biāo)號的點，因f3t<c3t，故對vt標(biāo)號 =min{1, c3t-f3t}= min{1, 1}= 1,(1),,找到一條增廣鏈s→v1→v3→t,網(wǎng)絡(luò)的最大流,(4) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。,●,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(3),7

44、(5),(∞),,(1),(1),,(1),,網(wǎng)絡(luò)的最大流,(5) 擦除所有標(biāo)號，重復(fù)上述標(biāo)號過程，尋找另外的增廣鏈。,●,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)絡(luò)的最大流,(5) 擦除所有標(biāo)號，重復(fù)上述標(biāo)號過程，尋找另外的增廣鏈。,●,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6

45、(1),2(0),9(9),5(3),7(5),(∞),(2),,ε(2)=min{∞,2}=2,(2),ε(1)=min{2,3}=2,,ε(3)=min{2,5}=2,(2),,(1),ε(4)=min{2,1}=1,,(1),ε(t)=min{1,2}=1,,網(wǎng)絡(luò)的最大流,(6) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。,●,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(1),2(

46、0),9(9),5(3),7(5),(∞),(2),,(2),,(2),,(1),,(1),,網(wǎng)絡(luò)的最大流,●,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) 擦除所有標(biāo)號，重復(fù)上述標(biāo)號過程，尋找另外的增廣鏈。,網(wǎng)絡(luò)的最大流,●,s,t,v1,v3,v2,v4,8(8),9(5),5(5),10(

47、9),6(0),2(0),9(9),5(2),7(6),(∞),(1),,(1),,(1),,(7) 擦除所有標(biāo)號，重復(fù)上述標(biāo)號過程，尋找另外的增廣鏈。,ε(2)=min{∞,1}=1,ε(1)=min{1,2}=1,ε(3)=min{1,4}=1,,網(wǎng)絡(luò)的最大流,例7.14 求下圖s→t的最大流，并找出最小割,網(wǎng)絡(luò)的最大流,解: (1) 在已知可行流的基礎(chǔ)上，通過標(biāo)號尋找增廣鏈。,(∞),ε(2)=min{∞,6}=6,(6),,ε

48、(3)=min{6,2}=2,(2),,,ε(t)=min{2,5}=2,(2),存在增廣鏈s→v2→v3→ t,網(wǎng)絡(luò)的最大流,(2) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。,(∞),(6),,(2),,,(2),網(wǎng)絡(luò)的最大流,(3) 擦除原標(biāo)號，重新搜尋增廣鏈。,(∞),(6),,(2),,,(2),網(wǎng)絡(luò)的最大流,(4) 重新搜尋增廣鏈。,,,,(∞),ε(2)=min{∞,4}=4,(4),(1),ε(5)=m

49、in{4,1}=1,ε(3)=min{1,2}=1,(1),(1),ε(t)=min{1,3}=1,,存在增廣鏈：s→v2→v5→v3→ t,網(wǎng)絡(luò)的最大流,(5) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。,,,,(∞),(4),(1),(1),(1),,網(wǎng)絡(luò)的最大流,(6) 擦除原標(biāo)號,,,,(∞),(4),(1),(1),(1),,網(wǎng)絡(luò)的最大流,,,(∞),(1),(1),(1),,ε(5)=min{∞,1}=1

50、,ε(5)=min{1,1}=1,ε(5)=min{1,2}=1,(7) 重新搜尋增廣鏈。,存在增廣鏈：s→v5→v3→ t,網(wǎng)絡(luò)的最大流,(8) 調(diào)整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流,,,(∞),(1),(1),(1),,網(wǎng)絡(luò)的最大流,,,(∞),(1),(1),(1),,(9) 擦除原標(biāo)號,網(wǎng)絡(luò)的最大流,(10) 重新標(biāo)號，搜索增廣鏈,(∞),ε(1)=min{∞,1}=1,(1),,ε(5)=min{1,1}=

51、1,(1),,ε(4)=min{1,1}=1,(1),,ε(t)=min{1,1}=1,(1),,存在增廣鏈：s→v1→v5→v4→t,網(wǎng)絡(luò)的最大流,(∞),(1),,(1),,(1),,(1),,(11) 調(diào)整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流,網(wǎng)絡(luò)的最大流,(∞),(1),,(1),,(1),,(1),,(11) 擦除標(biāo)號，在新的可行流上重新標(biāo)號。,,網(wǎng)絡(luò)的最大流,(∞),(11) 擦除標(biāo)號，在新的可行流上重新標(biāo)號。,