物流運籌學課件7

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

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

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

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

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

6、數目稱為點vi的次（也叫做度），記作d(vi)。右圖中d(v1)＝４,d(v3)=5,d(v5)=1。次為奇數的點稱作奇點，次為偶數的點稱作偶點，次為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圖）,圖的基本概念與模型,網絡（賦權圖）,設圖G＝（V，E），對G的每一條邊(vi,vj)相應賦予數量指標wij，wij稱為邊(vi,vj)的權,賦予權的圖G稱為網絡(或賦權圖）。權可以代表距離、費用、通過能力(容量)等等。端點無序的賦權圖稱為無向網絡，端點有序的

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

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

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

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

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

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

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

16、,邊數＝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,樹與圖的最小樹,練習：應用破圈法求最小樹,樹與圖的最小樹,樹與圖的最小樹,,,,,

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,樹與圖的最小樹,練習：應用避圈法求最小樹,,,,,,,,,,,,,,,,,,,,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,樹與圖的最小樹,課堂練習：,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,最短路問題,如何用最短的線路將三部電話連起來？此問題可抽象為設△ABC為三角形，，連接三頂點的路線（稱為網絡）。這種網絡有許多個，其中最短路線者顯然是二邊之和（如AB∪AC）。,,,,A,

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

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

26、ay）2） 點—— vi ,Uj表示河岸的狀態(tài)3） 邊—— ek 表示由狀態(tài) vi 經一次渡河到狀態(tài) vj 4） 權——邊 ek 上的權定為 1,我們可以得到下面的加權有向圖,最短路問題,狀態(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),此游戲轉化為在下面的二部圖中求從 v1 到 u1 的最短路問題。,,v

27、1,v2,v3,v4,v5,u5,u4,u3,u2,u1,,,,,,,,,,,,,,,,,,,,,,,,,,最短路問題,求最短路有兩種算法:,狄克斯特拉(Dijkstra)標號算法 逐次逼近算法,最短路問題,狄克斯特拉(Dijkstra)標號算法的基本思路：若序列{ 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的最短路。,最短路問題,求網絡圖的最短路，設圖的起點是vs,終點是vt ,以vi為起點vj為終點的弧記為 (i, j) 距離為dij,P標號(點標號)：P(vj) —起點vs到點vj的最短路長；T標號(邊標號)： T (Vi,Vj)k=P(i)+dij，,步驟：,1. 令起點的標號；P(s)＝0。,2. 找出所有vi已

29、標號vj未標號的弧集合 B={(i, j)} 如果這樣的弧不存在或vt已標號則計算結束；,3. 計算集合B中弧k(i，j)=P(i)+dij的標號,4. 選一個點標號 在終點vl處標號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已標號，計算結束。從v1到v7的最短路長是 11,最短路線： v1→ v4 → v6 → v7,最短路問題,從上例知，只要某點已標號，說明已找到起點vs到該點的最短路線及最短距離，因此可以將每個點標號，求出vs到任意點的最短路線，如果某個點vj不能標號，說明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,所有點都已標號，點上的標號就是v1到該點的最短距離，最短路線就是紅色的鏈。,最短路問題,課堂練習：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,網絡的最大流,如何制定一個運輸計劃

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

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

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

36、的流量為v(f )， (V, V´)為任意一個割集，則 v(f ) = f(V, V´) ? f(V´, V),推論1 對網絡 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 在網絡中s→t的最大流量等于它的最小割集的容量， 即: v＊ (f ) = c ＊(V, V´),網絡的最大流,增廣鏈在網絡的發(fā)點和收點之間能找到一條鏈，在該鏈上所有指向為s→t的弧，稱為前向弧，記作μ+,存在f0，則稱這樣的鏈為增廣鏈。例如下圖中，s→v2→v1→v3→v4→t。,定理3 網絡N中的流 f 是

38、最大流當且僅當N中不包含任何增廣鏈.,網絡的最大流,●,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(4),7(5),,,,,,網絡的最大流,求網絡最大流的標號算法：[基本思想] 由一個流開始，系統地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個增流過程，直至不存在增廣鏈。,[基本方法],找出第一個可行流，（例如所有弧的流量fij =0。）用標號的方法找一條增廣鏈,首先給發(fā)

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

40、條從s到t得由標號點及相應的弧連接而成的增廣鏈。繼續(xù)第(4)步,網絡的最大流,(4) 修改流量。設原圖可行流為f，令,得到網絡上一個新的可行流f’。,(5) 擦除圖上所有標號，重復(1)-(4)步，直到圖中找不到任何增廣鏈，計算結束。,網絡的最大流,例7.13 用標號算法求下圖中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、,網絡的最大流,解：(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),(∞),網絡的最大流,●,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點相鄰的未標號的點，因fs1<cs1，故對v1標號=min{∞, cs1-fs1}=1

42、,,,(1),網絡的最大流,●,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點相鄰的未標號的點，因f13<c13，故對v3標號=min{1, c13-f13}= min{1, 6}= 1,(1),,網絡的最大流,●,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點相鄰的未標號的點，因f3t<c3t，故對vt標號 =min{1, c3t-f3t}= min{1, 1}= 1,(1),,找到一條增廣鏈s→v1→v3→t,網絡的最大流,(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),,網絡的最大流,(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),,網絡的最大流,(5) 擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。,●,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,,網絡的最大流,(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),,網絡的最大流,●,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) 擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。,網絡的最大流,●,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) 擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。,ε(2)=min{∞,1}=1,ε(1)=min{1,2}=1,ε(3)=min{1,4}=1,,網絡的最大流,例7.14 求下圖s→t的最大流，并找出最小割,網絡的最大流,解: (1) 在已知可行流的基礎上，通過標號尋找增廣鏈。,(∞),ε(2)=min{∞,6}=6,(6),,ε

48、(3)=min{6,2}=2,(2),,,ε(t)=min{2,5}=2,(2),存在增廣鏈s→v2→v3→ t,網絡的最大流,(2) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。,(∞),(6),,(2),,,(2),網絡的最大流,(3) 擦除原標號，重新搜尋增廣鏈。,(∞),(6),,(2),,,(2),網絡的最大流,(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,網絡的最大流,(5) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。,,,,(∞),(4),(1),(1),(1),,網絡的最大流,(6) 擦除原標號,,,,(∞),(4),(1),(1),(1),,網絡的最大流,,,(∞),(1),(1),(1),,ε(5)=min{∞,1}=1

50、,ε(5)=min{1,1}=1,ε(5)=min{1,2}=1,(7) 重新搜尋增廣鏈。,存在增廣鏈：s→v5→v3→ t,網絡的最大流,(8) 調整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流,,,(∞),(1),(1),(1),,網絡的最大流,,,(∞),(1),(1),(1),,(9) 擦除原標號,網絡的最大流,(10) 重新標號，搜索增廣鏈,(∞),ε(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,網絡的最大流,(∞),(1),,(1),,(1),,(1),,(11) 調整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流,網絡的最大流,(∞),(1),,(1),,(1),,(1),,(11) 擦除標號，在新的可行流上重新標號。,,網絡的最大流,(∞),(11) 擦除標號，在新的可行流上重新標號。,