1、圖與網絡分析 (Graph Theory and Network Analysis,圖與網絡的基本知識,最短路問題,樹及最小樹問題,最大流問題,最小費用最大流問題,哥尼斯堡“七橋”難題,一筆畫問題,問題：一個游者怎樣才能一次連續走過這七座橋且每座橋只走一次，回到原出發點,歐拉用A,B,C,D四點表示河的兩岸和小島，用兩點間的聯線表示橋。七橋問題變為,從A,B,C,D任一點出發，能否通過每條邊一次且僅一次，再回到該點,一、 圖與網絡的基本知識 （一）、圖與網絡的基本概念,圖1,圖2,4.一條邊的兩個端點如果相同,稱此邊為環,6.不含環和多重邊的圖稱為簡單圖，含有多重邊的圖稱為多重圖,8.有向完全

2、圖則是指任意兩個頂點之間有且僅有一條有向邊的簡單圖,5.兩個點之間多于一條邊的，稱為多重邊,7.每一對頂點間都有邊相連的無向簡單圖稱為完全圖,有n個頂點的無向完全圖記作Kn,次為零的點稱為弧立點，次為1的點稱為懸掛點。連結懸掛點的邊稱為懸掛邊。次為奇數的點稱為奇點，次為偶數的點稱為偶點,定理2 任何圖中，次為奇數的頂點必為偶數個,有向圖中,所有頂點的入次之和等于所有頂點的出次之和,定理1 任何圖中，頂點次數的總和等于邊數的2倍,圖3,一個圖中任意兩點間至少有一條鏈相連，則稱此圖為連通圖。任何一個不連通圖都可以分為若干個連通子圖，每一個子圖稱為原圖的一個分圖,v4,v6,e2,e1,e3,e4,

3、e5,e6,e7,e8,e9,e10,圖4,例,權矩陣為,鄰接矩陣為,二、 樹及最小樹問題 已知有六個城市，它們之間要架設電話線，要求任意兩個城市均可以互相通話，并且電話線的總長度最短,1、連通且不含圈的無向圖稱為樹,樹中次為1的點稱為樹葉，次大于1的點稱為分支點,一個圖G 有生成樹的充要條件是G 是連通圖,用破圈法求出下圖的一個生成樹,一）破圈法,二）避圈法,某六個城市之間的道路網如下圖所示，要求沿著已知長度的道路聯結六個城市的電話線網，使電話線的總長度最短,求最小樹的方法,一、破圈法：在給定連通圖G中，任取一圈，去掉一條最大權邊（若有兩條或兩條以上的權均是最大權邊，則任意去掉其中一條），在

4、余圖中任取一圈，去掉一條最大權邊，重復下去，直到余圖中無圈為止，即得到圖G的最小樹,二、避圈法：在給定連通圖G中，任取權值最小的一條邊，在未選邊中選一條權值最小的邊，要求所選邊與已選邊不構成圈，重復下去，直到不存在與已選邊不構成圈的邊為止，已選邊與頂點構成的圖T即為所求的最小樹,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,破圈法求最小樹,v1,v2,v3,v4,v5,1,4,2,3,1,3,5,2,避圈法求最小樹,三、最短路問題,最短路問題是重要的優化問題之一，它不僅可以直接應用于解決生產實際的許多問題，如管道鋪設、線路安排、廠區布局、設備更新等，而且經常被作為一個基本工具，

5、用于解決其他的優化問題,Dijkstra標號法,例：如圖所示是某地區交通運輸示意圖，問從v1出發，經那條路線到達v8,才能使總行程最短,例2、 用Dijkstra算法求下圖從v1到v6的最短路,解 （1）首先給v1以P標號，給其余所有點T標號,2,3,4,5,6,7,8,9,10,反向追蹤得v1到v6的最短路為,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求從1到8的最短路徑,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1, w1=0,min c12,c14,c16=min 0+2,0+1,

6、0+3=min 2,1,3=1 X=1,4, p4=1,p4=1,p1=0,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,4,min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2 X=1,2,4, p2=2,p1=0,p4=1,p2=2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3 X=1,2,4,6, p6=3

7、,p2=2,p4=1,p1=0,p6=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 X=1,2,4,6,7, p7=3,p2=2,p4=1,p1=0,p6=3,p7=3,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min c23,c25,c75,c78=min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 X=1,2,4,5,6

8、,7, p5=6,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,4,6,7,min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8 X=1,2,3,4,5,6,7, p3=8,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,min c38,c58,c78=min 8+6,6+4

9、,3+7=min 14,10,11=10 X=1,2,3,4,5,6,7,8, p8=10,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,X=1,2,3,4,6,7,8,1到8的最短路徑為1，4，7，5，8，長度為10,p2=2,p4=1,p1=0,p6=3,p7=3,p5=6,p3=8,p8=10,求從V1 到 V8 的最短路線,由此看到，此方法不僅求出了從V1 到 V8 的最短路長，同時也求出了從V1 到 任意一點 的最短路長。將從V1 到 任一點的最短路權標在

10、圖上，即可求出從V1 到 任一點的最短路線。本例中V1 到 V8 的最短路線是： v1 v2 v5 v6 v8,二）、 逐次逼近法 算法的基本思路與步驟： 首先設任一點vi到任一點vj都有一條弧。 顯然，從v1到vj的最短路是從v1出發，沿著這條路到某個點vi再沿弧(vi,vj)到vj。則v1到vi的這條路必然也是v1到vi的所有路中的最短路。設P1j表示從v1到vj的最短路長，P1i表示從v1到vi的最短路長，則有下列方程： 開始時，令 即用v1到vj的直接距離做初始解。 從第二步起，使用遞推公式： 求 ，當進行到第t步，若出現 則停止計算， 即為v1到各點的最短路長,例2,求圖中v1到 各

11、點的最短路,0，0,v3 ，-5,v1 ，-2,v3 ，-7,v2 ，-3,v4 ，-5,v3 ，-1,v6 ，6,例3、求：5年內，哪些年初購置新設備，使5年內的總費用最小。 解：（1）分析：可行的購置方案（更新計劃）是很多的， 如： 1） 每年購置一臺新的，則對應的費用為： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年購置新的，一直用到第五年年底，則總費用為： 11+5+6+8+11+18 = 59 顯然不同的方案對應不同的費用,2）方法：將此問題用一個賦權有向圖來描述，然后求這個賦權有向圖的最短路。 求解步驟： 1）畫賦權有向圖： 設 Vi 表示第i年初，(

12、Vi ,Vj )表示第i 年初購買新設備用到第j年初（j-1年底），而Wi j 表示相應費用，則5年的一個更新計劃相當于從V1 到V6的一條路。 2）求解 （標號法,W12 =11+5=16 W13 =11+5+6=22 W14 =11+5+6+8=30 W15 =11+5+6+8+11=41 W16 =11+5+6+8+11+18=59,W23 =11+5=16 W24 =11+5+6=22 W25 =11+5+6+8=30 W26 =11+5+6+8+11=41,W45 =12+5=17 W46 =12+5+6=23 W56 =13+5=18,W34 =12+5=17 W35 =12+5+

13、6=23 W36 =12+5+6+8=31,例4、 某工廠使用一種設備，這種設備在一定的年限內隨著時間的推移逐漸損壞。所以工廠在每年年初都要決定設備是否更新。若購置設備，每年需支付購置費用；若繼續使用舊設備，需要支付維修與運行費用，而且隨著設備的老化會逐年增加。計劃期（五年）內中每年的購置費、維修費與運行費如表所示，工廠要制定今后五年設備更新計劃，問采用何種方案才能使包括購置費、維修費與運行費在內的總費用最小,28,v1,v2,v3,v4,v5,v6,23,25,26,29,30,42,60,85,32,44,62,33,45,30,四、最大流問題,是一個增廣鏈,顯然圖中增廣鏈不止一條,容量為

14、24,設,則截集為,容量為20,在此過程中，網絡中的點或為標號點或為未標號點，每個標號點的標號包含兩部分：第一個標號表明它的標號是從哪一點得到的，以便找出增廣鏈，第二個標號是為確定增廣鏈的調整量用的,例：用標號法求下圖所示的網絡最大流,求下圖所示網絡中的最大流，弧旁數為,最小截集,13 (11,9 (9,4 (0,5 (5,6(6,5 (5,5 (4,5 (4,4 (4,4 (3,9 (9,10 (7,截集1,截集2,最小截量為：9+6+5=20,（120,（230,（150,（200,尋找關于f 的最小費用增廣鏈： 構造一個關于f 的賦權有向圖L(f ) ，其頂點是原網絡G的頂點，而將G中的

15、每一條弧 ( vi, vj )變成兩個相反方向的弧（vi， vj）和(vj , vi)，并且定義圖中弧的權lij為： 1.當 ，令 2.當（vj，vi）為原來網絡G中（vi， vj）的反向弧，令 在網絡G中尋找關于f 的最小費用增廣鏈等價于在L(f )中尋求從vs 到vt 的最短路,步驟： （1）取零流為初始可行流 ，f (0) =0。 （2）一般地，如果在第k-1步得到最小費用流 f (k-1)，則構造圖 L( f (k-1) )。 （3）在L( f (k-1) )中，尋求從vs到vt的最短路。若不存在最短路，則f (k-1)就是最小費用最大流；否則轉(4)。 （4）如果存在最短路，則在可行

16、流f (k1)的圖中得到與此最短路相對應的增廣鏈，在增廣鏈上，對f (k1)進行調整，調整量為,令,得到新可行流f (k) 。對f (k)重復上面步驟，返回（2,例8.11 求網絡的最小費用最大流，弧旁權是（bij , cij,第六節 中國郵遞員問題,一、 歐拉回路與道路 定義8.18 連通圖G中，若存在一條道路，經過每邊一次且僅一次，則稱這條路為歐拉道路。若存在一條回路，經過每邊一次且僅一次，則稱這條回路為歐拉回路。 具有歐拉回路的圖稱為歐拉圖。 定理8.7 一個多重連通圖G是歐拉圖的充分必要條件是G中無奇點。 推論 一個多重連通圖G有歐拉道路的充分必要條件是G有且僅有兩個奇點,二、 奇偶點圖上作業法 （1）找出圖G中的所有的奇頂點，把它們兩兩配成對，而每對奇點之間必有一條通路，把這條通路上的所有邊作為重復邊追加到圖中去，這樣得到的新連通圖必無奇點。 （2）如果邊e=（u,v）上的重復邊多于一條，則可從重復邊中去掉偶數條，使得其重復邊至多為一條，圖中的頂點仍全部都是偶頂點。 （3）檢查圖中的每一個圈，