版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
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)=4,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不可達(dá)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)值達(dá)到最大。,網(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)號。,
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 運籌學(xué)課件
- 運籌學(xué)第7章
- 運籌學(xué)課件 6
- 運籌學(xué)課件 1
- 運籌學(xué)》習(xí)題答案運籌學(xué)答案
- 運籌學(xué)
- 運籌學(xué)》習(xí)題答案運籌學(xué)答案匯總
- 《運籌學(xué)》課件-第2講
- 《運籌學(xué)與最優(yōu)化方法》課件
- 運籌學(xué)習(xí)題答案運籌學(xué)答案
- 858 運籌學(xué)
- 《運籌學(xué)1》
- 運籌學(xué) 1
- 運籌學(xué)基礎(chǔ)
- 運籌學(xué)復(fù)習(xí)
- 工程碩士運籌學(xué)課件及重點
- 運籌學(xué)習(xí)題運籌學(xué)練習(xí)題
- 運籌學(xué)大作業(yè)
- 《運籌學(xué)基礎(chǔ)》2005
- 《管理運籌學(xué)》論文
評論
0/150
提交評論