1、第八章圖與網絡分析 圖的基本概念與模型 樹圖和圖的最小部分樹 最短路問題 網絡最大流問題 最小費用最大流問題 第八章圖與網絡分析 圖的基本概念與模型 樹圖和圖的最小部分樹 最短路問題 網絡最大流問題 最小費用最大流問題 圖論是應用非常廣泛的運籌學分支，它已經廣泛地應用于物理學控制論，信息論，工程技術，交通運輸，經濟管理，電子計算機等各項領域。對于科學研究，市場和社會生活中的許多問題，可以同圖論的理論和方法來加以解決。例如，各種通信線路的架設，輸油管道的鋪設，鐵路或者公路交通網絡的合理布局等問題，都可以應用圖論的方法，簡便、快捷地加以解決。引 言 1736年瑞士科學家歐拉發表了關于圖論方面的第一

2、篇科學論文，解決了著名的哥尼斯堡七座橋問題。即一個漫步者如何能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發地。如圖1所示。引例1歐拉將這個問題抽象成一筆畫問題。即能否從某一點開始不重復地一筆畫出這個圖形，最終回到原點。歐拉在他的論文中證明了這是不可能的，因為這個圖形中每一個頂點都與奇數條邊相連接，不可能將它一筆畫出，這就是古典圖論中的第一個著名問題。 在實際的生產和生活中，人們為了反映事物之間的關系，常常在紙上用點和線來畫出各式各樣的示意圖。引例2左圖是我國北京、上海、重慶等十四個城市之間的鐵路交通圖，這里用點表示城市，用點與點之間的線表示城市之間的鐵路線。諸如此類還有城市中的市政管

3、道圖，民用航空線圖等等。連云港武漢南京徐州上海北京塘沽青島濟南天津鄭州 有六支球隊進行足球比賽，我們分別用點v1v6表示這六支球隊，它們之間的比賽情況，也可以用圖反映出來，已知v1隊戰勝v2隊，v2隊戰勝v3隊，v3隊戰勝v5隊，如此等等。這個勝負情況，可以用下圖所示的有向圖反映出來。引例3v3v1v2v4v6v5圖的基本概念與模型點：研究對象（車站、國家、球隊）；點間連線：對象之間的特定關系（陸地間有橋、鐵路線、兩球隊比賽及結果)。對稱關系：橋、道路、邊界；用不帶箭頭的連線表 示，稱為邊。非對稱關系：甲隊勝乙隊，用帶箭頭的連線表示，稱為弧。圖：點及邊（或弧）組成。注意：一般情況下，圖中的相對

4、位置如何，點與點之間線的長短曲直，對于反映研究對象之間的關系，顯的并不重要，因此，圖論中的圖與幾何圖，工程圖等本質上不同。對稱關系非對稱關系無向圖：圖由點和邊所構成的， 記作G = V ,E(V是點的集合，E是邊的集合) 連接點vi,vjV的邊記作eij=vi,vj，或者vj,vi。有向圖：圖是由點和弧所構成的， 記作D=V ,A(V是點的集合，A是弧的集合) ， 一條方向從vi指向vj的弧，記作(vi,vj)。 圖的相關概念網絡圖：給圖中的點和邊賦予具體的含義和權數，如距離， 費用，容量等，記作N.圖的相關概念若邊eij=vi,vjE，稱vi，vj是eij的端點，也稱vi，vj是相鄰的。稱e

5、ij是點vi（及點vj）的關聯邊。若兩條邊有一個公共的端點，則稱這兩條邊相鄰。vivjevi，vj相鄰 e 與vi，vj關聯vie1vjvke2點與邊關聯點與點相鄰邊與邊相鄰若某條邊兩個端點相同，稱這條邊為環。若兩點之間有多于一條的邊，稱這些邊為多重邊。 無環、無多重邊的圖稱為簡單圖。無環、但允許有多重邊的圖稱為多重圖。v1e1e2e3v2v3e5e4v4v5注：無特別聲明我們今后討論的圖都是簡單圖圖的相關概念 圖G中以點v為端點的邊的數目，稱為v在G中的次(度）， 記為d（v）。d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1 次為1 的點為懸掛點，懸掛點的關聯邊稱為懸掛邊，次

6、為零的點稱為孤立點。v1e1e2e3v2v3e5e4v4v5次為奇數的點稱為奇點，否則稱為偶點。圖的相關概念給定圖G=（V，E），若圖G=（V，E），其中VV，E E ，則稱G是G的子圖。給定圖G=（V，E），若圖G=（V，E），其中EE，則稱G是G的一個支撐子圖（部分圖）。點全部保留（a）（b）子圖（c）部分圖子圖與部分圖（支撐子圖）圖的連通性鏈：設圖G=（V，E）中有一個點、邊交替序列 v1 ,e1,v2,vn-1,en-1 ,vn，若ei=(vi,vi+1)，即這(n-1)條邊把n個頂點串連起來，我們稱這個交替序列為圖G中的一條鏈，而稱點v1,vn為該鏈的兩個端點。對于簡單圖鏈也可以僅用

7、點的序列來表示。如果一條鏈的兩個端點是同一個點，則稱它為閉鏈或圈；如果一條鏈的各邊均不相同，則稱此鏈為簡單鏈；更若一條鏈的各點、各邊均不相同，則稱該鏈為初等鏈。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9簡單鏈：1=（v2，v1，v3，v6，v4，v3，v5）初等鏈：2=（v2，v1，v3，v5）圖的連通性最短鏈:網絡中鏈上權值的和稱為鏈的長度，以點v1,vn為端點的諸鏈中長度最短的鏈稱為這兩點的最短鏈。連通圖：如果圖G=（V，E）中的任意兩點都是其某一條鏈的兩個端點，則稱圖G是連通圖，否則，稱圖G是不連通的。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6

8、e8e9為不連通圖，有兩個連通分圖組成圖的矩陣表示圖的矩陣表示主要方法有：權矩陣、鄰接矩陣。權矩陣網絡圖N=（V，E），邊vi，vj的權為wij ，構造矩陣稱矩陣A為網絡N的權矩陣。v4v5v2v1v3234567894其權矩陣為： 注：當G為無向圖時，權矩陣為對稱矩陣。圖G=（V，E），p=n，構造矩陣稱矩陣A為G的鄰接矩陣。鄰接矩陣？vi與vj不相鄰圖的矩陣表示其鄰接矩陣為： v4v5v2v1v3注：當G為無向圖時，鄰接矩陣為對稱矩陣。 思考：有甲、乙、丙、丁、戊、己六名運動員報名參加A、B、C、D、E、F六個項目的比賽，下表中打的是個運動員報名參加比賽的項目，問六個項目的比賽順序應如何安

9、排？做到每名運動員都不連續地參加兩項比賽。ABCDEF分析：點表示項目，邊表示兩個項目有同一名運動員參加目的：在圖中找出點序列，使得依次排列的兩個點不相鄰，就找到了每名運動員不連續參加兩項比賽的安排方案A、C、B、F、E、D(不唯一)第八章圖與網絡分析圖的基本概念與模型樹圖和圖的最小部分樹最短路問題網絡最大流問題最小費用最大流問題 第八章圖與網絡分析圖的基本概念與模型樹圖和圖的最小部分樹最短路問題網絡最大流問題最小費用最大流問題 7個村莊要在他們之間架設電話線，要求任何兩個村莊都可以互相通電話(允許中轉)，并且電話線根數最少？引例村莊1村莊4村莊3村莊6村莊2村莊5村莊7分析：用七個點代表村莊

10、，如果在某兩個村莊之間架設電話線，則相應的在兩點之間連一條邊，這樣電話線網就可以用一個圖來表示，并且滿足如下要求：連通圖圖中有圈的話，從圈中任去掉一條邊，余下的圖仍連通為什么？樹村莊1村莊4村莊3村莊6村莊2村莊5村莊7如果G=（V，E）是一個無圈的連通圖，則稱G為樹。 樹中必存在次為1的點（懸掛點）樹中任兩點必有一條鏈且僅有一條鏈；在樹的兩個不相鄰的點之間添加一條邊，就得到一個圈； 反之，去掉樹的任一條邊，樹就成為不連通圖；n個頂點的樹有（n-1）條邊。樹是無圈連通圖中邊數最多的，也是最脆弱的連通圖！145241575237圖的部分樹（支撐樹）如果圖G=（V，E）的部分圖G=（V，E）是樹，

11、 則稱G是G的部分樹（或支撐樹）。村莊1村莊4村莊3村莊6村莊2村莊5村莊7部分樹上各樹枝上權值的和稱為它的長度，其中長度最短的部分樹，稱其為該圖的最小部分樹（最小支撐樹）。點保留邊可去仍是樹不唯一思考：如何鋪設電話線，使得電話線長度最少？ijkml最小部分樹的求法定理：圖中任一個點i，若j是與相鄰點中距離最近的， 則邊i,j一定必含在該圖的最小部分樹內。推論：把圖的所有點分成 和 兩個集合，則兩集合之間連線的最短邊一定包含在最小部分樹內。避圈法破圈法227541435175ABCDEST算法的步驟： 1、在給定的賦權的連通圖上任選一點vi ,其余點在 中。 2、從 與 的連線中找出權數最小的

12、邊vi, vj，這條邊一定包含在最小部分樹內，做以標記。 3、令 vi ， ； 4、重復2、3兩步，直至所有點都包含在 中為止。vi求解最小生成樹的避圈算法S77ABCDEST2254143515求解最小生成樹的破圈算法算法的步驟： 1、在給定的賦權的連通圖上任找一個圈。 2、在所找的圈中去掉一個權數最大的邊（如果有兩條或兩條以上的邊都是權數最大的邊，則任意去掉其中一條）。 3、如果所余下的圖已不包含圈，則計算結束，所余下的圖即為最小生成樹，否則返回第1步。第八章圖與網絡分析圖的基本概念與模型樹圖和圖的最小部分樹最短路問題網絡最大流問題最小費用最大流問題 第八章圖與網絡分析圖的基本概念與模型樹

13、圖和圖的最小部分樹最短路問題網絡最大流問題最小費用最大流問題 什么是最短路問題？固定起點的最短路 Dijkstra(狄克斯拉) (荷蘭)算法：標號法 逐次逼近算法(Ford(美國)算法)：修正標號法每 對 頂 點 之 間 的 最 短 路 路矩陣算法(Floyd(佛洛伊德)算法)最短路問題最短路問題提出 在現實生活中，除公路運輸網絡、電訊網絡等網絡圖以外，還有輸油管線這樣的圖。在輸油管線圖中，為反映油的輸送情況，兩點間不僅有連線，線上往往還標有箭頭，以表示油的流動方向。又如，指揮系統圖、控制系統圖等圖中都標有指向。從這樣的一類圖中就可以概括為有向圖的概念。有向圖由點集 和V 中元素的有序對的一個

14、集合 所組成的二元組稱為有向圖，記為D=（V，A）。 其中 V中的元素 vi叫做頂點， A中元素aij叫做以vi為始點（尾），vj為終點（首）的弧。 aij與aji作為具有不同指向的弧是不同的。有向網絡與混合圖如果在圖D=（V，A）中，給每一弧賦予權值，如 將弧aij=(vi,vj)有權值 wij，記為w(aij)=wij則賦權有向圖D=（V，A）稱為有向網絡，在不至于混淆時，也簡稱網絡。混合圖如果一個圖中既有邊，也有弧，那么稱這種圖為混合圖。它往往出現在既有單行線，又有雙行線的交通圖中。12534372最短路問題引例下圖為單行線交通網，每弧旁的數字表示通過這條線所需的費用。現在某人要從v1出

15、發，通過這個交通網到v8去，求使總費用最小的旅行路線。v2v523464v3v1v4v6121061210v8v9v72363從v1到v8：P1=（v1，v2，v5，v8） 費用 6+1+6=13P2=（v1，v3，v4， v6， v7， v8） 費用 3+2+10+2+4=21P3= 從v1到v8的旅行路線 從v1到v8的路。旅行路線總費用 路上所有弧權之和。最短路問題中，不考慮有向環、并行弧。v2v523464v3v1v4v6121061210v8v9v72363幾個概念路：設p是D中一個首尾相連的弧的集合，如果vs是它的第一條弧的始點，vt是它的最后一條弧的終點，則稱它是以點vs為始點，

16、以點vt為終點的一條路。路長：路p中所有弧的權值的和稱為路p的長，記為設圖D=（V，A）是一有向網絡 v2v523464v3v1V4 v6121061210v8v9v72363設P是以點vs為始點，以點vt為終點的所有路的集合， 如果 ,且 ，則稱p0是以點vs 為始點，以點vt為終點的最短路。而稱其路長為點 vi到點vj的距離，記為 。幾個概念注意：在有向網絡中,一般最短路及一點到另一點的距離 最短路問題是重要的最優化問題之一，可以直接應用于解決生產實際的許多問題:管道鋪設、線路安排、廠區布局等。而且經常被作為一個基本工具來解決其他的優化問題。最短路問題求解方法Dijkstra算法逐步逼近算

17、法路矩陣算法最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法求解最短路問題的Dijkstra算法條件：當所有 wij 0 時，用來求給定點vs到任一 個點vj 最短路的公認的最好方法。事實：如果P是D中從vs到vj的最短路，vi是P中的一 基解 個點，那么，從vs沿P到vi的路是從vs到vi的最基解 短路。 Dijkstra算法是Dijkstra在1959年提出的，可用于求解指定兩點間的最短路問題，或從指定點到其余各點的最短路問題。由于其以標號為主要特征，又稱為標號法。v1v2v3v4v5最短路的子路是最短路Dijkstra算法基本思想 從始點vs出發，逐步順序地向外探尋，每向外延

18、伸一步都要求是最短的。執行過程中，與每個點對應，記錄下一個數(稱為這個點的標號) 1.標號 P（固定標號或永久性標號）從始點vs到該標號點vj的最短路權P (vj) 。 2.標號 T（臨時性標號）從始點vs到該標號點vj的最短路權上界T (vj) 。j ,P (vj)j, T (vj) 該方法的每一步就是去修改T標號，并且把某一個具T標號的點改變為具有P標號的點，從而使D中具P標號的頂點數多一個，至多經過n-1步，就可以求出始點vs到各點的最短路。前點標號j 表示始點vs到vj的最短路上vj的前一點。Dijkstra算法步驟： 第二步：考慮滿足條件 的所有點； vi具有P 標號;vj具有T 標

19、號; 修改vj的T標號為 ，并將結果仍記為T(vj)第一步：始點標上固定標號 ,其余各點標臨時性標號 T(vj)=, j1; 第三步：若網絡圖中已無T標號點，停止計算。否則, 令 ，s為T標號點集, 然后將 的T 標號改成P 標號 ，轉入第二步。v1,6圖上標號法v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, M, v1,3M, M, M, v1,1v1,1永久標號永久標號臨時標號v1出發到v8去，使總費用最小的旅行路線v1,6圖上標號法v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, M, v1,3M, M, M,

20、 0,0v1,1v4,11v1,3永久標號臨時標號v1出發到v8去，使總費用最小的旅行路線v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, v1,1M, M,M, 1,3圖上標號法v4,11v1,3v1,6v3,5v3,5永久標號臨時標號v1出發到v8去，使總費用最小的旅行路線v5v223464v3v1v41210 6 1210v8v9v72363v60,0M, v4,11v1,1M, M, M, v1,3圖上標號法v3,5v2, 6v2, 6永久標號臨時標號v1出發到v8去，使總費用最小的旅行路線v5v223464v3v1v41210 6 1210v8v

21、9v72363v60,0M, v4,11v1,1M, M, v1,3v5,12v5,9v5,9圖上標號法v3,5v2, 6永久標號臨時標號v5,10v1出發到v8去，使總費用最小的旅行路線v5v223464v3v1v41210 6 1210v8v9v72363v60,0v5,10v1,1M, v5, 12 v1,3v5,9v5, 12 v3,5v2, 6圖上標號法永久標號臨時標號v5,10v1出發到v8去，使總費用最小的旅行路線v5v223464v3v1v41210 6 1210v8v9v72363v60,0v5,10v1,1M, v1,3v5, 12 v3,5v2, 6圖上標號法v5,9永久

22、標號臨時標號標號結束 反向追蹤v1出發到v8去，使總費用最小的旅行路線Dijkstra算法步驟： 第二步：考慮滿足條件 的所有點； vi具有P 標號;vj具有T 標號; 修改vj的T標號為 ，并將結果仍記為T(vj)第一步：始點標上固定標號 ,其余各點標臨時性標號 T(vj)=, j1; 第三步：若網絡圖中已無T標號點，停止計算。否則, 令 ，s為T標號點集, 然后將 的T 標號改成P 標號 ，轉入第二步。例 求如下交通網絡中v1 到各點間最短路路長。Dijkstra算法（標號法）算例31025v4v1v2v5v312262448混合圖無向網絡:負權弧時。wijvivjwijwijvjvi無向

23、網絡中，最短路最短鏈。 多個點對之間最短路？v1v2v312-3Dijkstra算法失效Dijkstra算法注意的問題逐步逼近算法路矩陣算法5727461263202657710v3v1v2v4v5v6v7練習：求如下無向網絡中v1到v7的最短鏈Dijkstra算法求最短鏈最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法逐次逼近算法思想 該公式表明， P(1)1j中的第j個分量等于P(0)1j的分量與基本表(權矩陣)中的第j列相應元素路長的最小值，它相當于在v1與vj之間插入一個轉接點(v1,v2,vn中的任一個，含點v1

24、與vj)后所有可能路中的最短路的路長；每迭代一次，就相當與增加一個轉接點，而P(k)1j中的每一個分量則隨著k的增加而呈不增的趨勢！v1v2v312-3用于計算帶有負權弧指定點v1到其余各點的最短路j=1,2,n. k=1,2,tn.2.計算逐次逼近算法基本步驟 j=1,2,n.1.令其元素即是v1到vj的最短路長。3.當出現時，v1v2v312-3例 計算從點v1到所有其它頂點的最短路解：初始條件為 以后按照公式 進行迭代。 直到得到 ，迭代停止。v1v2v3v4v6v5v8v72-35467-24-3342-1v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wijv1v2v

25、3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-204200利用下標追蹤路徑基本表空格為無窮大v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wijv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-204200利用下標追蹤路徑基本表空格為無窮大最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法最短路問題求解方法Dijkstra算法逐步逼近算法路矩陣算法 某些問題需要求網絡上任意兩點間的最短路。當然，它也可以用標號算法依次改變始點的辦法來計算，但是比較麻煩。 這里介紹Fl

26、oyd在1962年提出的路矩陣法，它可直接求出網絡中任意兩點間的最短路。Floyd算法(路矩陣法)思想 考慮D中任意兩點vi，vj，如將D中vi，vj以外的點都刪掉，得只剩vi，vj的一個子網絡D0，記wij為弧（ vi，vj）的權。 在D0中加入v1及D中與vi，vj，v1相關聯的弧，得D1，D1中vi到vj的最短路記為 ,則一定有vivjv1wijFloyd算法(路矩陣法)思想 網絡D=（V，A，W），令U=(dij)nn， 表示D中vi到vj的最短路的長度。dij 再在D1中加入v2及D中與vi，vj，v1， v2相關聯的弧，得D2，D2中vi到vj的最短路長記為 ，則有Floyd算法(

27、路矩陣法)思想Floyd算法(路矩陣法)步驟設有有向網絡D=（V，A），其權矩陣為A=(aij)nn，如下構造路矩陣序列：則n階路矩陣D(n)中的元素d(n)ij就是vi到vj的最短路的路長。 令權矩陣A為初始路矩陣D（0），即令D（0）=A2. 依次計算K階路矩陣D（K）=（d(k)ij）nn, k=1,2,n，這里路矩陣序列的含義 K階路矩陣D（K） 其中的元素表示相應兩點間可能以點v1、v2、vk為 轉接點的所有路中路長最短的路的路長。 D（0） 其中的任一元素表示相應兩點間無轉接點時最短路路長。一階路矩陣D（1） 其中的元素表示相應兩點間可能以點v1為轉接點的所有路中路長最短的路的路長

28、；為使計算程序化，轉接點按頂點下標的順序依次加入n階路矩陣D(n) 其中的元素d(n)ij就是vi到vj的可能以點v1、v2、vn為轉接點的所有路中路長最短的路的路長。既是vi到vj的最短路的路長。例 求如下交通網絡中各對點間最短路路長。該圖的權矩陣為：Floyd算法(路矩陣法)算例31025v4v1v2v5v312262448例 求如下交通網絡中各對點間最短路路長。Floyd算法(路矩陣法)算例31025v4v1v2v5v312262448利用公式發現第一行，第一列元素不變31025v4v1v2v5v312262448利用公式發現第二行，第二列元素不變31025v4v1v2v5v312262448利用公式發現第三行，第三列元素不變31025v4v1v2v5v312262448利用公式發現第四行，第四列元素不變31025v4v1v2v5v31226244831025v4v1v2v5v312262448D(5)中的元素給出相應兩點間的最短路，其下標給出最短路個頂點下標,比如：6254已知有7個村子，相互間道路的距離如下圖示。擬合建一所小學，已知A處有小學生30人，B處40人，C處25人，D處20人，E處50人，F處60人， G處60人,問小學應建在哪一個村子，使學生上學最方便（原則所有人走的總路程最短；盡可能公平。）。