Chapter8圖與網絡分析

(GraphTheoryandNetworkAnalysis)圖的基本概念與模型樹與圖的最小樹最短路問題網絡的最大流本章主要內容： 學習要點：

1.掌握一般圖論及其基本概念；

2.能夠應用最短路算法求解實際問題；

3.掌握最大流最小割理論。

18世紀，K?nigsberg是俄羅斯的一個城市（現為加里寧格勒）。市內有七座橋。人們在此散步，問：“能否從某處出發，經過每座橋一次且恰好一次又回到出發點？”1736年，Euler巧妙地將此問題化為圖的不重復一筆畫問題，并證明了該問題不存在肯定回答，發表了第一篇論文。七橋問題圖的基本概念與模型中國郵路問題一郵遞員送信，要走完他所負責的全部街道分送信件，最后返回郵局。郵遞員都會本能地以盡可能少的行程完成送信任務。如何走路線最短。1962年，由我國數學家管梅谷提出，國際上稱為中國郵遞員問題。問題：求一個圈，過每邊至少一次，并使圈的長度最短。圖的基本概念與模型Hamilton圖游戲：用正十二面體上20個頂點表示20個城市，要求參加游戲者沿著各邊行走，走遍每一個城市且僅走一次，最后回到出發城市。問題：如何判斷一個圖是否具有這樣的性質。如果有，這樣的行走路線如何確定。thedodecahedronisHamiltonian顯然這樣的路線存在且不唯一圖的基本概念與模型50112463143726352362511225341538104964214013362761229523328391648760120415429594458533217426472574419305535854631564318在一個棋盤中，若馬（馬走日步）能否從某一點出發跳遍棋盤上每一點恰好一次，再回到出發點？對于4×4，5×5，或8×8的棋盤上馬的跳動如何？圖的基本概念與模型幻方問題圖的基本概念與模型某團體舉行舞會，其中有n個男士與n個女士，每個男士恰好認識r個女士，每個女士也恰好認識r個男士。問：在這個團中，能否做到：每個男士與其認識的女士跳舞，每個女士也與其認識的男士跳舞。比如：任意6個人，一定有3個人相互認識或者有3個人相互不認識鴿籠原理和Ramsey數圖的基本概念與模型四色猜想

能否用四種顏色給地圖染色，使相鄰的國家有不同的顏色。問題：能否用四種顏色給平面圖的點染色，使有公共邊的點有不同的顏色。圖的基本概念與模型M?bius在1840年的一次演講中提出如下問題：一個國王有五個兒子，要求在他死后將國土分成五部分，每個兒子占一部分并建立各自的宮殿。要求每座宮殿之間都有（平面的）路相連且互不相交（不允許立體交叉）。Tietze研究后指出這是不可能的。因為5個頂點的完全圖不是平面圖。平面圖在印刷電路板中有重要的應用。平面圖與網絡圖的基本概念與模型n-方體Qnn方體n維立方體n=3的情形，上底下底是兩個2維立方體。對應頂點連線后(同時把上底中頂點標號末位加號0，下底中頂點標號末位加號1)得到3維立方體。完全二分圖是具有二分劃(X,Y)的二分圖，并且X的每個頂點與Y的每個頂點都相連。完全二分圖記為Km,nK3,3

K2,4

G2G1G2G1G2G1網絡（賦權圖）設圖G＝（V，E），對G的每一條邊(vi,vj)相應賦予數量指標wij，wij稱為邊(vi,vj)的權，賦予權的圖G稱為網絡(或賦權圖）。權可以代表距離、費用、通過能力(容量)等等。端點無序的賦權圖稱為無向網絡，端點有序的賦權圖稱為有向網絡。①②③④⑤⑥910201571419256圖的基本概念與模型一個圖是二部圖當且僅當它不含奇圈。設G

是一個簡單圖，若δ(G)≥2，則G

中必含有圈。設G

是簡單圖，若δ(G)≥3,則G

必有偶圈。設有2n個電話交換臺，每個臺與至少n個臺有直通線路，則該交換系統中任二臺均可實現通話。回答：圖的基本性質：定理1任何圖中，頂點次數之和等于所有邊數的2倍。定理2任何圖中，次為奇數的頂點必為偶數個。證明：由于每條邊必與兩個頂點關聯，在計算點的次時，每條邊均被計算了兩次，所以頂點次數的總和等于邊數的2倍。證明：設V1和V2分別為圖G中奇點與偶點的集合。由定理1可得：2m為偶數，且偶點的次之和也為偶數，所以必為偶數，即奇數點的個數必為偶數。圖的基本概念與模型圖的矩陣描述：如何在計算機中存儲一個圖呢？現在已有很多存儲的方法，但最基本的方法就是采用矩陣來表示一個圖，圖的矩陣表示也根據所關心的問題不同而有：鄰接矩陣、關聯矩陣、權矩陣等1.鄰接矩陣對于圖G=（V，E），|V|=n，|E|=m，有nn階方矩陣A=(aij)nn，其中圖的基本概念與模型2.關聯矩陣對于圖G=(V,E),|V|=n,|E|=m,有mn階矩陣M=(mij)mn，其中:3.權矩陣對于賦權圖G=(V,E),其中邊有權,構造矩陣B=(bij)nn

其中：圖的基本概念與模型v5v1v2v3v4v64332256437

下圖所表示的圖可以構造鄰接矩陣A如下圖的基本概念與模型例1v1v2v3v4v5v6v7v8v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4

下圖所表示的圖可以構造鄰接矩陣M如下:M=（mij）=101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000圖的基本概念與模型例2v5v1v2v3v4v64332256437

下圖所表示的圖可以構造權矩陣B如下:圖的基本概念與模型例3樹是圖論中結構最簡單但又十分重要的圖。在自然和社會領域應用極為廣泛。

乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如下圖所示。ABCDEFGH運動員樹與圖的最小樹

某企業的組織機構圖也可用樹圖表示。樹與圖的最小樹廠長人事科財務科總工程師生產副廠長經營副廠長技術科新產品開發科生產科設備科供應科動力科檢驗科銷售科樹是一個不包含圈的簡單連通圖。樹中度為1的點稱為樹葉，度大于1的點稱為分枝點。具有k個連通分支的不包含圈的圖稱為k-樹，或森林。下是具有六個頂點的樹，圖中的每棵樹都只有5條邊，并且至少有2個頂點的次數是1。樹：無圈的連通圖即為樹性質1：任何樹中必存在次為1的點。性質2：n個頂點的樹必有n-1條邊。性質3：樹中任意兩個頂點之間，恰有且僅有一條鏈。性質4：樹連通，但去掉任一條邊，必變為不連通。性質5：樹無回圈，但不相鄰的兩個點之間加一條邊，恰得到一個圈。v1v2v3v4v5v6樹與圖的最小樹圖的最小部分樹(支撐樹)如果G2是G1的部分圖，又是樹圖，則稱G2是G1的部分樹（或支撐樹）。樹圖的各條邊稱為樹枝。一般圖G1含有多個部分樹，其中樹枝總長最小的部分樹，稱為該圖的最小部分樹（或最小支撐樹）。v1v2v3v4v5v1v2v3v4v5G1G2樹與圖的最小樹(賦權)圖中求最小樹的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最長邊，直到無圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521邊數＝n-1=5樹與圖的最小樹v1v2v3v4v5v643521得到最小樹：MinC(T)=15樹與圖的最小樹避圈法:

去掉G中所有邊，得到n個孤立點；然后加邊。加邊的原則為：從最短邊開始添加，加邊的過程中不能形成圈，直到點點連通(即:n-1條邊)。5v1v2v3v4v5v6843752618樹與圖的最小樹v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15樹與圖的最小樹8.3最短路問題如何用最短的線路將三部電話連起來？此問題可抽象為設△ABC為等邊三角形，連接三頂點的路線（稱為網絡）。這種網絡有許多個，其中最短路線者顯然是二邊之和（如AB∪AC）。ABC最短路問題ABCP但若增加一個周轉站（新點P），連接4點的新網絡的最短路線為PA＋PB＋PC。最短新路徑之長比原來只連三點的最短路徑要短。這樣得到的網絡不僅比原來節省材料，而且穩定性也更好。最短路問題問題描述： 就是從給定的網絡圖中找出一點到各點或任意兩點之間距離最短的一條路。

有些問題，如選址、管道鋪設時的選線、設備更新、投資、某些整數規劃和動態規劃的問題，也可以歸結為求最短路的問題。因此這類問題在生產實際中得到廣泛應用。最短路問題

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

表示河岸的狀態3）邊——ek

表示由狀態vi

經一次渡河到狀態vj

4）權——邊ek

上的權定為1我們可以得到下面的加權有向圖最短路問題狀態說明：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

的最短路問題。v1v2v3v4v5u5u4u3u2u1最短路問題求最短路有兩種算法:狄克斯屈拉(Dijkstra)標號算法逐次逼近算法最短路問題狄克斯屈拉(Dijkstra)標號算法的基本思路：若序列{vs，v1…..vn-1，vn}是從vs到vt間的最短路，則序列{vs，v1…..vn-1

}必為從vs到vn-1的最短路。 假定v1→v2→v3→v4是v1→v4的最短路，則v1→v2→v3一定是v1→v3的最短路，v2→v3→v4也一定是v2→v4的最短路。v1v2v3v4v5最短路問題Dijkstra算法基本步驟Dijkstra算法的基本思想是從vs出發，逐步地向外探尋最短路，采用標號法。執行過程中，與每個點對應，記錄下一個數（稱為這個點的標號），它或者表示從vs到該點的最短路長（稱為P標號），或者是從vs到該點的最短路長的上界（稱為T標號）。算法每一步都把某個頂點的T標號改為P標號，當終點vt得到P標號時，計算結束。最多n-1步。最短路問題網絡圖的最短路圖的起點是vs，終點是vt，以vi為起點vj為終點的弧記為(i,j)，距離為dij。P標號(點標號)：b(j)—起點vs到點vj的最短路長；T標號(邊標號)：k(i,j)=b(i)+dij。最短路問題步驟：

2.找出所有vi已標號vj未標號的弧集合B={(i,j)}如果這樣的弧不存在或vt已標號則計算結束；3.計算集合B中弧k(i，j)=b(i)+dij的標號;4.選一個點標號在終點vl處標號b(l),返回到第2步。

1.令起點的標號；b(s)＝0。最短路問題求連接vs、vt

的最短路.0--∞-∞PT-∞-∞-∞-∞開始，給vs以P標號，P(vs)=0,其余各點給T標號T(vi)=+∞.227414731555vsv2v1vtv4v5v3Step1:

迭代1

Dijkstra算法基本步驟：例2最短路問題0--∞-∞-∞-∞-∞-∞若vi為剛得到

P標號的點,考慮這樣的點

vj

:(vi,vj)∈E

且vj

為

T標號。227414731555vsv2v1vtv4v5v3Step2:對vj的T標號進行如下更改T(vj)=min[T(vj),P(vi)+wij]245迭代1

考察vs,

T(v2)=min[T(v2),P(vs)+ws2]=min[+∞,0+5]=5T(v1)=min[T(v1),P(vs)+ws1]=min[+∞,0+2]=2最短路問題0--∞-∞-∞-∞-∞-∞比較所有具有T標號的點，把最小者改為P標號，227414731555vsv2v1vtv4v5v3Step3:245即

P(vi)=min[T(vi)].當存在兩個以上最小者時,可同時改為P

標號。若全部點為P標號,則停止。否則用vi代替vi轉step2.-2迭代1

全部T標號中,T(v1)最小,令P(v1)=2,記錄路徑(vs

,v1).最短路問題0-2--5-∞-∞-∞-4227414731555vsv2v1vtv4v5v394若vi為剛得到

P標號的點,考慮這樣的點

vj

:(vi,vj)∈E且vj

為

T標號。Step2:對vj的T標號進行如下更改T(vj)=min[T(vj),P(vi)+wij]迭代2

考察v1,

T(v4)=min[T(v4),P(v1)+w14]=min[+∞,2+7]=9T(v2)=min[T(v2),P(v1)+w12]=min[5,2+2]=4最短路問題0-2--4-9-∞-∞-4227414731555vsv2v1vtv4v5v344迭代2

比較所有具有T標號的點，把最小者改為P標號，Step3:即

P(vi)=min[T(vi)].--全部T標號中,T(v2),T(v3)最小,令P(v2)=4,P(v3)=4,記錄路徑(v1,v2),(v1,v4),.最短路問題0-2-4--9-∞-∞4-227414731555vsv2v1vtv4v5v37迭代3

若vi為剛得到

P標號的點,考慮這樣的點

vj

:(vi,vj)∈E且vj

為

T標號。Step2:對vj的T標號進行如下更改T(vj)=min[T(vj),P(vi)+wij]最短路問題0-2-4--9-∞-74-227414731555vsv2v1vtv4v5v37迭代3

比較所有具有T標號的點，把最小者改為P標號，Step3:即

P(vi)=min[T(vi)].-最短路問題0-2-4--9-∞7-4-227414731555vsv2v1vtv4v5v3迭代4

若vi為剛得到

P標號的點,考慮這樣的點

vj

:(vi,vj)∈E且vj

為

T標號。Step2:對vj的T標號進行如下更改T(vj)=min[T(vj),P(vi)+wij]814最短路問題0-2-4--8-147-4-227414731555vsv2v1vtv4v5v3迭代4

8-比較所有具有T標號的點，把最小者改為P標號，Step3:即

P(vi)=min[T(vi)].最短路問題0-2-4-8--147-4-227414731555vsv2v1vtv4v5v3迭代5

13若vi為剛得到

P標號的點,考慮這樣的點

vj

:(vi,vj)∈E且vj

為

T標號。Step2:對vj的T標號進行如下更改T(vj)=min[T(vj),P(vi)+wij]最短路問題0-2-4-8--137-4-227414731555vsv2v1vtv4v5v3迭代5

13比較所有具有T標號的點，把最小者改為P標號，Step3:即

P(vi)=min[T(vi)].當存在兩個以上最小者時,可同時改為P

標號。若全部點為P標號,則停止。否則用vi代替vi轉step2.-最短路問題0-2-4-8-13-7-4-227414731555vsv2v1vtv4v5v3最短路

Dijkstra算法不僅找到了所求最短路，而且找到了從vs

點到其他所有頂點的最短路；這些最短路構成了圖的一個連通無圈的支撐子圖，即圖的一個支撐樹。最短路問題從上例知，只要某點已標號，說明已找到起點vs到該點的最短路線及最短距離，因此可以將每個點標號，求出vs到任意點的最短路線，如果某個點vj不能標號，說明vs不可達vj

。最短路問題算法適用條件：Dijkstra算法只適用于全部權為非負情況，如果某邊上權為負的，算法失效。此時可采用逐次逼近算法。如右圖所示中按dijkstra算法可得P(v1)=5為從vs→v1的最短路長顯然是錯誤的，從vs→v2→v1路長只有3。v2vsv15-58最短路問題例2Ford算法基本思想：為逐次逼近的方法。每次求出從出發點v0到其余點的有限制的最短路，逐次放寬條件。即第一次逼近是找v0到vn的最短路，但限于最短路只允許有一條邊（弧），其距離記為d1(v0,vn).簡記為d1(vn)。第二次逼近，再找v0到vn的最短路，其限制條件放寬到允許最短路不超過兩條邊（弧），其距離記為d2(vn)。到第m次逼近,dm(vn)表示由v0到vn的不超過m條邊（弧）組成的最短路的距離。最多p-1次。網絡有負權的最短路最短路問題2-2-2311v0v2v1v3Ford算法基本步驟：(1)令m=1,令d1(v0)=0,d1(vi)=w(v0,vi).解：①

d1(v0)=0,d1(v1)=2,d1(v2)=1,d1(v3)=-2.021-2第一次逼近最短路問題2-2-2311v0v2v1v3(2)令解：②

d2(v1)=min{d1(v1)+w(v1,v1),d1(v2)+w(v2,v1),d1(v3)+w(v3,v1)}021-2當vi,v為同一個點時，有w(v

,vi)=0.=min{2+0,1+∞,-2+3}=1.1d2(v2)=min{d1(v1)+w(v1,v2),d1(v2)+w(v2,v2),d1(v3)+w(v3,v2)}=min{2-2,1+0,-2+∞}=0.0d2(v3)=min{d1(v1)+w(v1,v3),d1(v2)+w(v2,v3),d1(v3)+w(v3,v3)}=min{2+∞,1+1,-2+0}=-2.第二次逼近(3)若m+1=p則停止。否則m=m+1,轉(2).最短路問題2-2-2311v0v2v1v3解：③

d3(v1)=min{d2(v1)+w(v1,v1),d2(v2)+w(v2,v1),d2(v3)+w(v3,v1)}010-2=min{1+0,0+∞,-2+3}=1.d3(v2)=min{d2(v1)+w(v1,v2),d2(v2)+w(v2,v2),d2(v3)+w(v3,v2)}=min{1-2,0+0,-2+∞}=-1.-1d3(v3)=min{d2(v1)+w(v1,v3),d2(v2)+w(v2,v3),d2(v3)+w(v3,v3)}=min{1+∞,0+1,-2+0}=-2.第三次逼近(2)令當vi,v為同一個點時，有w(v

,vi)=0.(3)若m+1=p則停止。否則m=m+1,轉(2).最短路問題2-2-2311v0v2v1v3最后解得：d3(v1)=1，d3(v2)=-1，d3(v3)=-2.01-1-2即v0到v1最短路長度為

d3(v1)=1，最短路為v0,v3,v1.即v0到v2最短路長度為

d3(v2)=-1,最短路為v0,v3,v1,v2.即v0到v3最短路長度為

d3(v3)=-2,最短路為v0,v3.最短路問題Ford算法基本步驟：(1)令m=1,令d1(v0)=0,d1(vi)=w(v0,vi).(2)令當vi,v為同一個點時，有w(v

,vi)=0.(3)若m+1=p則停止。否則m=m+1,轉(2).最短路問題某些問題中，要求網絡上任意兩點間的最短路。這類問題可以用Dijkstra算法依次改變起點的辦法計算，但比較繁瑣。而F1oyd方法(1962年)可直接求出網絡中任意兩點間的最短路。令網絡的權矩陣為三、Floyd算法其中最短路問題權矩陣：v1v2v4v3v55122310284462圖中有四條無向邊，每條均可化為兩條方向相反的有向邊。則得權矩陣為：最短路問題(1)輸入權矩陣D(0)=D;(2)計算其中(3)中元素Floyd算法基本步驟：就是vi到vj的最短路長.最短路問題計算實例：求圖中任意兩點間的最短路。解:(1)輸入權矩陣D(0)=D.v1v2v4v3v55122310284462最短路問題(2)計算其中計算如：其中0512∞506722302827304∞2440v1v2v4v3v55122310284462其中表示從vi點到vj點或直接有邊或借v1點為中間點時的最短路長。最短路問題其中表示從vi點到vj點最多經中間點v1,v2的最短路長。(2)計算其中計算最短路問題其中表示從vi點到vj點最多經中間點v1,v2,v3的最短路長。(2)計算其中計算最短路問題其中表示從vi點到vj點最多經中間點v1,v2,v3,v4,v5計算的所有路中的最短路長。所以D(5)就給出了任意兩點間不論幾步到達的最短路長。如果還希望給出具體的最短路經，則在運算過程中要保留下標信息，即等等。如在D(1)中的是由得到的，所以可以寫成.而D(2)中的是由得到的，所以可以寫成.最短路問題而D(2)中的是由得到的，所以可以寫成.而D(3)中的是由得到的，而所以可以寫成等.最短路問題由此v1v2v4v3v55122310284462最短路問題最短路問題的應用：電信公司準備準備在甲、乙兩地沿路架設一條光纜線，問如何架設使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權數表示兩地間公路的長度（單位：公里）。

v1（甲地）1517624431065v2v7(乙地)v3v4v5v6最短路問題例3設備更新問題某工廠使用一臺設備，每年年初工廠都要作出決定．如果繼續使用舊的，要付維路費；若購買一臺新設備，要付購買費。試制定一個5年的更新計劃，使總支出最少。若已知設備在各年年初的價格為：還知使用不同年數的設備所需要的維修費用為：例4年度第1年第2年第3年第4年第5年購買費1111121213使用年數0-11-22-33-44-5維修費用5681118最短路問題可供選則的設備更新方案是很多的。例如，每年都購置一臺新設備，則其購置費用為11+11+12+12+13=59，而每年支付的維修費用為5，五年合計為25，于是五年總的支付費用為59+25=84。又如，決定在第一、三、五年各購進一臺新設備，則其購置費用為11+12+13=36，維修費用為5+6+5+6+5=27，于是五年總的支付費用為36+27=63。年度第1年第2年第3年第4年第5年購買費1111121213使用年數0-11-22-33-44-5維修費用5681118最短路問題可把這個問題化為最短路問題。用點vi表示第i年年初購進一臺新設備．虛設一個點v6,表示第五年年底。弧(vi,vj)表示第i年初購進的設備一直使用到第j年年初(即第j-1年年底).v1v2v3v4v5v6最短路問題弧(vi,vj)上的數字表示第i年初購進設備，一直使用到第j年初所需支付的購買、維修的全部費用.例如(v1

,v4):購置費11，維修費5+6+8=19，總計30.v1v2v3v4v5v6161617171830412322312359413022年度第1年第2年第3年第4年第5年購買費1111121213使用年數0-11-22-33-44-5維修費用5681118最短路問題這樣設備更新問題就變為：求從v１到v6的最短路。求解得：{v1

,v3

,

v6

}及{v1

,v4

,

v6

}均為最短路。總的支付費用均為53。v1v2v3v4v5v6161617171830412322312359413022最短路問題8.4網絡最大流如何制定一個運輸計劃使生產地到銷售地的產品輸送量最大。這就是一個網絡最大流問題。網絡最大流不同網絡中流的意義不同，流本身是一種輸送，可以把它們統稱為運輸網絡的流。許多系統包含了流量問題。例如在交通運輸網絡中有人流、車流、貨物流；供水網絡中有水流；金融系統中有現金流；通訊系統中有信息流，等等.8528796653vsv1vtv4v3v2網絡最大流管道網絡中每邊的最大通過能力即容量是有限的，實際流量也并不一定等于容量，上述問題就是要討論如何充分利用裝置的能力．以取得最好效果(流量最大)，這類問題通常稱為最大流問題。50年代福持(Ford)、富克遜(Fulkerson)建立的“網絡流理論”，是網絡應用的重要組成部分。8528796653vsv1vtv4v3v2網絡最大流

1.容量網絡：隊網絡上的每條弧(vi,vj)都給出一個最大的通過能力，稱為該弧的容量，簡記為cij。容量網絡中通常規定一個發點(也稱源點，記為s)和一個收點(也稱匯點，記為t)，網絡中其他點稱為中間點。s①②③④t4844122679基本概念網絡最大流2.網絡的最大流

是指網絡中從發點到收點之間允許通過的最大流量。3.

流與可行流流是指加在網絡各條弧上的實際流量，對加在弧(vi,vj)上的負載量記為fij。若fij=0，稱為零流。滿足以下條件的一組流稱為可行流。容量限制條件。容量網絡上所有的弧滿足：0≤fij≤cij

中間點平衡條件。若以v(f)表示網絡中從s→t的流量，則有：網絡最大流結論：任何網絡上一定存在可行流。（零流即是可行流）網絡最大流問題： 指滿足容量限制條件和中間點平衡的條件下，使v(f)值達到最大。網絡最大流最大流問題實際是個線性規劃問題，但是利用它與圖的緊密關系，能更為直觀簡便地求解。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2v(f)=7.網絡最大流割與割集割是指容量網絡中的發點和收點分割開，并使s→t的流中斷的一組弧的集合。割容量是組成割集合中的各條弧的容量之和，用表示。網絡最大流(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2割集網絡最大流網絡的割集有多個，其中割集容量最小者稱為網絡的最小割集容量(簡稱最小割)。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2網絡最大流如下圖中，AA′將網絡上的點分割成兩個集合。并有，稱弧的集合{(v1,v3),(v2,v4)}是一個割，且的流量為18。●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AA’BB’網絡最大流定理1

設網絡N中一個從s到t

的流f的流量為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)不大于最小割集的容量，即：v＊

(f)min{c(V,V′)}定理2

在網絡中s→t的最大流量等于它的最小割集的容量，即：v＊

(f)=c＊(V,V′)網絡最大流增廣鏈 在網絡的發點和收點之間能找到一條鏈，在該鏈上所有指向為s→t的弧，稱為前向弧，記作μ+,存在f<c；所有指向為t→s的弧，稱為后向弧，記做μ－，若f>0，則稱這樣的鏈為增廣鏈。定理3

網絡N中的流f

是最大流當且僅當N中不包含任何增廣鏈網絡最大流一個可行流f={fij}，稱fij=

cij的弧為飽和弧，稱fij<cij的弧為不飽和弧.

fij=

0的弧為零流弧，fij>

0的弧為非零流弧.(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2飽和弧零流弧不飽和弧網絡最大流設P是網絡D的一條連接源點vs和匯點vt的鏈，定義鏈P的方向是從vs到vt

，前向弧—弧的方向與P的方向一致；全體記為P

+.后向弧—弧的方向與P的方向相反；全體記為P

-.鏈P：(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2注：鏈不是有向路，鏈的每一邊去掉方向是一條路.則P中的弧可分為兩類：網絡最大流f

是一個可行流，P是從vs到vt的一條鏈，如果(1)P的每一前向弧都是不飽和弧（）;(2)P的每一后向弧都是非零流弧（）；則稱P是網絡D的關于可行流f

的一條增廣鏈。簡稱增廣鏈。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2增廣鏈P：網絡最大流●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)例如下圖中，s→v2→v1→v3→v4→t。網絡最大流求網絡最大流的標號算法：Ford-Fulkerson

算法[基本思想]

由一個流開始，系統地搜尋增廣鏈，然后在此鏈上增流，繼續這個增流過程，直至不存在增廣鏈。[基本方法]找出第一個可行流，（例如所有弧的流量fij=0。）用標號的方法找一條增廣鏈首先給發點s標號(∞),標號中的數字表示允許的最大調整量。選擇一個點vi

已標號并且另一端未標號的弧沿著某條鏈向收點檢查：網絡最大流如果弧的起點為vi，并且有fij<Cij，則給vj標號為(Cij－fij)

如果弧的方向指向vi，并且有fji>0，則vj標號(fji)(3)重復第(2)步，可能出現兩種結局：標號過程中斷，t無法標號，說明網絡中不存在增廣鏈，目前流量為最大流。同時可以確定最小割集，記已標號的點集為V,未標號的點集合為V′,(V,V′)為網絡的最小割。

t得到標號，反向追蹤在網絡中找到一條從s到t得由標號點及相應的弧連接而成的增廣鏈。繼續第(4)步網絡最大流(4)修改流量。設原圖可行流為f，令得到網絡上一個新的可行流f′。(5)擦除圖上所有標號，重復(1)-(4)步，直到圖中找不到任何增廣鏈，計算結束。網絡最大流8528796653vsv1vtv4v3v2算例：求下面網絡的最大流。網絡最大流(0,8)(0,5)(0,2)(0,8)(0,7)(0,9)(0,6)(0,6)(0,5)(0,3)vsv1vtv4v3v2(1)給網絡賦一個初始0流f0；給vs標號(-,∞);(-,∞)(a)對弧(vi,vk),若,則給vk

標號(+vi,l(vk)),其中(b)對弧(vk,vi),若,則給vk

標號(-vi,l(vk)),其中標號過程1(+vs,8)(+vs,2)(+v1,5)(+v3,2)(+v2,5)找到流f0

的增廣鏈P0=vsv1v2vt，網絡最大流(0,8)(0,5)(0,2)(0,8)(0,7)(0,9)(0,6)(0,6)(0,5)(0,3)vsv1vtv4v3v2(-,∞)調整過程1(+vs,8)(+vs,2)(+v1,5)(+v3,2)(+v2,5)找到流f0

的增廣鏈P0=vsv1v2vt，2.調整流量調整量θ=5.555調整流值得流值為5的新可行流f1.網絡最大流(5,8)(5,5)(0,2)(0,8)(0,7)(5,9)(0,6)(0,6)(0,5)(0,3)vsv1vtv4v3v2給vs標號(-,∞);(-,∞)(a)對弧(vi,vk),若,則給vk

標號(+vi,l(vk)),其中(b)對弧(vk,vi),若,則給vk

標號(-vi,l(vk)),其中標號過程2(+vs,3)(+vs,2)(+v3,2)(+v3,2)(+v2,2)找到流f1

的增廣鏈P1=vsv3v2vt，得新可行流f1

，重新進入標號過程.網絡最大流(5,8)(5,5)(0,2)(0,8)(0,7)(5,9)(0,6)(0,6)(0,5)(0,3)vsv1vtv4v3v2(-,∞)調整過程2(+vs,3)(+vs,2)(+v3,2)(+v3,2)(+v2,2)找到流f1

的增廣鏈P1=vsv3v2vt，2.調整流量調整量θ=2.2調整流值得流值為7的新可行流f2.27網絡最大流(5,8)(5,5)(2,2)(0,8)(0,7)(7,9)(0,6)(0,6)(2,5)(0,3)vsv1vtv4v3v2給vs標號(-,∞);(-,∞)(a)對弧(vi,vk),若,則給vk

標號(+vi,l(vk)),其中(b)對弧(vk,vi),若,則給vk

標號(-vi,l(vk)),其中標號過程3(+vs,3)(+v1,3)(+v3,3)(+v3,3)(+v4,3)找到流f2

的增廣鏈P2=vsv1v3v4vt，得新可行流f2

，重新進入標號過程.網絡最大流(5,8)(5,5)(2,2)(0,8)(0,7)(7,9)(0,6)(0,6)(2,5)(0,3)vsv1vtv4v3v2(-,∞)調整過程3(+vs,3)(+v1,3)(+v3,3)(+v3,3)(+v4,3)找到流f2

的增廣鏈P2=vsv1v3v4vt，2.調整流量調整量θ=3.8調整流值得流值為10的新可行流f3.333網絡最大流(8,8)(5,5)(2,2)(3,8)(3,7)(7,9)(3,6)(0,6)(2,5)(0,3)vsv1vtv4v3v2給vs標號(-,∞);(-,∞)(a)對弧(vi,vk),若,則給vk

標號(+vi,l(vk)),其中(b)對弧(vk,vi),若,則給vk

標號(-vi,l(vk)),其中標號過程4得新可行流f3

，重新進入標號過程.標號無法進行,說明f3已是最大流，流值10.令S={vs},則(S,S)是最小割.網絡最大流用標號算法求下圖中s→t的最大流量，并找出最小割。●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)例5網絡最大流解：(1)先給s標號(∞)●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(∞)網絡最大流●stv1v3v2v48(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,(1)網絡最大流●stv1v3v2v48(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)網絡最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)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)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)(∞)(1)(1)(1)網絡最大流(5)擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。●stv1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7(5)(∞)(1)(1)(1)網絡最大流(5)擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。●stv1v3v2v48(8)9(4)5(5)10(8)6(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)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(∞)(2)(2)(2)(1)(1)網絡最大流●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)(∞)(2)(2)(2)(1)(1)(7)擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。網絡最大流●stv1v3v2v48(8)9(5)5(5)10(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網絡最大流例6.9求下圖s→t的最大流，并找出最小割stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●網絡最大流stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●解:(1)在已知可行流的基礎上，通過標號尋找增廣鏈。(∞)ε(2)=min{∞,6}=6(6)ε(3)=min{6,2}=2(2)ε(t)=min{2,5}=2(2)存在增廣鏈s→v2→v3→t網絡最大流(2)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●(∞)(6)(2)(2)網絡最大流(3)擦除原標號，重新搜尋增廣鏈。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)(6)(2)(2)網絡最大流(4)重新搜尋增廣鏈。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)ε(2)=min{∞,4}=4(4)(1)ε(5)=min{4,1}=1ε(3)=min{1,2}=1(1)(1)ε(t)=min{1,3}=1存在增廣鏈：s→v2→v5→v3→t網絡最大流(5)修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)(4)(1)(1)(1)網絡最大流(6)擦除原標號stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(4)(1)(1)(1)網絡最大流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(1)(1)(1)ε(5)=min{∞,1}=1ε(5)=min{1,1}=1ε(5)=min{1,2}=1(7)重新搜尋增廣鏈。存在增廣鏈：s→v5→v3→t網絡最大流(8)調整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(1)(1)(1)網絡最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(∞)(1)(1)(1)(9)擦除原標號網絡最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(10)重新標號，搜索增廣鏈(∞)ε(1)=min{∞,1}=1(1)ε(5)=min{1,1}=1(1)ε(4)=min{1,1}=1(1)ε(t)=min{1,1}=1(1)存在增廣鏈：s→v1→v5→v4→t網絡最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(∞)(1)(1)(1)(1)(11)調整增廣鏈上的流量，非增廣鏈流量不變，得到新的可行流網絡最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)●(∞)(1)(1)(1)(1)(11)擦除標號，在新的可行流上重新標號。網絡最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)●(∞)(11)擦除標號，在新的可行流上重新標號。(3)ε(1)=min{∞,3}=1無法標號，不存在增廣鏈，此可行流已為最大流。最大流量為14。網絡最大流第9章網絡計劃1網絡計劃圖2時間參數計算3網絡計劃的優化用網絡分析的方法編制的計劃稱為網絡計劃技術,

是20世紀50年代末發展起來的一種編制大型工程進度計劃的有效方法。網絡計劃是運用工程網絡圖來表達計劃的內容及其相互之間的關系，通過分析、計算找到整個計劃的主要矛盾、關鍵環節，然后進行調整，以求得完工日期、技術資源及成本的優化方案。主要內容有關鍵路線法(criticalpathmethod,縮寫為CPM)，計劃評審方法(programevaluation&reviewtechnique，縮寫為PERT)等．我國已故著名數學家華羅庚先生將這些方法總結概括稱為統籌方法．在60年代初引入我國．而且身體力行地進行推廣應用。目前，這些方法被世界各國廣泛應用于工業、農業、國防、科研等計劃管理中，對縮短工期、節約人力、物力和財力，提高經濟效益發揮了重要作用.在制定企業不同業務部門的系統規劃時，制定網絡計劃，并找出在編制計劃時及計劃執行過程中的關鍵路線的方法，稱為關鍵路線法(CPM).計劃評審方法(PERT)側重于用網絡分析與網絡計劃的方法對各項工作安排的評價和審查等．編制網絡計劃包括繪制網絡圖，計算時間參數，確定關鍵路線及網絡優化等環節。基本術語及繪制網絡圖規則網絡圖是由結點、弧及權所構成的有向圖。弧表示一個工序，結點表示一個事項。工序：為了完成工程項目，在工程技術和組織管理上相對獨立的工作或活動(消耗時間或資源)．用a

表示.(一)網絡圖9.1、網絡計劃圖事項：工序的開始或結束為事項，是相鄰工序在時間上的分界點。用有標號的結點i表示。工程的開始事項稱為最初事項，標號為①，工程的結束事項為最終事項，標號為n.權：一個工序所消耗的時間、資源等數據為權。通常標注在弧的下方或其他合適的位置上。12467835abcfdgekhl60101820253035404515例：如圖就是一項研制新產品工程的網絡圖。箭尾事項、箭頭事項.(二)、畫圖注意事項：(1)、網絡圖只能有一個開始事項，一個結束事項.方向：整個圖的方向遵循從左向右的原則；編號：同一工序箭尾事項的編號小于箭頭事項的編號．12345678cabdefg(2)、兩事項間只有一個工序5ijcba3(3)、不允許回路123(4)、緊前工序與緊后工序12467835abcfdgekhl60101820253035404515a為b,c,d,e的緊前工序；b,c,d,e

為a的緊后工序.必須正確表示工序間的緊前、緊后關系如4道工序a,b,c,d的關系為：c必須在a,b均完成后才能開工，而d只要在b完工后即可開工，如畫成下圖是錯誤的，因本來與a工序無關的工序d被錯誤地表為必須在a完成后才能開工。12435acbd(5)、虛工序②正確表達工序的緊前、緊后關系①解決畫法中問題為了表達相鄰工序之間的銜接關系，而虛設的工序，稱為虛工序。不消耗資源。ij0③

表達平行作業④

表達交叉作業00012346578cabedfg①解決畫法中問題0ijkc5a3b5ijcba30例1、a,b,c,d四個工序，c在a,b完工后開始，d在b完工后開始。cabdabcd②正確表達工序的緊前、緊后關系例2、已知ABCEADC例2、答案ABDCE③

表達平行作業abc12acb344b2b14一道工作分為幾道工作同時進行，稱為平行工作.④

表達交叉作業ab96a1a2a3b1b2b3a