圖與網(wǎng)絡優(yōu)化.ppt課件

1、運籌學課件 圖與網(wǎng)絡分析 1 圖與網(wǎng)絡分析 圖的基本概念與基本定理 樹和最小支撐樹 最短路問題 網(wǎng)絡系統(tǒng)最大流問題 網(wǎng)絡系統(tǒng)的最小費用最大流問題 中國郵遞員問題本章內容重點2引 言圖論應用非常廣泛： 控制論，信息論，工程技術，交通運輸，經(jīng)濟管理，電子計算機等領域； 科學研究，市場和社會生活中的許多問題，可以用圖論的理論和方法來加以解決。 例如，通信線路的架設，輸油管道的鋪設，鐵路或者公路交通網(wǎng)絡的合理布局。3引 言 將復雜的工程系統(tǒng)和管理問題用圖的理論加以描述，可以解決許多工程項目和管理決策的優(yōu)化問題。 圖論越來越受到工程技術人員和經(jīng)營管理人員的重視。4引 言 1736年瑞士科學家歐拉發(fā)表了關

2、于圖論方面的第一篇科學論文，解決了著名的哥尼斯堡七座橋問題。 德國的哥尼斯堡城有一條普雷格爾河，河中有兩個島嶼，河的兩岸和島嶼之間有七座橋相互連接，如圖8-1a所示。5引 言AB圖8-1 a）CD6引 言 當?shù)氐木用駸嶂杂谶@樣一個問題，一個漫步者如何能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發(fā)地。盡管試驗者很多，但是都沒有成功。 為了尋找答案，1736年歐拉將這個問題抽象成圖8-1b所示圖形的一筆畫問題。即能否從某一點開始不重復地一筆畫出這個圖形，最終回到原點。歐拉在他的論文中證明了這是不可能的，因為這個圖形中每一個頂點都與奇數(shù)條邊相連接，不可能將它一筆畫出，這就是古典圖論中的第一

3、個著名問題。7引 言圖8-1 b）ACDB8例4 中國郵遞員問題（CPPChinese postman problem） 一名郵遞員負責投遞某個街區(qū)的郵件。如何為他（她）設計一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內每條街道至少一次，最后返回郵局）？由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題。9例5 旅行商問題（哈密頓問題）（TSPtraveling salesman problem） 一名推銷員準備前往若干城市推銷產(chǎn)品。如何為他（她）設計一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問

4、題。10 在實際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關系，常常在紙上用點和線來畫出各式各樣的示意圖。 例8.1:圖8-2是我國北京、上海、重慶等十四個城市之間的鐵路交通圖，這里用點表示城市，用點與點之間的線表示城市之間的鐵路線。諸如此類還有城市中的市政管道圖，民用航空線圖等等。1.圖的基本概念與基本定理111.圖的基本概念與基本定理太原重慶武漢南京徐州連云港上海鄭州石家莊塘沽青島濟南天津北京圖8-212 例8.2:有六支球隊進行足球比賽，我們分別用點v1v6表示這六支球隊，它們之間的比賽情況，也可以用圖反映出來，已知v1隊戰(zhàn)勝v2隊，v2隊戰(zhàn)勝v3隊，v3隊戰(zhàn)勝v5隊，如此等等。這個勝負情況

5、，可以用圖8-3所示的有向圖反映出來。1.圖的基本概念與基本定理131.圖的基本概念與基本定理v3v1v2v4v6v5圖8-314 圖論中常用點和點之間的線所構成的圖，反映實際生產(chǎn)和生活中的某些特定對象之間的特定關系。一般來說，通常用點表示研究對象、用點與點之間的線表示研究對象之間的特定關系。 在一般情況下，圖中的相對位置如何，點與點之間線的長短曲直，對于反映研究對象之間的關系，顯的并不重要。 因此，圖論中的圖與幾何圖，工程圖等本質上是不同的。1.圖的基本概念與基本定理15 通常把點與點之間不帶箭頭的線叫做邊，帶箭頭的線叫做弧。 如果一個圖是由點和邊所構成的，那么，稱為為無向圖，記作G =(V

6、，E)，其中V表示圖G的點集合，E表示圖G的邊集合。連接點vi,vjV的邊記作vi,vj，或者vj,vi。 如果一個圖是由點和弧所構成的，那么稱為它為有向圖，記作D =(V,A)，其中V 表示有向圖D的點集合，A表示有向圖D的弧集合。一條方向從vi指向vj的弧，記作(vi,vj)。16例如.圖8-4是一個無向圖G=（V，E）其中V = v1,v2,v3,v4 E = v1,v2,v2,v1,v2,v3, v3,v4,v1,v4, v2,v4, v3,v3 1.圖的基本概念與基本定理v3v2v1v4圖8-417圖8-5是一個有向圖D=（V，A）其中V = v1,v2,v3,v4,v5,v6,v7

7、 A = (v1 ,v2),(v1 ,v3),(v3 ,v2), (v3 ,v4), (v2 ,v4),(v4 ,v5),(v4 ,v6),(v5 ,v3), (v5 ,v4),(v5 ,v6),(v6 ,v7)1.圖的基本概念與基本定理v7v5v3v4v2v1v6圖8-518一些常用的名詞：無向圖G 或 有向圖D節(jié)點數(shù) 記作P(G)或P(D),簡記作P,邊數(shù) 或者 弧數(shù) 記作q(G)或者q(D),簡記作q。如果邊vi,vjE,那么稱vi,vj是邊的端點，或者vi,vj是相鄰的。如果一個圖G中，一條邊的兩個端點是相同的,那么稱為這條邊是環(huán)。1.圖的基本概念與基本定理191.圖的基本概念與基本定

8、理如果兩個端點之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡?。一個無環(huán)，無多重邊的圖為簡單圖。一個無環(huán)，有多重邊的圖稱為多重圖。v3v2v1v4圖8-4環(huán)20 以點v為端點的邊的個數(shù)稱為點v 的度，記作d(v)。如上圖中d(v1)=3, d(v2)=4, d(v3)=4, d(v4 )=3。 度為零的點稱為弧立點，度為1的點稱為懸掛點。懸掛點的邊稱為懸掛邊。 度為奇數(shù)的點稱為奇點，度為偶數(shù)的點稱為偶點。1.圖的基本概念與基本定理21端點的度 d(v)：點 v 作為邊端點的個數(shù)；奇點：d(v)=奇數(shù)； 偶點：d(v)=偶數(shù)；懸掛點：d(v)=1；懸掛邊：與懸掛點連接的邊；孤立點：d(v)=0；空圖：E

9、 = ，無邊圖1.圖的基本概念與基本定理22 定理8.1 所有頂點次數(shù)之和等于所有邊數(shù)的2倍。 定理8.2 在任一圖中，奇點的個數(shù)必為偶數(shù)。 1.圖的基本概念與基本定理23圖的連通性： 鏈： 由兩兩相鄰的點及其相關聯(lián)的邊構成的點邊序列; 如: v0 ,e1 ,v1 ,e2 ,v2 ,e3 ,v3 ,vn-1 ,en , vn ;v0 ，vn分別為鏈的起點和終點； 簡單鏈：鏈中所含的邊均不相同； 初等鏈：鏈中所含的點均不相同,也稱通路；1.圖的基本概念與基本定理24回路：若 v0 vn 分稱該鏈為開鏈，否則稱為閉鏈或回路；圈：除起點和終點外鏈中所含的點均不相同的閉鏈；連通圖：圖中任意兩點之間均至

10、少有一條通路，否則稱作不連通圖。1.圖的基本概念與基本定理25G11.圖的基本概念與基本定理G1= V1 , E1 26子圖： 設 G1= V1 , E1 ,G2= V2 ,E2 子圖定義：如果 V2 V1 , E2 E1 稱 G2 是 G1 的子圖； 真子圖：如果 V2 V1 , E2 E1 稱 G2 是 G1 的真子圖； 部分圖（支撐子圖）：如果 V2 = V1 , E2 E1 稱 G2 是 G1 的部分圖； 導出子圖：若V2 V1, E2=vi,vj:vi,vjV2, 稱 G2 是 G1 中由V2 導出的導出子圖。1.圖的基本概念與基本定理27G2真子圖G2真子圖1.圖的基本概念與基本定

11、理G2= V2 ,E2 子圖、真子圖28G3子圖部分圖（支撐子圖）1.圖的基本概念與基本定理部分圖：V3 = V1 , E3 E1 稱 G3 是 G1 的部分圖；29G4導出子圖G4導出子圖1.圖的基本概念與基本定理導出子圖：V4 V1,E4=vi,vjvi,vjV4,稱 G4 是 G1 中由V4 導出的導出子圖。30有向圖：關聯(lián)邊有方向?。河邢驁D的邊a=(u ,v),起點u,終點v;路：若有從 u 到 v 不考慮方向的鏈,且 各方向一致,則稱之為從u到v的路；初等路: 各頂點都不相同的路； 初等回路:u = v 的初等 路; 連通圖： 若不考慮方向 是無向連通圖; 強連通圖：任兩點有路;1.

12、圖的基本概念與基本定理312.樹和最小支撐樹 一、樹及其性質 在各種各樣的圖中，有一類圖是十分簡單又非常具有應用價值的圖，這就是樹。 例8.3：已知有六個城市，它們之間要架設電話線，要求任意兩個城市均可以互相通話，并且電話線的總長度最短。322.樹和最小支撐樹 如果用六個點v1，v6代表這六個城市，在任意兩個城市之間架設電話線，即在相應的兩個點之間連一條邊。這樣，六個城市的一個電話網(wǎng)就作成一個圖。由于任意兩個城市之間均可以通話，這個圖必須是連通圖。并且，這個圖必須是無圈的。否則，從圈上任意去掉一條邊，剩下的圖仍然是六個城市的一個電話網(wǎng)。圖8-8是一個不含圈的連通圖，代表了一個電話線網(wǎng)。332.

13、樹和最小支撐樹圖8-8v6v3v4v2v5v1342.樹和最小支撐樹 定義8.1 無圈的連通圖叫做樹。 性質： 定理8.3 設圖G=(V，E)是一個樹P(G) 2，那么圖G中至少有兩個懸掛點。 定理8.4 圖G=（V，E）是一個樹的充要條件是G不含圈，并且有且僅有P-1條邊。352.樹和最小支撐樹定理8.5 圖G=（V，E）是一個樹的充要條件是G是連通圖，并且有且僅有P-1條邊。定理8.6 圖G是一個樹的充分必要條件是任意兩個頂點之間有且僅有一條鏈。362.樹和最小支撐樹從以上定理，不難得出以下結論： （1）從一個樹中任意去掉一條邊，那么剩下的圖不是連通圖，亦即，在點集合相同的圖中，樹是含邊數(shù)

14、最少的連通圖。 （2）在樹中不相鄰的兩個點之間加上一條邊，那么恰好得到一個圈。372.樹和最小支撐樹 二.支撐樹 定義8.2 設圖K=(V,E)是圖G=(V,E)的一支撐子圖,如果圖K=(V,E)是一個樹,那么稱K是G的一個支撐樹。 圖8.10b 是圖8-10a 的一個支撐樹。v6v5v2v3v4v1v6v5v2v3v4v1圖8-10a）b）382.樹和最小支撐樹顯然,如果圖K=( V, E )是圖G=(V, E)的一個支撐樹,那么K 的邊數(shù)是p(G)-1；G中不屬于支撐樹K的邊構成K的余樹，其邊數(shù)是q(G)-p(G)+1。定理8.7 一個圖G有支撐樹的充要條件是G是連通圖。39T支撐樹（部分

15、圖）1.圖的基本概念與基本定理40T的余樹（部分圖）1.圖的基本概念與基本定理41證明: 必要性顯然；充分性: 設圖G是連通的，若G不含圈，則G是一個樹，從而G是自身的一個支撐樹。 若G含圈，則任取G的一個圈，從該圈中任意去掉一條邊，得到圖G的一支撐子圖G1。若G1不含圈，則G1是G的一個支撐樹。若G1仍然含圈，則任取G1的一個圈，再從圈中任意去掉一條邊，得到圖G的一支撐子圖G2。依此類推，可以得到圖G的一個支撐子圖GK，且不含圈，從而GK是一個支撐樹。422.樹和最小支撐樹 以上充分性的證明，提供了一個尋找連通圖支撐樹的方法叫做“破圈法”。就是從圖中任取一個圈，去掉一條邊。再對剩下的圖重復以

16、上步驟，直到不含圈時為止，這樣就得到一個支撐樹。432.樹和最小支撐樹例8.4:用破圈法求出下圖的一個支撐樹。V5V4V2V3V1e6e5e4e3e2e1e7e844 取一個圈(v1,v2,v3,v1)，在一個圈中去掉邊e3 。在剩下的圖中，再取一個圈（v1,v2,v4,v3,v1），去掉邊e4 。再從圈（v3,v4 v5,v3）中去掉邊e6 。再從圈 (v1,v2,v5,v4,v3,v1 ）中去掉邊e7，這樣，剩下的圖不含圈，于是得到一個支撐樹，如圖所示。v2e1e2e5e8v1v3v4452.樹和最小支撐樹 三、最小支撐樹問題 定義8.3 如果圖G =（V，E），對于G中的每一條vi,vj

17、，相應地有一個數(shù)wij，那么稱這樣的圖G為賦權圖，wij稱為邊vi,vj的權。 這里所指的權，是具有廣義的數(shù)量值。根據(jù)實際研究問題的不同，可以具有不同的含義。例如長度，費用、流量等等。462.樹和最小支撐樹 定義8.4 如果圖T =（V，E）是圖G 的一個支撐樹，那么稱E上所有邊的權之和為支撐樹T 的權，記作S(T)。 如果圖G 的支撐樹T* 的權S(T*)，在G 的所有支撐樹T 中的權最小，即S(T*) = minS(T)，那么稱T*是G 的最小支撐樹。472.樹和最小支撐樹常用的有破圈法和生長法（避圈法）兩個方法： （1）在網(wǎng)絡圖中尋找一個圈。若不存在圈，則已經(jīng)得到最短樹或網(wǎng)絡不存在最短樹

18、； （1）去掉該圈中權數(shù)最大的邊； 反復重復 （1）（2） 兩步，直到最短樹。 1.破圈法482.樹和最小支撐樹 例8.5 某六個城市之間的道路網(wǎng)如圖8-13a所示，要求沿著已知長度的道路聯(lián)結六個城市的電話線網(wǎng)，使得電話線的總長度最短。492.樹和最小支撐樹v6v5v2v3v4圖8-13av162753544v3v2v1v4v6v5513142圖8-13b順序：淺蘭，黃，粉紅，白502.樹和最小支撐樹 解：如圖8-13a，用破圈法求解最小支撐樹。 （1）圈 v1,v2,v3,v1 ，刪圈中權最大邊v1,v3； （2）圈 v3,v5,v2,v3 ，去掉邊v2,v5； （3）圈 v3,v5,v4,

19、v2,v3 ，去掉邊v3,v5； （4）圈 v5,v6,v4,v5 ，這里有兩條權最大的邊v5,v6和v4,v6。任意刪一條，如v5,v6。 這時得到一個不含圈的圖，即是最小支撐樹。如圖8-13b所示。512.樹和最小支撐樹 從網(wǎng)絡圖中依次尋找權數(shù)較小的邊，尋找過程中，節(jié)點不得重復，即不得構成圈。注意在找較小權數(shù)邊時不考慮已選過的邊和可能造成圈的邊。如此反復進行，直到得到最短樹或證明網(wǎng)絡不存在最短樹。2.成長法(避圈法)522.樹和最小支撐樹用“生長法”求解例8.5解：考慮賦權圖8-13a，任取一點，如 從v1 取權較小的邊（v1 ,v2 ）； 從v2 取權較小的邊（v2 ,v3 ）； 從v3

20、 取權較小的邊（v3 ,v4 ）； 同理依次?。╲4 ,v5），（v4 ,v6 ）。 這時得到了如圖8-13b所示的最小支撐樹。532.樹和最小支撐樹v6v5v2v3v4圖8-13av162753544v3v2v1v4v6v5513142圖8-13b順序：黃，粉紅，白，綠，淺蘭54計算機編程/view/d4839e80d4d8d15abe234e84.html553.最短路徑問題 一.引言 最短路徑問題是圖論中十分重要的最優(yōu)化問題之一，它作為一個經(jīng)常被用到的基本工具，可以解決生產(chǎn)實際中的許多問題，比如城市中的管道鋪設，線路安排，工廠布局，設備更新等等。也可以用于解決其它的最優(yōu)化問題。 563.

21、最短路徑問題 例8.6: 如圖8-14所示的單行線交通網(wǎng)，每個弧旁邊的數(shù)字表示這條單行線的長度。現(xiàn)在有一個人要從v1出發(fā)，經(jīng)過這個交通網(wǎng)到達v8，要尋求是總路程最短的線路。圖8-14v1v4v2v8v7v6v5v9636234102312624101573.最短路徑問題 從v1到v8的路線是很多的。比如從v1出發(fā)，經(jīng)過v2,v5到達v8或者從v1出發(fā)，經(jīng)過v4，v6，v7到達v8等等。但不同的路線，經(jīng)過的總長度是不同的。例如，按照第一個線路，總長度是6+1+6=13單位，按照第二個路線，總長度是1+10+2+4=17單位。58 一般意義下的最短路問題： 設賦權有向圖D =（V，A），對每個弧a

22、 =（vi,vj），相應地有權wij。vs,vt是D中的兩個頂點，P是D中從vs到vt的任意一條路，定義路的權是P中所有弧權的和，記作S(p)。 最短路問題就是求S(P0)=minS(p)。P0叫做從vs到vs的最短路。P0的權S(P0)叫做從vs到vt的距離，記作d（vs，vt）。 由于D是有向圖，很明顯d（vs，vt）與d（vt，vs）一般不相等。593.最短路徑問題 二、Dijkstra（狄克斯拉方法）算法 下面介紹在一個賦權有向圖中尋求最短路的方法Dijkstra算法，它是在1959年提出來的。目前公認，在所有的權 wij 0時，這個算法是尋求最短路問題最好的算法。并且，這個算法實際上

23、也給出了尋求從一個始定點vs到任意一個點vj的最短路。60 Dijkstra算法的基本思想 從vs出發(fā)，逐步向外尋找最短路。在運算過程中，與每個點對應，記錄一個數(shù)，叫做一個點的標號,分為兩類：P 標號：表示從vs到該點的最短路權T 標號：表示從vs到該點最短路權的上界。 算法的每一步是去修改T 標號，把某一個具有T 標號的點改變?yōu)榫哂蠵 標號的點，使圖D 中具有P 標號的頂點多一個。這樣，至多經(jīng)過P -1步，就可求出從vs到各點vj的最短路。61說明：在例8.6中 S=1。因為wij0，d (v1,v1)=0。這時，v1是具有P標號的點。 再看從v1出發(fā)的三條弧(v1,v2)，(v1,v3)和

24、(v1,v4)。如果從v1出發(fā)沿(v1,v2)到達v2，這時的路程是d (v1,v1) + w12= 6單位； 如果從v1出發(fā)，沿(v1,v3)到達v3，則是d (v1,v1) + w13 = 3單位； 同理，如果從v1出發(fā)沿(v1,v4)到達v4，是d（v1,v1）+ w14 = 1單位。62說明（續(xù)） 因此，從v1出發(fā)到達v4的最短路必是（v1,v4），d（v1,v4）=1。這是因為從v1到達v4的任一條路，假如不是（v1,v4），則必先沿（v1,v2）到達v2，或者沿（v1,v3）到達v3，而這時的路程已是6或者3單位。由于wij 0，因此不論他如何再從v2或者v3到達v4，所經(jīng)過的總路

25、程都不會比1少，于是就有d（v1,v4）=1。于是V4變成具有P標號的點。63例8.6說明： 從v1出發(fā)的三條弧(v1,v2)，(v1,v3)和(v1,v4)，mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v1)+w14 = d（v1,v4）=1。P(V4)v2v8v7v6v5v963623410231262410P(V1)164 再看從v1和v4指向其余點的?。簭腣1出發(fā)，分別沿(v1,v2),(v1,v3 )到達v2，v3 ，經(jīng)過的路程是6或者3單位；從v4出發(fā)沿(v4,v6)到達v6，經(jīng)過的路程是d(v1,v4)+w46=1+10=11單位。而mind(v1,v1)

26、+w12,d(v1,v1)+w13,d(v1,v4)+w46=d（v1,v1）+w13=3單位。 根據(jù)同樣的理由，可以斷定，從v1到達v3的最短路是（v1,v3），d（v1,v3）=3。這樣，又使點v3變?yōu)榫哂蠵 標號的點，不斷重復以上過程，就可以求出從vs到達任一點vj的最短路。65例8.6說明（續(xù)）：再看從v1和v4指向其余點的弧, mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46=d（v1,v1）+w13=3 。P(V4)v2v8v7v6v5v963623410231262410P(V1)P(V3)1663.最短路徑問題 在下述的Dijkstra算法中，

27、以P，T 分別表示某一個點的P 標號，T 標號。Si表示在第i步時，具有P 標號點的集合，為了在算出從vs到各點的距離的同時，也找出從vs到各點的最短路，于是，給每一個點v一個值。當算法結束時，如果(v)= m，則表示在從vs到v 的最短路上，v 的前一個點是vm。如果(v)=M，則表示在圖D 中不含有從vs 到達v 的路。(v)=0，表示v=vs。67Dijkstra算法的步驟如下：開始（i=0） 令S0=vs，P（vs）=0，(vs)=0，對每一個v vs，令T（v）=+，(v)=M ，令k=s；（1）如果Si=V，則算法結束，對每一個vSi，d（vs,v）=P（v）。否則轉入（2）；（2

28、）考察每一個使(vk,vj)A，且vjSi的點vj，如果T(vj)P(vk)+wkj ，則把T(vj)改變?yōu)镻(vk)+wkj，把(vj)改變?yōu)閗，否則轉入（3）；683.最短路徑問題（3）令T(vji)=minT(vj)vjSi，如果T(vji)+，則把vji的T 標號改變?yōu)镻 標號P(vji)=T(vji)，令Si+1=Sivji，k=ji，把i換成i+1，轉入（1）；否則結束。這時，對vSi，d(vs,v) = P(v)； 對vSi，d(vs,v) =T(v)。693.最短路徑問題用Dijkstra算法求解例8.6。vs為起點:開始, s =1, i=0; S0=v1, P(v1)=0,

29、 (v1)=0, T(vi)=+,(vi)=M, i=2,3,9, k=1。(2) (v1,v2)A，v2S0，P(v1)+w12w32+P(v3)，將T(v2)改變?yōu)镻(v3)+w32=5,(v2)改變?yōu)?。（3）在所有的T標號中，T(v2)=5最小，于是令P(v2)=5，S3=v1,v4,v3，k=2。 i=3：（2）將T(v5)改變?yōu)镻(v2)+w25=6，(v5) 改變?yōu)?。（3）在所有的T標號中，T(v5)=6最小，于是令P(v5)=6，S4=v1,v4,v3，k=5。723.最短路徑問題（2）將T(v6)，T(v7)，T(v8)分別改變?yōu)?0,9，12，將(v0)，(v7)，(v8

30、)改變?yōu)?。（3）在所有的T標號中，T(v7)=9最小，于是令P(v7)=9，S5=v1,v4,v3,v2,v5,v7，v=7。 i=5：（2）（v7,v8）A，v8S5，但是T(v8) w78+P(v7)，故T(v8)不變。（3）在所有的T標號中，T(v6)=10最小，于是,令P(v6)=10，S6=v1,v4,v3,v2,v5,v7, v6， k=6。733.最短路徑問題 i=6：（2）從v6出發(fā)沒有弧指向不屬于S6的點，因此轉入（3）。（3）在所有的T標號中，T(v8)=12最小，令 P(v8)=12，S7=v1,v4,v3,v2,v5,v7,v6,v8， k=8。 i=7： 僅有T標號

31、的點為v9，T（v9）=+，算法結束。 此時，把P標號和值標在圖中，如圖8-15所示74例題求解圖示（1）v4v2v8v7v6v5v963623410231262410圖8-15T(V6)= +T(V7)= +(V1)=0P(V1)=0P(V4)=1(V4)=1(V6)=M(V5)=MT(V2)= 6T(V5)= +T(V8)= +(V7)=M(V2)=1(V8)=MT(V9)=+(V9)=MT(V3)= 3(V3)=11i = 0 S1=S0v4=v1,v4v1v375例題求解圖示（2）v4v2v8v7v6v5v963623410231262410圖8-15T(V6)=11T(V7)=+(V

32、1)=0P(V1)=0P(V4)=1(V4)=1(V6)=4(V5)=MT(V2)=6T(V5)=+T(V8)=+(V7)=M(V2)=1(V8)=MT(V9)=+(V9)=MP(V3)=3(V3)=11i = 1 S2=S1v3=v1,v4,v3v1v376例題求解圖示（3）v4v2v8v7v6v5v963623410231262410圖8-15T(V6)=11T(V7)=+(V1)=0P(V1)=0P(V4)=1(V4)=1(V6)=4(V5)=MP(V2)=5T(V5)=+T(V8)=+(V7)=M(V2)=3(V8)=MT(V9)=+(V9)=MP(V3)=3(V3)=11i = 2

33、S3=S2v2=v1,v4,v3,v2v1v377例題求解圖示（4）v4v2v8v7v6v5v963623410231262410圖8-15T(V6)=11T(V7)=+(V1)=0P(V1)=0P(V4)=1(V4)=1(V6)=4(V5)=2P(V2)=5P(V5)=6T(V8)=+(V7)=M(V2)=3(V8)=MT(V9)=+(V9)=MP(V3)=3(V3)=11i = 3 S4=S3v5=v1,v4,v3,v2,v5v1v378例題求解圖示（5）v4v2v8v7v6v5v963623410231262410圖8-15T(V6)=10P(V7)=9(V1)=0P(V1)=0P(V4

34、)=1(V4)=1(V6)=5(V5)=2P(V2)=5P(V5)=6T(V8)=12(V7)=5(V2)=3(V8)=5T(V9)=+(V9)=MP(V3)=3(V3)=11i = 4 S5=S4v7=v1,v4,v3,v2,v5,v7v1v379例題求解圖示（6）v4v2v8v7v6v5v963623410231262410圖8-15P(V6)=10P(V7)=9(V1)=0P(V1)=0P(V4)=1(V4)=1(V6)=5(V5)=2P(V2)=5P(V5)=6T(V8)=12(V7)=5(V2)=3(V8)=5T(V9)=+(V9)=MP(V3)=3(V3)=11i = 5 S6=S

35、5v6=v1,v4,v3,v2,v5,v7,v6v1v380例題求解圖示（7）v4v2v8v7v6v5v963623410231262410圖8-15P(V6)=10P(V7)=9(V1)=0P(V1)=0P(V4)=1(V4)=1(V6)=5(V5)=2P(V2)=5P(V5)=6P(V8)=12(V7)=5(V2)=3(V8)=5T(V9)=+(V9)=MP(V3)=3(V3)=11i = 6 S7 =S6v8=v1,v4,v3,v2,v5,v7,v6,v8v1v381例題求解圖示（8）v4v2v8v7v6v5v963623410231262410圖8-15P(V6)=10P(V7)=9(

36、V1)=0P(V1)=0P(V4)=1(V4)=1(V6)=5(V5)=2P(V2)=5P(V5)=6P(V8)=12(V7)=5(V2)=3(V8)=5T(V9)=+(V9)=MP(V3)=3(V3)=11最短路：V1-(V4)V3-V2-V5-(V6,V7)V8v1v3823.最短路徑問題 圖8-15中，從v1到v8的最短路：因為(v8)=5，故最短路經(jīng)過點v5；又因為(v5)=2，故最短路經(jīng)過點v2；依次類推，(v2)=3，(v3)=1于是，最短路經(jīng)過點v3，v1。這樣，從v1到v8的最短路是（v1，v3，v2，v5，v8）。同理，可以求出從v1到任一點vi的最短路，顯然不存在從v1到v

37、9的最短路。833.最短路徑問題 對于一個賦權(無向)圖G=(V，E)，因為邊vi,vj可以看作2條?。╲i,vj）和(vj,vi)，并且具有相同的權wij。這樣，在一個賦權（無向）圖中，如果有所有的權wij0，只要將Dijkstra算法中的“(2)看作每一個使(vk,vj)A，且vjSj的點vj”改變?yōu)椤?2)看作每一個使vk,vjE，且vjSj的點vj”而其他的條件不變，同樣可以求出從vs到各點的最短路（對于無向圖叫做最短鏈）。84證明Dijkstra算法。 只須證明vSi, P(v)是從vs到v的最短路權，即P(v)=d(vs.v)。 證:用數(shù)學歸納法。當i=0時，結論顯然成立。假設i=

38、n時，結論成立?？磇=n+1的情形，由于Sn+1=Snvjn,所以只要證明P(vjn)=d(vs,vj)。85 根據(jù)算法，vjm是具有最小T標號的點，即Tn(vjn)=minTn(vj)，其中vjSm.這里，用Tn()表示當i=n時，執(zhí)行步驟（3）時點的T標號。設H是圖D中任意一條從vs到vjn的路。 因為vsSn,而vjn Sn,所以從vs出發(fā)，沿H 必存在一條弧，其始點屬于Sn，而終點不屬于Sn。令（vr,vl）是第一條這樣的弧，于是H =(vsvr,vlvjn), s(H )=S(vs,vr)+wrl+S(vlvjn)。863.最短路徑問題 由歸納假設，P(vr)是從vs到vr的最短路權

39、，于是，有S(H)P(vr) + wrl+S(vlvjn)。根據(jù)算法中的T 標號修改規(guī)則，因為 vrSn, vl Sn, 故 P(vr) + wrl Tn(vl), 而Tn(vl) Tn(vjn)，且S(vlvjn)0，所以S(H) Tn(vjn)+S(vl,vjn) Tn(vjn)。 這樣，就證明了Tn(vjn)是從vs到vjn的最短權。根據(jù)算法，P(vjn)=Tn(vjn),于是就有P(vjn)=d(vs ,vjn)。87Dijkstra算法僅適合于所有的權wij0的情形。如果當賦權有向圖中存在有負權弧時，則該算法失效。 例如圖8-16中，根據(jù)Dijkstra算法，可以得出從v1到v2最短

40、路權是2，但是這顯然不對，因為從v1到v2的最短路是（v1,v3,v2）,權是-1。v1v3v222-3圖8-16883.最短路徑問題Ford(福德)算法: 當賦權有向圖存在負權弧時，求最短路的方法: 首先，設從任一點 vi 到任一點vj 都有一條弧，如果在圖 D 中，（vi,vj）不屬于A,則添加弧(vi,vj),并且令 wij = +.89 從 vs 到 vj 的最短路是從 vs 點出發(fā)，沿著這條路到某個點vi，再沿弧(vi,vj)到點vj。 顯然，從vs到vi的這條路必定是從vs到vi的最短路。否則從vs到vj的這條路將不是最短路。于是，從vs到vj的距離d(vs,vj)滿足以下條件 d

41、(vs,vj)=min d (vs,vi) + wij , i i=1, , p, p = p(D) 903.最短路徑問題這個關系式的解d(vs,v1)d(vs,vp).可利用如下的 遞推公式 求解 d(1)(vs,vj) = wsj , j =1, , p . d(t)(vs,vj) = min d(t-1)(vs,vi)+ wij, t=2,3 i當計算到第k步時,對一切的j =1, , p, 有 d(k)(vs,vj) = d(k-1)(vs,vj ) 則d(k)(vs,vj), j = 1, , p,就是從vs到各點vj的最短路徑的權。91 設C是賦權函數(shù)有向圖D中的一個回路。如果回路

42、C的權S（C）是負數(shù)那么稱C是D中的一個負回路。 可以證明以下的結論： （1） 如果賦權有向圖D不含有負回路，那么從vs到任一點的最短路至多包含P-2個中間點，并且必可取為初等路。此方法有如下結論92 （2）如果賦權有向圖D不含有負回路，那么上述遞推算法至多經(jīng)過P-1次迭代必收斂，可以求出從vs到各個點的最短路權。 （3）如果上述算法經(jīng)過P-1次迭代，還存在在著某個j，使得 d(p)(vs,vj) d(p-1)(vs,vj) ， 那么D中含有負回路。這時，不存在從 vs 到 vj 的路（權無界）。933.最短路徑問題 例8.7: 在如圖8-17所示的賦權有向圖中求從v1到各點的最短路。 解:

43、利用上述遞推公式，將求解結果列出如表8-18所示。 可以看出，當t =4 時，有 d(t)(vs,vj)=d(t-1)(vs,vj) j =1, , 8 因此，表中的最后一列，就是從v1到v1,v2 ,v8的最短路權。943.最短路徑問題v8v2v4v7v5v1v3v6圖8-171111112335522367895終點起點V1V2V3V4V5V6V7V8t=1t=2t=3t=4V10-1-230000V2602-1-5-5-5V3-30-51-2-2-2-2V48023-7-7-7V5-101-3-3V61017-1-1-1V7-105-5-5V8-3-5066wij d(t)(vs,vj)

44、 963.最短路徑問題 為了求出從v1到各個點的最短路，一般采用反向追蹤的方法：如果已知d(vs,vj),那么尋求一個點vk,使得d(vs,vk)+wkj=d(vs,vj),然后記錄下(vk,vj).在看d(vs,vk),尋求一個點vi,使得d(vs,vi)+wik=d(vs,vk)依次類推，一直到達vs為止。這樣，從vs到vj的最短路是（vs ,vi ,vk ,vj）.97在例中，由上表知，d(v1,v8)=6,由于d(v1,v6)+w68 = (-1) + 7 記錄下v6 ;由于d (v1,v3) + w36= d (v1,v6), j記錄下v3; 由于d(v1,v1)+w13=d(v1,

45、v3), 于是，從v1到v8的最短路是 (v1,v3,v6,v8)98計算機程序 1、/view/f5e5781cfad6195f312ba616.html2、/s/blog_4b425443010008ov.html994 .網(wǎng)絡系統(tǒng)的最大流問題 一 引言 在許多實際的網(wǎng)絡系統(tǒng)中都存在著流量和最大流問題。例如鐵路運輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題等等。而網(wǎng)絡系統(tǒng)流最大流問題是圖與網(wǎng)絡流理論中十分重要的最優(yōu)化問題，它對于解決生產(chǎn)實際問題起著十分重要的作用。1004 .網(wǎng)絡系統(tǒng)的最大流問題圖8-18vtv3v2v1v4vs1735108611453Cij 圖8-18是一個網(wǎng)絡?；∨赃叺?/p>

46、權就是對應的容量（最大通過能力）。要求指定一個運輸方案，使得從vs到vt的貨運量最大，這是尋求網(wǎng)絡系統(tǒng)的最大流問題。101 4.網(wǎng)絡系統(tǒng)的最大流問題 二 、基本概念 定義8.5 設賦權有向圖D=(V,A), 在V中指定一個發(fā)點vs和一個收點vt , 其他的點叫做中間點。對于D中的每一個弧 (vi ,vj)A, 都有一個權 cij 叫做弧的容量。我們把這樣的圖 D 叫做一個網(wǎng)絡系統(tǒng)，簡稱網(wǎng)絡，記做D =（V，A，C）。102網(wǎng)絡D上的流 指定義在弧集合A上的一個函數(shù) f = f(vi,vj) = fij ; f(vi,vj)=fij叫做弧在(vi,vj)上的流量。103 4.網(wǎng)絡系統(tǒng)的最大流問題

47、v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fij 圖8-19表示了網(wǎng)絡上的一個流（運輸方案）弧上的流量 fij 就是運輸量例如fs1=5, fs2=3, f13=2等等。vt圖8-19104 4.網(wǎng)絡系統(tǒng)的最大流問題 網(wǎng)絡系統(tǒng)上流的特點： (1)發(fā)點的總流出量和收點的總流入量必相等； (2)每一個中間點的流入量與流出量的代數(shù)和等于零； (3)每一個弧上的流量不能超過它的最大通過能力（即容量）。105 4.網(wǎng)絡系統(tǒng)的最大流問題 定義8.6 網(wǎng)絡上的一個流 f 叫做可行流，如果 f 滿足以下條件： （1）容量條件：對于每一個弧(vi,vj)A,有 0 fij

48、cij ； （2）平衡條件： 對于發(fā)點vs，有fsj -fjs= v( f ) 對于收點vt，有ftj -fjt =-v( f ) 對于中間點，有fij -fji=0 其中發(fā)點的總流量（或收點的總流量） v( f )叫做這個可行流的流量。106 4.網(wǎng)絡系統(tǒng)的最大流問題任意一個網(wǎng)絡上的可行流總是存在的。例如零流 v ( f ) = 0, 就是滿足以上條件的可行流。網(wǎng)絡系統(tǒng)中最大流問題就是在給定的網(wǎng)絡上尋求一個可行流 f,其流量 v ( f ) 達到最大值。 107飽和弧與零流弧 設流 f = fij 是網(wǎng)絡D上的一個可行流。我們把 D 中fij = cij 的弧叫做飽和弧，fij 0 的弧為非

49、零流弧，fij = 0 的弧叫做零流弧。108 4.網(wǎng)絡系統(tǒng)的最大流問題 設是網(wǎng)絡D中連接發(fā)點s和收點vt的一條鏈。定義鏈的方向是從vs到vt，于是鏈上的弧被分為兩類：一是弧的方向與鏈的方向相同，叫做前向弧，前向弧的集合記做+。二是弧的方向與鏈的方向相反，叫做后向弧，后向弧的集合記做-。109在下圖（8-18與8-19合并圖）中，(v4,v3)是飽和弧，其它弧均是非飽和弧、非零流弧。如圖在鏈（vs,v1,v2,v3,v4,vt)中=(v4,v3)； +=(vs,v1),(v1,v2),(v2,v3),(v4,vt)。v3v2v1v4vs（17,2）（3,3）（5,2）（10,5）（8,3）（6

50、,3）（11,6）（4,1）（5,1）（3,2）fijvt110 4.網(wǎng)絡系統(tǒng)的最大流問題 定義：如果鏈滿足以下條件： 1在弧(vi,vj)+上，有0 fij cij ,即+中的每一條弧是非飽和弧。 2在弧(vi,vj)-上，有0 0 。取116 定理8.8實際上提供了一個尋求網(wǎng)絡系統(tǒng)最大流的方法： 如果網(wǎng)絡D 中有一個可行流f，只要判斷網(wǎng)絡是否存在關于可行流f的增廣鏈 。如果沒有增廣鏈，那么f一定是最大流。如有增廣鏈，那么可以按照前面說明，不斷改進和增大可行流f的流量，最終可以得到網(wǎng)絡中的一個最大流。117 三、標號法 用給頂點標號的方法來定義V1*。在標號過程中，有標號的頂點是V1*中的點

51、，沒有標號的點不是V1*中的點。如果 vt 有了標號，則表示存在一條關于 f 的增廣鏈。如果標號過程無法進行下去，并且 vt 未被標號，則表示不存在關于 f 增廣鏈。這樣，就得到了網(wǎng)絡中的一個最大流和最小截集。118 4.網(wǎng)絡系統(tǒng)的最大流問題 1 標號過程 在標號過程中，網(wǎng)絡中的點或者是標號點（分為已檢查和未檢查兩種）。或者是未標號點。每個標號點的標號包含兩部分：第一個標號表示這個標號是從那一點得到的。以便找出增廣鏈。第二個標號是為了用來確定增廣鏈上的調整量。1194.網(wǎng)絡系統(tǒng)的最大流問題 標號過程開始，先給vs標號(0, +)。這時，vs是標號未檢查的點，其他都是未標號點。一般地，取一個標號

52、未檢查點vi，對一切未標號點vj： 1）如果在弧(vi,vj)上，fij 0, 那么給vj標號(-vi, l(vj) )，其中l(wèi)(vj) = min l(vi), fij。這時，vj 成為標號未檢查點。 于是vi成為標號已檢查的點。重復以上步驟，如果所有的標號都已經(jīng)檢查過，而標號過程無法進行下去，則標號法結束。這時的可行流就是最大流。但是，如果vt被標上號，表示得到一條增廣鏈，轉入下一步調整過程。121 2.調整過程 首先按照vt和其他的點的第一個標號，反向追蹤，找出增廣鏈。例如，令vt的第一個標號是vk，則?。╲k,vt）在上。再看vk的第一個標號，若是vi，則弧(vi,vk)都在上。依次類

53、推，直到vs為止。這時，所找出的弧就成為網(wǎng)絡D的一條增廣鏈。取調整量= l(vt),即vt的第二個標號， 4.網(wǎng)絡系統(tǒng)的最大流問題122 fij+，當(vi ,vj)+ 令f ij= fij -，當(vi ,vj)- 其他不變 再去掉所有的標號，對新的可行流 f = f ij ,重新進行標號過程，直到找到網(wǎng)絡D的最大流為止。 4.網(wǎng)絡系統(tǒng)的最大流問題1234.網(wǎng)絡系統(tǒng)的最大流問題V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）(Cij,fij)Vt圖8-21124 例8.8: 求圖8-21的網(wǎng)絡最大流，弧旁的權數(shù)表示（cij , f

54、ij）。用標號法解 解: 1.標號過程。 （1）首先給vs標號（0，+） （2）看vs: 在弧(vs,v2)上, fs2=cs3=3, 不具備標號條件。在弧(vs,v1)上,fs1=10, 故給v2標號（-v1, l(v2)）,其中 l(v2)=minl(v1), f21=min4,1=1. （4）看v2:在?。╲2,v4）上，f24=3 0,故給v3標號（-v2，l(v3),其中 l (v3)=minl(v2),f32=min1,1=1。126 （5）在v3 ,v4中任意選一個，比如v3,在弧( v3 ,vt )上，f3t = 1 c3t = 2, 故給 vt 標號(v3, l(vt),其中

55、 l(vt)=minl(v3),(c3t-f3t)=min1,1=1. 因為vt被標上號，根據(jù)標號法，轉入調整過程。 4.網(wǎng)絡系統(tǒng)的最大流問題127 4.網(wǎng)絡系統(tǒng)的最大流問題V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）( Cij , fij )Vt(V2,1)(0，+)(-V1,1)(Vs,4)(-V2,1)圖8-22(V3,1)128 2.調整過程 從vt開始，按照標號點的第一個標號，用反向追蹤的方法，找出一條從vs到vt的增廣鏈，如圖8-22中雙箭線所示。顯然, +=(vs,v1),(v3,vt),-=(v2,v1),(v3

56、,v2) 取=1，在上調整f，得到 fs1+=1+1=2 在+上 f3t+=1+1=2 在+上 f*= f21-=1-1=0 在-上 f32-=1-1=0 在-上 其他的不變4.網(wǎng)絡系統(tǒng)的最大流問題129 調整后的可行流f*，如圖8.23所示，再對這個可行流從新進行標號過程，尋找增廣鏈。 首先給vs標號（0，+），看vs , 給v1標號（vs , 3）。看v1,在?。╲1,v3）上，f13=c13,弧（v2,v1）上，f21=0,均不符合條件。因此標號過程無法進行下去，不存在從vS到vt的增廣鏈，算法結束。 4.網(wǎng)絡系統(tǒng)的最大流問題1304.網(wǎng)絡系統(tǒng)的最大流問題 這時，網(wǎng)絡中的可行流f*即是最

57、大流，最大流的流量 v ( f * ) = fs1 + fs2 = 5. 同時，也找出D的最小截集（V1，V1），其中V1是標號的集合，V1是未標號的集合。1314.網(wǎng)絡系統(tǒng)的最大流問題V4V1V2V3Vs（2,2）（3,0）（4,3）（3,3）（5,2）（2,2）（5,3）（1,0）Vt( 0,+)(Vs,3)圖8-23(Cij,fij)（1,0）132 圖8-21的另一最大流V4V1V2V3Vs（2,1）（3,0）（4,3）（3,3）（5,1）（2,2）（5,3）（1,1）（1,1）( Cij , fij )Vt(V2,1)(0，+)(-V1,1)(Vs,4)(-V2,1)(V4,2)13

58、3圖8-21的另一最大流(續(xù))V4V1V2V3Vs（2,1）（3,0）（4,4）（3,3）（5,2）（2,2）（5,4）（1,0）（1,1）( Cij , fij )Vt(0，+)(Vs,3)134計算機程序/view/e68b58fe700abb68a982fb89.html/share/detail/32803107135 在實際的網(wǎng)絡系統(tǒng)中，當涉及到有關流的問題的時候，我們往往不僅僅考慮的是流量，還經(jīng)常要考慮費用的問題。比如一個鐵路系統(tǒng)的運輸網(wǎng)絡流，即要考慮網(wǎng)絡流的貨運量最大，又要考慮總費用最小。最小費用最大流問題就是要解決這一類問題。/view/c655c6c76137ee06eff9

59、185e.html5.網(wǎng)絡系統(tǒng)的 最小費用最大流問題136 設一個網(wǎng)絡D = (V1，A，C )，對于每一個弧(vi ,vj)A, 給定一個單位流量的費用bij 0，網(wǎng)絡系統(tǒng)的最小費用最大流問題，是指要尋求一個最大流 f ，并且流的總費用 b ( f ) = bij fij 達到最小。 （vi ,vj）A5.網(wǎng)絡系統(tǒng)的 最小費用最大流問題137 在一個網(wǎng)絡D 中，當沿可行流 f 的一條增廣鏈，以調整量=1改進 f ，得到的新可行流 f 的流量，有 v( f ) = v( f ) + 1， 此時總費用 b( f ) 比 b( f ) 增加了 b(f)-b(f)=bij(fij-fij)- bij

60、(fij-fij)= bij-bij + - + -將bij-bij叫做這條增廣鏈的費用。5.網(wǎng)絡系統(tǒng)的 最小費用最大流問題1385.網(wǎng)絡系統(tǒng)的 最小費用最大流問題 如果可行流在流量為v(f)的所有可行流中的費用最小，并且是關于f 的所有增廣鏈中的費用最小的增廣鏈。那么沿增廣鏈調整可行流f，得到的新可行流f，也是流量為v(f)的所有可行流中的最小費用流。 依次類推，當f是最大流時，就是所要求的最小費用最大流。139 顯然，零流f =0是流量為0的最小費用流。一般地，尋求最小費用流，從零流f=0開始。問題是：如果已知f 是流量為 v ( f ) 的最小費用流，那么就要去尋找關于f 的最小費用增廣