圖與網絡計劃評審方法(六七章)jsp

1、2022-3-23-第6章 圖與網絡分析-1-第六章 圖與網絡分析 圖是一種模型，如公路、鐵路交通圖， 通訊網絡圖等。 圖示對現(xiàn)實的抽象，以點和線段的連接組合表示。2022-3-23-第6章 圖與網絡分析-2- 1圖的基本概念與模型圖的基本概念與模型 2樹圖和圖的最小部分樹樹圖和圖的最小部分樹 3最短路問題最短路問題 4網絡的最大流網絡的最大流 5最小費用流最小費用流2022-3-23-第6章 圖與網絡分析-3-BACD 當地的居民熱衷于這當地的居民熱衷于這樣一個問題：樣一個問題：一個漫步者如何能夠走過一個漫步者如何能夠走過這七座橋，并且每座橋只這七座橋，并且每座橋只能走過一次，最終回到原能走

2、過一次，最終回到原出發(fā)地。出發(fā)地。盡管試驗者很多，盡管試驗者很多，但是都沒有成功。但是都沒有成功。2022-3-23-第6章 圖與網絡分析-4-4歐拉用歐拉用A A、B B、C C、D D四點表示四點表示河的兩岸和小島，用兩點間的聯(lián)河的兩岸和小島，用兩點間的聯(lián)線表示橋，如右下圖所示，該問線表示橋，如右下圖所示，該問題可歸結為：題可歸結為：能否從某一點出發(fā)，一筆畫能否從某一點出發(fā)，一筆畫出這個圖形，最后回到出發(fā)點而出這個圖形，最后回到出發(fā)點而不重復？即一筆畫問題。不重復？即一筆畫問題。ACBDBCDA歐拉在歐拉在17861786年發(fā)表了年發(fā)表了題為題為“依據幾何位置依據幾何位置的解題方法的解題方

3、法”的的論文，解決了著名的哥尼斯堡論文，解決了著名的哥尼斯堡七橋問題七橋問題歐拉證明了上述圖形一筆劃是不可能的，歐拉證明了上述圖形一筆劃是不可能的，因為圖中每一個點都只和奇數條線相關聯(lián)因為圖中每一個點都只和奇數條線相關聯(lián)他的結論是：圖形能一筆畫的充要條件是圖形的奇頂點（連接他的結論是：圖形能一筆畫的充要條件是圖形的奇頂點（連接奇數條線的頂點）的個數為零奇數條線的頂點）的個數為零2022-3-23-第6章 圖與網絡分析-5- 在實際的生產和生活中，人們?yōu)榱朔从呈挛镏g的關系，在實際的生產和生活中，人們?yōu)榱朔从呈挛镏g的關系，常常在紙上用點和線來畫出各式各樣的示意圖。常常在紙上用點和線來畫出各式各

4、樣的示意圖。例例 有六支球隊進行足球比賽，我們分別用點有六支球隊進行足球比賽，我們分別用點v v1 1v v6 6 表表示這六支球隊，它們之間的比賽情況，也可以用圖反示這六支球隊，它們之間的比賽情況，也可以用圖反映出來，已知映出來，已知v v1 1 隊戰(zhàn)勝隊戰(zhàn)勝v v2 2 隊，隊，v v2 2 隊戰(zhàn)勝隊戰(zhàn)勝v v3 3隊，隊，v v3 3 隊戰(zhàn)隊戰(zhàn)勝勝v v5 5 隊，如此等等。這個勝負情況，可以用下圖所示隊，如此等等。這個勝負情況，可以用下圖所示的有向圖反映出來。的有向圖反映出來。2022-3-23-第6章 圖與網絡分析-6-6在自然界和人類的實際生活中，常用點和點與點之間的在自然界和人類

5、的實際生活中，常用點和點與點之間的聯(lián)線所構成的圖，來反映某些研究對象和對象之間的某種聯(lián)線所構成的圖，來反映某些研究對象和對象之間的某種特定的關系。如：特定的關系。如：為了反映城市之間有沒有航為了反映城市之間有沒有航班，我們可用右圖表示。甲城與班，我們可用右圖表示。甲城與乙城，乙城與丙城有飛機到達，乙城，乙城與丙城有飛機到達，而甲、丙兩城沒有直飛航班。而甲、丙兩城沒有直飛航班。甲甲乙乙丙丙甲甲乙乙丙丙工人工人ABC工作工作6.1 圖的基本概念和模型 對于工作分配問題，我們可能對于工作分配問題，我們可能用點表示工人與需要完成的工作，用點表示工人與需要完成的工作，點間連線表示每個工人可以勝任哪點間連

6、線表示每個工人可以勝任哪些工作如右圖所示。些工作如右圖所示。2022-3-23-第6章 圖與網絡分析-7-(v1)趙(v2)錢孫(v3) 李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5可見圖論中的圖與幾何圖、工程圖是不一樣的。可見圖論中的圖與幾何圖、工程圖是不一樣的。例如：在一個人群中，對相互認識這個關系我們可以用圖來表示。2022-3-23-第6章 圖與網絡分析-8-一、概念（1）圖：點V和邊E的集合，用以表示對某種現(xiàn)實事物的抽象。記作 G=V,E,V=v1,v2,vn, E=e1,e2,

7、em點：表示所研究的事物對象； 邊：表示事物之間的聯(lián)系。v1v2v3v4v0e1e2e3e4e5e6e7e0（2）若邊e的兩個端點重合，則稱e為環(huán)。（3）多重邊：若某兩端點之間多于一條邊，則稱為多重邊。 給圖中的點和邊賦以具體的含義和權值，我們稱這樣的給圖中的點和邊賦以具體的含義和權值，我們稱這樣的圖為圖為網絡圖網絡圖（賦權圖）（賦權圖）2022-3-23-第6章 圖與網絡分析-9-9 無向圖：無向圖：G= V,E1 14 43 32 2e e1 1e e5 5e e6 6e e4 4e e3 3e e2 2e e7 71234V =v ,v,v,v1234567E= e ,e ,e ,e ,

8、e ,e ,e112212323434514613744e= v,v,e = v,v,e = v ,v,e = v,v,e = v,v,e = v,v,e = v ,v2022-3-23-第6章 圖與網絡分析-10-10有向圖：有向圖：D= V,A111221333243452464574685395410561167a = v,v,a = v,v,a = v,v,a = v,v,a = v ,v,a = v ,v,a = v ,v,a = v ,v , a = v ,v,a = v ,va = v ,v1234567V= v ,v ,v ,v ,v ,v ,v12311A= a ,a ,a

9、,a324567a1a2a3a4a6a5a7a8a9a10a112022-3-23-第6章 圖與網絡分析-11-（4）簡單圖：無環(huán)、無多重邊的圖稱為簡單圖。（5）鏈：點和邊的交替序列，其中點可重復，但邊不能重復。（6）路：點和邊的交替序列，但點和邊均不能重復。（7）圈：始點和終點重合的鏈。（8）回路：始點和終點重合的路。（9）連通圖：若一個圖中，任意兩點之間至少存在一條鏈，稱這樣的圖為連通圖。（10）子圖，部分圖：設圖G1=V1,E1, G2=V2,E2, 如果有V1V2，E1E2，則稱G1是G2的一個子圖；若V1=V2，E1E2，則稱G1是G2的一個部分圖。（11）次：某點的關聯(lián)邊的個數稱為

10、該點的次，以d(vi)表示。2022-3-23-第6章 圖與網絡分析-12-次，奇點，偶點，孤立點次，奇點，偶點，孤立點 某點的某點的次次也稱為也稱為度、線度度、線度。次為奇數的點稱為。次為奇數的點稱為奇點奇點，次，次為偶數的點稱為為偶數的點稱為偶點偶點，次為零的點稱為，次為零的點稱為孤立點，孤立點，次為次為1的點的點稱為稱為懸掛點懸掛點。如圖：如圖：奇點為奇點為 v v5 5 ， v v3 3偶點為偶點為 v v1 1 , , v v2 2 , , v v4 4 , , v v6 6孤立點為孤立點為 v6懸掛點為懸掛點為 v52022-3-23-第6章 圖與網絡分析-13- 有向圖中，以vi

11、為始點的邊數稱為點vi的出次，用d+(vi)表示；以vi為終點的邊數稱為點vi 的入次，用表示d-(vi) ；vi 點的出次和入次之和就是該點的次。 有向圖中，所有頂點的入次之和等于所有頂點的出次之和。圖的次: 一個圖的次等于各點的次之和。定理定理 圖圖 中，所有頂點的次之和等于所有邊數的中，所有頂點的次之和等于所有邊數的2 2倍，倍， 即即G= V,Ev Vd(v)=2q2022-3-23-第6章 圖與網絡分析-14-鏈，圈，路，回路，連通圖鏈，圈，路，回路，連通圖35264734221,vevevevevev鏈鏈4734221,vevevev路路,1335264734221veveveve

12、vevev圈圈子圖：子圖：部分圖部分圖注意：注意：部分圖也是子圖，但子圖部分圖也是子圖，但子圖不一定是部分圖。不一定是部分圖。回路回路1224331,v e v e v e v15（1 1）開鏈和閉鏈：如果）開鏈和閉鏈：如果 ，則該鏈稱為開鏈；如果，則該鏈稱為開鏈；如果 ，則該鏈稱為閉鏈（或稱為圈）。則該鏈稱為閉鏈（或稱為圈）。（2 2）簡單鏈和初等鏈：如鏈內所含的邊均不相同，稱之為簡單鏈；如）簡單鏈和初等鏈：如鏈內所含的邊均不相同，稱之為簡單鏈；如鏈內所含的點均不相同，稱之為初等鏈。鏈內所含的點均不相同，稱之為初等鏈。 如：如：1niivv1niiv = v12345367v ,v,v,v,

13、v,v,v,v是簡單鏈，是簡單鏈，12367v ,v,v,v,v是初等鏈，是初等鏈，12341v ,v,v,v,v是初等圈，是初等圈，412357634v,v ,v,v,v,v,v,v,v是簡單圈，是簡單圈，1243567e1e2e3e8e4e7e6e5e916 賦權圖賦權圖：設圖：設圖 , ,若對其邊集若對其邊集E E定義了一個實值函數定義了一個實值函數 ， , ,則稱該圖為一個賦權圖。記作則稱該圖為一個賦權圖。記作 。 稱稱 為邊為邊 的權。的權。 如某工廠內連接六個車間的道路網如入所示，已知每條路長，要求沿道路如某工廠內連接六個車間的道路網如入所示，已知每條路長，要求沿道路架設連接六個車

14、間的電話線路，使電話總長最短。架設連接六個車間的電話線路，使電話總長最短。123456652715344左圖為一賦權圖左圖為一賦權圖最優(yōu)解：如紅線所示，最優(yōu)解：如紅線所示，電話總長電話總長15個單位。個單位。紅線所示為圖的最小紅線所示為圖的最小支撐樹支撐樹G= V,Eijijw v ,v, v ,vEG= V,E,ijw v ,vijv ,v17 網絡圖：網絡圖：若若 為一賦權圖為一賦權圖 ，并在其頂點集合，并在其頂點集合V V中指中指定了起點（或稱發(fā)點）和終點（或稱收點），其余的點為中間點，這樣定了起點（或稱發(fā)點）和終點（或稱收點），其余的點為中間點，這樣的賦權圖稱為網絡圖（簡稱網絡）。記作

15、的賦權圖稱為網絡圖（簡稱網絡）。記作 。 網絡一般是連通的賦權圖。網絡一般是連通的賦權圖。 若一個網絡圖中的每條邊都是有向的弧，則稱之為有向網絡，記作若一個網絡圖中的每條邊都是有向的弧，則稱之為有向網絡，記作 G= V,E,N= V,E,N= V,A,9102015714192562022-3-23-第6章 圖與網絡分析-18-二、圖的模型 例：有甲、乙、丙、丁、戊、己六名運動員報名參加A、B、C、D、E、F六個項目的比賽。如表中所示，打“”的項目是各運動員報名參加比賽的項目。問：六個項目的比賽順序應如何安排，才能做到使每名運動員不連續(xù)地參加兩項比賽？甲 乙 丙 丁 戊 己項目人A B C D

16、 E F 2022-3-23-第6章 圖與網絡分析-19-建立模型：解：項目作為研究對象，排序。設 點：表示運動項目。邊：若兩個項目之間無無同一名運動員參加。ABCDEFACDEFBAFEDCBACBFEDAFBCDE順序：一個班級的學生共計選修A、B、C、D、E、F六門課程，其中一部分人同時選修D、C、A，一部分人同時選修B、C、F，一部分人同時選修B、E，還有一部分人同時選修A、B，期終考試要求每天考一門課，六天內考完，為了減輕學生負擔，要求每人都不會連續(xù)參加考試，試設計一個考試日程表。以每門課程為一個頂點，共同被選修的課程之間用邊相連，得圖，按題意，相鄰頂點對應課程不能連續(xù)考試，不相鄰頂

17、點對應課程允許連續(xù)考試，因此，作圖的補圖，問題是在圖中尋找一條哈密頓道路，如，就是一個符合要求的考試課程表。2022-3-23-第6章 圖與網絡分析-24-6.2 樹圖和圖的最小部分樹（1）樹圖： 無圈的連通圖稱為樹圖，簡稱為樹。記為T（V，E）一、樹圖的概念樹是圖論中結構最簡單但又十分重要的圖。在自然和社會領域應用極為廣泛。乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如下圖所示。AB CDEF GH運動員 某企業(yè)的組織機構圖也可用樹圖表示。廠長廠長人事科人事科財務科財務科總工總工程師程師生產副生產副廠長廠長經營副經營副廠長廠長開發(fā)科開發(fā)科技術科技術科生產科生產科設備科設備科供應科供應科銷售科

18、銷售科檢驗科檢驗科動力科動力科2022-3-23-第6章 圖與網絡分析-27-（2）樹圖的性質性質1：任何樹中必存在次為1的點。性質2：具有n個頂點的樹的邊數恰好為n-1條。性質3：任何具有n個點、n-1條邊的連通圖必為樹圖。比如有六個頂點的樹有比如有六個頂點的樹有6 6種種2022-3-23-第6章 圖與網絡分析-28-性質4：樹是邊數最多的無圈連通圖。在樹中任加一 條邊，就會形成圈。性質5：樹是邊數最少的連通圖。在樹中任減一條邊，則不連通。二、圖的最小部分樹：二、圖的最小部分樹：1圖的部分樹：若G1是G2的一個部分圖，且為樹圖，則稱G1是G2的一個部分樹。G2：ABCD547365576G

19、1：ACBD2022-3-23-第6章 圖與網絡分析-29-2圖的最小部分樹：樹枝總長為最短的部分樹稱為圖的最小部分樹（或最小支撐樹） 。樹枝：樹圖中的邊稱為樹枝。2022-3-23-第6章 圖與網絡分析-34-三、最小部分樹的求法定理1：圖中任一個點i，若j是與i相鄰點中距離最近的點，則邊i，j一定在其最小部分樹內。推論：將圖中所有的點分成V和V兩個集合，則兩個集合之間連線最短的一個邊一定包含在最小部分樹內。2022-3-23-第6章 圖與網絡分析-35-SABCDET252414317557最小部分樹長Lmin=14例：要在下圖所示的各個位置之間建立起通信網絡，試確定使總距離最佳的方案。2

20、022-3-23-第6章 圖與網絡分析-36-1. 避圈法：將圖中所有的點分V為V兩部分，V最小部分樹內點的集合V非最小部分樹內點的集合 任取一點vi加粗，令viV， 取V中與V相連的邊中一條最短的邊(vi,vj)， 加粗(vi,vj)，令vjV 重復 ，至所有的點均在V之內。2. 破圈法： 任取一圈，去掉其中一條最長的邊， 重復，至圖中不存在任何的圈為止。v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5樹與圖的最小樹部分樹2022-3-23-第6章 圖與網絡分析-40-SABCDET252414317557最小部分樹長Lmin=1437

21、49346321Min C(T)=12Min C(T)=15254173314475答案：6.3 最短路問題 如何用最短的線路將三部電話連起來？ 此問題可抽象為設ABC為等邊三角形，連接三頂點的路線（稱為網絡）。這種網絡有許多個，其中最短路線者顯然是二邊之和（如ABAC）。ABCABCP但若增加一個周轉站（新點P），連接4點的新網絡的最短路線為PAPBPC。最短新路徑之長N比原來只連三點的最短路徑要短。這樣得到的網絡不僅比原來節(jié)省材料，而且穩(wěn)定性也更好。最短路問題 問題描述：就是從給定的網絡圖中找出一點到各點或任意兩點之間距離最短的一條路 .有些問題，如選址、管道鋪設時的選線、設備更新、投資、

22、某些整數規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結為求最短路的問題。因此這類問題在生產實際中得到廣泛應用。2022-3-23-第6章 圖與網絡分析-45- 在圖示的網絡圖中，從給定的點S出發(fā)，要到達目的地T。問：選擇怎樣的行走路線，可使總行程最短？方法：Dijkstra（D氏）標號法按離出發(fā)點的距離由近至遠逐漸標出最短距離和最佳行進路線。S1求某兩點間最短距離的D（Dijkstra）氏標號法2472022-3-23461. 設 dij 表示圖中兩相鄰點 i 與 j 的距離，若 i 與 j 不相鄰，令 dij =，顯然 dii =0。 Dijkstra 算法假設：基本思路：如果 v1 v2 v3 v4 是

23、 v1 v4 的最短路徑，則 v1 v2 v3 一定是 v1 v3 的最短路徑。 v2 v3 v4 一定是 v2 v4 的最短路徑。2. 設 Lsi 表示從 s 點到 i 點的最短距離。2022-3-2347Dijkstra 算法步驟：1. 對起始點 s ，因 Lss =0 ，將 0 標注在 s 旁的小方框內，表示 s 點已標號；2. 從點 s 出發(fā)，找出與 s 相鄰的點中距離最小的一個，設為 r ，將 Lsr = Lss+ dsr 的值標注在 r 旁的小方框內，表明點 r 也已標號；3. 從已標號的點出發(fā)，找出與這些點相鄰的所有未標號點 p ，若有 Lsp =min Lss+ dsp , L

24、sr+ drp ，則對 p 點標號，并將 Lsp 的值標注在 p 點旁的小方框內；4. 重復第 3 步，直到 t 點得到標號為止。求從起始點 s 到終止點 t 的最短路徑。2022-3-2348例. 求下圖中從 v1 到 v7 的最短路。解： (1) 從 v1 點出發(fā)，對 v1 點標號，將 L11=0 標注在 旁的小方框內，令 v1V，其余點屬于 ；V2022-3-2349L1r = min 0+d12 , 0+ d13 =min5,2=2= L13(2) 同 v1 相鄰的未標號點有v2 、 v3 ，2022-3-2350對 v3 標號，將 L13 的值標注在v3 旁的小方框內；將( v1,

25、v3) 加粗，并令 Vv3 V，VvV3。2022-3-2351L1p = min L11+d12 , L13+d34, L13+d36 =min0+5,2+7,2+4 = 5 = L12(3) 同 v1 , v3 相鄰的未標號點有v2 、 v4 、 v6 ，2022-3-2352對 v2 標號，將 L12 的值標注在 v2 旁的小方框內；將( v1, v2) 加粗，并令 Vv2 V，VvV22022-3-2353L1p = min L12+d25 , L12+d24, L13+d34 ,L13+d36 =min5+7,5+2,2+7,2+4 = 6 = L16。(4) 同 v1 , v2 ,

26、v3 相鄰的未標號點有v4 、 v5、 v6 ，2022-3-2354對 v6 標號，將 L16 的值標注在 v6 旁的小方框內；將( v3, v6) 加粗，并令 Vv6 V，VvV62022-3-2355L1p = min L12+d25 , L12+d24, L13+d34 , L16+d64 , L16+d65 , L16+d67 =min5+7, 5+2, 2+7, 6+2, 6+1, 6+6 = 7 = L14 = L15(5) 同 v1 , v2 ,v3 , v6 相鄰的未標號點有v4 、 v5、 v7 ，2022-3-2356對 v4 , v5 同時標號，將 L14 = L15

27、的值標注在 v4, v5 旁的小方框內；將( v2, v4), ( v6, v5) 加粗，并令Vv4v5V，VvvV54,2022-3-2357L1p = min L15+d57 , L16+d67 =min7+3,6+6=10= L17(6) 同 v1 , v2 ,v3 , v4, v5, v6 相鄰的未標號點只有 v7 ，2022-3-2358 對 v7 標號，將 L17 的值標注在 v7 旁的小方框內；將( v5, v7) 加粗。圖中粗線表明從點 v1 到網絡中其它各點的最短路，各點旁的數字就是點 v1 到各點的最短距離。2022-3-23-第6章 圖與網絡分析-59-SABCDET25

28、241431755702447891413594 最短路線：S AB E D T最短距離：Lmin=13 練習： 1. 用Dijkstra算法求下圖從v1到v6的最短距離及路線。v3v54v1v2v4v635222421v1到v6的最短路為：6521vvvv61n 逐次逼近算法逐次逼近算法 DijkstraDijkstra算法只適用于所有算法只適用于所有 的情形，當賦權有向圖中存在的情形，當賦權有向圖中存在負權時，則算法失效。負權時，則算法失效。例如在右圖所示的賦權有向圖中，例如在右圖所示的賦權有向圖中，用用DijkstraDijkstra算法得算法得 到到 的最短路的的最短路的權是權是5.5

29、.但這里顯然不對；但這里顯然不對； 因為因為 到到 的最短路是的最短路是 ，權為，權為3 3。 當當 存在負權時，可采取逐次逼近算法來求解最短路存在負權時，可采取逐次逼近算法來求解最短路。 不妨設從任一點不妨設從任一點 到任一點到任一點 都有一條弧，如果都有一條弧，如果則添加弧則添加弧 ，且令，且令 。 如果為同一頂點，則如果為同一頂點，則 。 ijw01v3v123vvv1v3v75-4231ivijw jvD= V,A,ijija =(v ,v )Aijija =(v ,v )ii= 0, i=1,2,pw62 由最優(yōu)性原理，若令由最優(yōu)性原理，若令 為從為從 到到 的最短距離，則必滿足如的

30、最短距離，則必滿足如下方程：下方程： ，其中，其中P為為D的點數。的點數。 由此可得如下遞推公式：由此可得如下遞推公式： 其中其中 表示從表示從 走一步直接到達走一步直接到達 的最短距離，的最短距離， 表示從表示從 走走t t步到達步到達 的最短距離。為迭代步數。的最短距離。為迭代步數。 若第若第k k步，對所有步，對所有 ，有，有 則則 為為 到任一點到任一點 的最短路權。的最短路權。 sjd v ,vsvjvsjsiiji=1,2,pd v ,v= mind v ,v+ws到到j 的最短路的最短路s s到到i的最短路的最短路i j 1sjsjdv ,v= , j1,2,p;w tt-1sj

31、siiji=1,2,pdv ,vmindv ,v +w 1sjdv ,v tsjdv ,vsvjv kk-1sjsjdv ,v=dv ,vj1,2,p ksjdv ,vsvjvsvjv63解：迭代初始條件為：解：迭代初始條件為：有有 第二步迭代：第二步迭代：用表表示全部計算過程。用表表示全部計算過程。 1sjsjdv ,v=w 111112111314111516111718dv ,v= 0, dv ,v= -1,dv ,v= -2, dv ,v= 3, dv ,v=+ , dv ,v=+ ,dv ,v=+ , dv ,v=+ .例例 求所示賦權有向圖中從求所示賦權有向圖中從 到各點的最短路。

32、到各點的最短路。11-1-1-2-3-3-56318-527212345678 21sjsiijidv ,v= min dv ,v+w, j=1,2,81-11v640-5-350-1-1710110-1-73208-2-21 1-5-50-3-5-1206003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格為表中空格為） 111111121314dv ,v= 0, dv ,v= -1,dv ,v= -2, dv ,v= 3 6560-5-3-550-1-1-17101-310-1-7-73208-2-2-21

33、1-5-50-3-5-5-12060003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格為表中空格為）66660-5-3-5-550-1-1-1-17101-3-310-1-7-7-73208-2-2-2-21 1-5-50-3-5-5-5-120600003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格為表中空格為）67當時當時表明已得到從表明已得到從 到各點的最短路的權，即表中最后一列數。到各點的最短路的權，即表中最后一列數。如

34、果需要知道點到各點的最短路徑，可以采用如果需要知道點到各點的最短路徑，可以采用“反向追蹤反向追蹤”的辦法。的辦法。比如已知，則尋找一點，使比如已知，則尋找一點，使記下，再考察尋找一點，使記下，再考察尋找一點，使記下，直至達到為止本例中記下，直至達到為止本例中因為因為由記下由記下由記下由記下因為因為 一步可達，所以最短路徑一步可達，所以最短路徑 431j1jdv ,v=dv ,vj=1, 2,8t=41v1v1jd v ,v1kkj1jd v ,vwd v ,v1iik1kd v ,vwd v ,vkj(v ,v )1kd v ,v,ik(v ,v )1vivkv18d v ,v=6166818

35、d v ,v+w=(-1)+7=6=d v ,v68(v ,v )133616d v ,v+w =(-2)+1= -1 =d v ,v36(v ,v )13d v ,v=21368vvvv68660-5-3-5-550-1-1-1-17101-3-310-1-7-7-7320-2-2-2-21 1-5-50-3-5-5-5-120600003-2-10ij1v2v4v5v6v7v8v1v2v3v3v4v5v7v8v6vijw t1jdv ,v1t2t3t4t（表中空格為表中空格為）69例例 設備更新問題。某企業(yè)使用一臺設備，在每年年初，都要決定設備更新問題。某企業(yè)使用一臺設備，在每年年初，都要

36、決定是否更新。若購置新設備，要付購買費；若繼續(xù)使用舊設備，則支是否更新。若購置新設備，要付購買費；若繼續(xù)使用舊設備，則支付維修費用。試制定一個付維修費用。試制定一個5 5年更新計劃，使總支出最少。年更新計劃，使總支出最少。 若已知設備在各年的購買費及不同機器役齡時的殘值和維修費若已知設備在各年的購買費及不同機器役齡時的殘值和維修費，如下表所示：，如下表所示：第第1 1年年第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 購買費購買費 11111212131314141414機器役齡機器役齡 0-10-11-21-22-32-33-43-44-54-5維修費維修費 5 56 68

37、811111818殘值殘值 4 43 32 21 10 070解：把這個問題化為最短路問題解：把這個問題化為最短路問題用用 表示第表示第i i年初購進一臺新設備，虛設一個點年初購進一臺新設備，虛設一個點 表示第表示第5 5年底；年底； 用弧用弧 表示第表示第i i年初購的設備一直使用到第年初購的設備一直使用到第j j年年初（第年年初（第j-1j-1年年低）；弧年年低）；弧旁的數字表示第旁的數字表示第i i年初購進設備，一直使用到第年初購進設備，一直使用到第j j年初所需支付的購買年初所需支付的購買、維修的全部費用。、維修的全部費用。 這樣設備更新問題就變?yōu)椋呵髲倪@樣設備更新問題就變?yōu)椋呵髲?到

38、到 的最短路的最短路. .ivijv ,v1v6vijv ,v6v第第1 1年年第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 購買費購買費 11111212131314141414機器役齡機器役齡 0-10-11-21-22-32-33-43-44-54-5維修費維修費 5 56 68 811111818殘值殘值 4 43 32 21 10 071第第1 1年年第第2 2年年 第第3 3年年 第第4 4年年 第第5 5年年 購買費購買費 11111212131314141414機器役齡機器役齡 0-10-11-21-22-32-33-43-44-54-5維修費維修費 5 56

39、 68 811111818殘值殘值 4 43 32 21 10 0194059121314152130152841292220123456購買購買維修維修殘值殘值費用費用72 計算結果表明計算結果表明 為最短路，路長為為最短路，路長為4949。即在。即在第第1 1年、第年、第3 3年初各購買一臺新設備為最優(yōu)決策，這時年初各購買一臺新設備為最優(yōu)決策，這時5 5年的總費用年的總費用為為4949。136vvv194059121314152130152841292220123456(v1,0)(v1,12)(v1,19)(v1,28)(v3,40)(v3,49) V1 V2 12V3 19 19V4

40、28 28 28V5 40 40 40 40V6 59 53 49 49 49相鄰點相鄰點V1 V1 V1 V1 V3V3標號標號73n 圖的矩陣表示圖的矩陣表示l距離矩陣：設圖距離矩陣：設圖 ， 為邊上的權，表示點為邊上的權，表示點 到到 之間的距離，則可構造距離矩陣，之間的距離，則可構造距離矩陣， 其中其中如：以下無向賦權圖中的權表示點與點之間距離如：以下無向賦權圖中的權表示點與點之間距離G= V,E,ijwijnnA =aijijijw v ,v Ea =0 ijv ,v 其他其他1234512345 v v v v vv09247v9034+A= v 23085v44806v7+560

41、1 12 24 47 76 63 35 54 48 89 92 23 34 45 5或或 對有向賦權圖，則定義時將改為。對有向賦權圖，則定義時將改為。ijaij v ,v ij (v ,v )ivjv654321654321 030303302004020576305020007204346040vvvvvvvvvvvvB v5v1v2v3v4v64332256437下圖所表示的圖可以構造權矩陣B如下:75l鄰接矩陣：鄰接矩陣：設圖設圖 ，則鄰接矩陣的元素可定，則鄰接矩陣的元素可定義如下義如下ijn nA= aij1a=0G= V,Eij v ,v E其他其他對有向賦權圖，則定義時將改為對有向

42、賦權圖，則定義時將改為如如ijaij v ,v ij (v ,v )1234512345 v v v v vv01010v10110A= v00000v00001v0110012345v5v1v2v3v4v643322564371234561236 6456 010111101100010101111010100101101010 vvvvvvvvvAvvv下圖所表示的圖可以構造鄰接矩陣A如下 關聯(lián)矩陣：對于圖G=(V,E), | V |=n, | E |=m, 有mn階矩陣M=(mij) mn，其中: 其他其他的一個端點的一個端點是邊是邊當且僅當當且僅當的兩個端點的兩個端點是邊是邊當且僅當當

43、且僅當0ev1ev2jijiijm1 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0v1v2v3v4v5v6v7v8e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4下

44、圖所表示的圖可以構造鄰接矩陣M如下:M=（mij）=2022-3-23-第6章 圖與網絡分析-79-SABCDET2524143175572求任意兩點間最短距離的矩陣算法2022-3-23-第6章 圖與網絡分析-80- 構造任意兩點間直接到達的最短距離矩陣D（0）= dij（0） S A B C D E T S 0 2 5 4 A 2 0 2 7 B 5 2 0 1 5 3 C 4 1 0 4 D 7 5 0 1 5 E 3 4 1 0 7 T 5 7 0D（0）= 構造任意兩點間直接到達、或者最多經過1個中間點到達的最短距離矩陣D（1）= dij（1）2022-3-23-第6章 圖與網絡分析

45、-81-其中 dij（1）= min dir（0）+ drj（0） ， S A B C D E T S 0 2 4 4 9 8 A 2 0 2 3 7 5 12 B 4 2 0 1 4 3 10 C 4 3 1 0 5 4 11 D 9 7 4 5 0 1 5 E 8 5 3 4 1 0 6 T 12 10 11 5 7 0D（1）=irjdir（0）drj（0）rdSE（1）= min dSS（0）+dSE（0）, dSA（0）+dAE（0）, dSB（0）+dBE（0）, dSC（0）+dCE（0）, dSD（0）+ dDE（0） , dSE（0）+ dEE（0）, dST（0）+ dTE

46、（0） =8例如2022-3-23-第6章 圖與網絡分析-82-其中 dij（2）= min dir（1）+ drj（1） S A B C D E T S 0 2 4 4 8 7 14 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 14 11 9 10 5 6 0D（2）=irjdir（1）drj（1）r 構造任意兩點間最多可經過3個中間點到達的最短距離矩陣 D（2）= dij（2）2022-3-23-第6章 圖與網絡分析-83-其中 dij（3）= min dir（2）+

47、 drj（2） S A B C D E T S 0 2 4 4 8 7 13 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0D（3）=irjdir（2）drj（2）r 構造任意兩點間最多可經過7個中間點到達的最短距離矩陣 D（3）= dij（3）2022-3-23-第6章 圖與網絡分析-84-說明：一般，對于D（k）= dij（k），其中 dij（k）= min dir（k-1）+ drj（k-1） ，k=0，1，2，3， 最多可經過2k-1

48、個中間點： 其數列為 0，1，3，7，15，31， 2k-1， 收斂條件： 當 D（k+1）= D（k）時，計算結束； 設網絡中有p個點，即有p-2個中間點，則 2k-1-1 p-2 2k-1 k-1log2 (p-1) k Klog2(p-1)+1，計算到 k=lg(p-1)/lg2 +1時，收斂，計算結束。2022-3-23-第6章 圖與網絡分析-85- 例：有7個村鎮(zhèn)要聯(lián)合建立一所小學，已知各村鎮(zhèn)小學生的人數大致為S30人， A40人，B20人，C15人，D35人，E25人， T50人。問：學校應建在那一個地點，可使學生總行程最少？ S A B C D E T S 0 2 4 4 8 7

49、 13 A 2 0 2 3 6 5 11 B 4 2 0 1 4 3 9 C 4 3 1 0 5 4 10 D 8 6 4 5 0 1 5 E 7 5 3 4 1 0 6 T 13 11 9 10 5 6 0L=30 40 20 15 35 25 50人數= 1325 1030 880 1035 910 865 1485T解： 如何制定一個運輸計劃使生產地到銷售地的產品輸送量最大。這就是一個網絡最大流問題。6.5 網絡最大流問題2022-3-2387一. 網絡最大流的有關概念 1. 有向圖與容量網絡圖中每條邊有規(guī)定指向的圖稱為有向圖，有向圖的邊稱為弧，記作(vi , vj )，表示方向從點 v

50、i 指向點 vj ，有向圖是點與弧的集合，記作 D(V, A )。弧(vi , vj )的最大通過能力，稱為該弧的容量，記為c(vi , vj ) ，或簡記為 cij 。定義了弧容量的網絡稱為容量網絡。2022-3-2388容量網絡通常規(guī)定一個發(fā)點(源點，記為s)一個收點(匯點，記為t)，網絡中其余的點稱為中間點。從發(fā)點到收點之間允許通過的最大流量稱為最大流。多個收(發(fā))點的網絡可以轉換為只含一個收(發(fā))點。2. 流與可行流流是指加在網絡各條弧上的一組負載量，對加在弧(vi ,vj )上的負載量記作 f (vi , vj ) ，或簡記作 fij ，若網絡上所有的 fij =0，這個流稱為零流。

51、2022-3-2389以 v( f )表示網絡中從 st 的流量，則jtjjjsvvfvvffv),(),()(零流是可行流，求最大流就是求v( f )的最大值。稱網絡上滿足下述條件(1)、(2)的流為可行流：(1) 容量限制條件: 對所有弧有0f (vi , vj ) c (vi , vj )(2) 中間點平衡條件：f (vi , vj ) - f(vj , vi ) =0 (is , t)2022-3-2390二. 割和流量割(集）是指將容量網絡中的發(fā)點和收點分割開，并使st 的流中斷的一組弧的集合（截集）弧旁數字為 cij ( fij ) 有不同的割見教材161頁上圖中 KK 將網絡上的

52、點分割成 V 和 兩個集合，并有 sV , t ，稱弧的集合 (V, )=(v1 , v3) , (v2 , v4)是一個割。注意，這里不包含(v3 , v2) 。VVV2022-3-2391割的容量是組成它的集合中各弧容量之和，用c(V, )表示，V),(),(),(),(VVjijivvcVVc f (V, ) 表示通過割 (V, ) 中所有 V 方向弧的流量的總和; f ( ,V ) 表示通過割 中所有 V方向弧的流量的總和，則有：VVVVV),(),(),(),(),(),( , ),(),(VVijijVVjijivvfVVfvvfVVf2022-3-2392從 st 的流量等于通過

53、割的從V 的流量減 V的流量，有：VV),(),()(VVfVVffv用 v*( f ) 表示網絡中從 st 的最大流，則有),(),()(*VVfVVffvV),(),(),()(*VVcVVfVVffv因此，上例中最大流不會超過14（所有割集中最小者） 。最大流 v*( f ) 應 最小割的容量(用 c*(V, )表示)定理：網絡的最大流量等于它的最小割集的容量。定理：網絡的最大流量等于它的最小割集的容量。2022-3-23-第6章 圖與網絡分析-93- 有向圖：含有以箭頭指示方向的邊的網絡圖。 ?。河邢驁D上的邊稱為弧。用（vi,vj）表示。 弧的容量：弧上通過負載的最大能力，簡稱容量。以

54、cij表示。 流：加在網絡每條弧上的一組負載量，以fij表示。 可行流：能夠通過網絡的負載量，通常應滿足兩個條件： 容量限制條件：對所有的弧，0 fijcij 中間點平衡條件：對任何一個中間點，流入量=流出量 發(fā)點、收點、中間點：流的起源點稱發(fā)點，終到點稱收點，其余的點稱中間點。 最大流；能夠通過網絡的最大流量。 割集：一組弧的集合，割斷這些弧，能使流中斷。簡稱割。 割的容量：割集中各弧的容量之和。 最小割：所有割集中容量之和為最小的一個割集。2022-3-23-第6章 圖與網絡分析-94-定理：當網絡中不存在任何增廣鏈時，則網絡達到最大流狀態(tài)。二、最大流最小割定理 前向弧+：一條發(fā)點到收點鏈

55、中，由發(fā)點指向收點的弧，又稱正向弧。 后向弧-：一條發(fā)點到收點鏈中，由收點指向發(fā)點的弧，又稱逆向弧。 增廣鏈：由發(fā)點到收點之間的一條鏈，如果在前向弧上滿足流量小于容量，即fij0，（反向弧非零流），則稱這樣的鏈為增廣鏈。2022-3-23-第6章 圖與網絡分析-95-三、網絡最大流的標號算法(Ford-Fulkerson標號算法)基本思想：尋找增廣鏈，改善流量分布；再重復，直到不 存在任何增廣鏈為止。步驟： 給始點標號：（0，+） 從已標號點i出發(fā)，看與其相關聯(lián)的未標號點j上的弧，對+，若有0fijcij，則可對j點標號，記（i, (j)）， 其中 (j)=min (i) ，cij - fij

56、對-，若有0 fji cij，也可對j點標號，記（ i, (j)）， 其中 (j)=min (i) ，fji （注：若有多個可標號點，可任選其中之一。）若標號中斷，則得到最大流狀態(tài)，否則，重復，繼續(xù)標號，至收點得到標號，轉。2022-3-23-第6章 圖與網絡分析-96-當收點得到標號，則沿標號得到的增廣鏈進行流量調整： 對+，fij = fij + (t) 對-，fij = fij - (t) 其余弧上的流量不變。 重復上述過程。 最小割集：已標號點集合與未標號點集合相連接的弧中， 流量=容量的弧。97找可行流找可行流給給S 標號標號( S， ) ) t 是否已是否已 標號標號 是否存在已標

57、號是否存在已標號 但未檢查的點但未檢查的點 倒向追蹤倒向追蹤找出增廣鏈找出增廣鏈 令調整量令調整量求改進的可行流求改進的可行流+ijij-ijijijijijf +v ,vf = f -v ,vfv ,vt=vlf不存在關于不存在關于的增廣鏈的增廣鏈即為最大流即為最大流 i 已已 標號標號,但未檢查但未檢查 對對i 進行檢查，并對進行檢查，并對j 標號標號: 若，且，對若，且，對j 標號標號: ，ijv ,vAijijfcijv , (v )l jiijijv =minv ,c -fll 若，且，對若，且，對j 標號標號: ，jiv ,vAji0fij-v , (v )ljijivminv ,

58、 cll 是是否否2022-3-2398例：用標號法求下述網絡圖 s t 的最大流量，并找出該網絡圖的最小割。2022-3-2399解：(1) 先給 s 點標號 (0 , )；2022-3-23100 (2) 從 s 點出發(fā)的弧 (s , v2)，因有 fs20 ，且(v1)=min(v2) , f12)=2故對 v1 點標號(v2 , 2)。 (v2 , v4)飽和，不標號。2022-3-23102 (4) 弧 (v1 , v3)，因有 f130 ，且(v4)=min(v3) , f43)=1故對 v4 點標號(v3 , 1)。 (v3 , t)飽和，不標號, v2 已標號。2022-3-2

59、3104(6) 弧 (v4 , t)，因有 f4tc4t ，且(t)=min(v4) , (c4t - f4t)=1故對 t 點標號(v4 , 1)。2022-3-23105(7) 由于收點 t 得到標號，用反追蹤法找出網絡圖上的一條增廣鏈。2022-3-23106(8) 修改增廣鏈上各弧的流量：918)(011)(514)(314)(615)(4443431313121222tfftfftfftfftffttss非增廣鏈上的所有弧流量不變，這樣得到網絡圖上的一個新的可行流。2022-3-23107重復上述標號過程，由于對點 s 、v1 、v2 、v3 標號后，標號中斷，故圖中的可行流即為最大

60、流，v*( f )=14已標號點集為V =s , v1 , v2 , v3 ，未標號點集 ，(V , ) =(3 , t) , (2 , 4)為網絡的最小割。VV2022-3-23108三. 應用舉例例1：P166，例7ADECBF2321211111、方向含義2、E、D之間3、數字含義切斷A、F之間的通路，相當于求最小割集。2022-3-23109例2：P167，例81、匹配關系1234562、匹配限制145f=1 f14 f152022-3-23110134f=1 f34 f14 3、等價網絡圖123456st111111111111例 用標號算法求下圖中st的最大流量，并找出最小割。v1