1、第八章 圖與網(wǎng)絡分析,主要內(nèi)容： 8.1 圖與網(wǎng)絡的基本知識,8.2 最短路問題,8.3 最大流問題,8.4 最小費用流問題,8.1 圖與網(wǎng)絡基本知識,一、引言 1。產(chǎn)生 哥尼斯堡七橋難題,例8-1：哥尼斯堡七橋問題,哥尼斯堡（現(xiàn)名加里寧格勒）是歐洲一個城市，Pregei河把該城分成兩部分，河中有兩個小島，十八世紀時，河兩邊及小島之間共有七座橋，當時人們提出這樣的問題：有沒有辦法從某處（如A）出發(fā)，經(jīng)過各橋一次且僅一次最后回到原地呢？,數(shù)學家Euler在1736年解決：,8.1 圖與網(wǎng)絡基本知識,二、圖與網(wǎng)絡的基本概念,8.1 圖與網(wǎng)絡基本知識,圖論是專門研究圖的理論的一門數(shù)學分支，主要研究點

2、和線之間的 幾何關系。,圖論是離散數(shù)學的范疇。,8.1 圖與網(wǎng)絡基本知識,一、圖的有關概念,表示為： G=（V，E） V-點集合 E-邊集合,簡稱圖，由點和邊組成。,無向圖：,帶箭頭的聯(lián)線，表示不對稱關系。,?。?不帶箭頭的聯(lián)線，表示對稱關系。,邊：,反映對象之間關系的一種工具。,圖：,表示兩個對象之間的某種特定關系。,連線：,表示研究對象。,點：,8.1 圖與網(wǎng)絡基本知識,二、無向圖的有關概念：,有多重邊的圖。,多重圖：,無環(huán)，無多重邊的圖。,簡單圖：,兩點之間多于一條邊。,多重邊：,若u=v， e是環(huán)。,環(huán)：,e是點u，v的關聯(lián)邊。,關聯(lián)邊：,e=u,vE， 則u,v是e的端點，稱u,v相

3、鄰。,端點：,8.1 圖與網(wǎng)絡基本知識,二、無向圖的有關概念：,次為偶數(shù)的點。,偶點：,次為奇數(shù)的點。,奇點：,次為0的點。,孤立點：,懸掛點的關聯(lián)邊。,懸掛邊：,次為1的點。,懸掛點：,例: 如圖示 d(v1)=4，d(v4)=4,以點v為端點的邊數(shù)稱為v的次。表示為： d(v),次：,8.1 圖與網(wǎng)絡基本知識,二、無向圖的有關概念,定理8-2：在任意一個圖中，奇頂點的個數(shù)必為偶數(shù)。,定理8-1：在一個圖中，所有頂點次的和等于邊的兩倍。,圈中邊均不相同。,簡單圈：,鏈中邊均不相同。,簡單鏈：,圈中無重復的點和邊。,初等圈：,鏈中無重復的點和邊。,初等鏈：,如一條鏈中起點和終點重合。,圈：,點

4、邊交錯序列。,鏈：,8.1 圖與網(wǎng)絡基本知識,二、無向圖的有關概念：,圖G去掉點v及v的關聯(lián)邊的圖。,G-v：,對G=（V，E）， 若G=(V，E), 使V=V，E是E的子集，則G是G的一個支撐子圖。,支撐子圖：,對不連通圖，每一連通的部分稱為一個連通分圖。,連通分圖：,任意兩點之間至少有一條鏈。,連通圖：,例8-2：有7個人圍桌而坐，如果要求每次相鄰的人都與以前完全不同，試問不同的就座方案共有多少種？,8.1 圖與網(wǎng)絡基本知識,提示：用頂點表示人，用邊表示兩者相鄰。共有3種方案。,8.1 圖與網(wǎng)絡基本知識,三、有向圖的有關概念:,有多重弧。,多重有向圖：,無自環(huán)，無多重弧。,簡單有向圖：,圈

5、中無重復的點和弧。,初等圈（回路）：,鏈中無重復的點和弧。,初等鏈（道路）：,如一條鏈中起點和終點重合。,圈（回路）：,點弧交錯序列。,鏈（道路）：,對弧a=(u，v)， u為a的始點，v為a的終點。,始點和終點：,由點和弧組成。表示為：D=（V，A） V-點集合 A-弧集合,有向圖：,樹：一個無圈的無向連通圖稱為樹。如果一個無圈的圖中每一個分支都是樹，則稱圖為森林。,8.1 圖與網(wǎng)絡基本知識,四、 樹的概念,樹的性質(zhì)： 在圖中任意兩點之間必有一條而且只有一條通路。,2）在圖中劃去一條邊，則圖不連通。,3）在圖中不相鄰的兩個頂點之間加一條邊，可得一個且僅得一個圈。,4）圖中邊數(shù)為：p-1（p為

6、頂點數(shù)）,例8-4：一個班級的學生共計選修A、B、C、D、E、F六門課程，其中一部分人同時選修D(zhuǎn)、C、A，一部分人同時選修B、C、F，一部分人同時選修B、E，還有一部分人同時選修A、B，期終考試要求每天考一門課，六天內(nèi)考完，為了減輕學生負擔，要求每人都不會連續(xù)參加考試，試設計一個考試日程表。,8.1 圖與網(wǎng)絡基本知識,解：以每門課程為一個頂點，共同被選修的課程之間用邊相連，得圖，按題意，相鄰頂點對應課程不能連續(xù)考試，不相鄰頂點對應課程允許連續(xù)考試，因此，作圖的補圖，問題是在圖中尋找一條哈密頓道路，如CEAFDB，就是一個符合要求的考試課程表。,8.1 圖與網(wǎng)絡基本知識,8.1 圖與網(wǎng)絡基本知識

7、,四、 樹的概念,圖的支撐樹（生成樹）： 1）定義:設圖T=(V，E) 是圖G=(V,E)的支撐子圖,如果T是一個樹, 則稱T是G的一個支撐樹。,最優(yōu)樹（最小生成樹、最小支撐樹）： 在賦權圖G中，一棵生成樹所有樹枝上權的總和，稱為生成樹的權。具有最小權的生成樹，稱為最優(yōu)樹（或最小樹）。,2）定理5：圖G=（V，E）有支撐樹的充分必要條件是G是連通的。,四、 樹的概念 求最小生成樹的方法有破圈法和避圈法。,8.1 圖與網(wǎng)絡基本知識,五、歐拉回路與中國郵遞員問題,8.1 圖與網(wǎng)絡基本知識,一筆劃問題 歐拉鏈（道路）： 圖中存在一條鏈，過每邊一次且僅一次。 歐拉圈（回路）：圖中存在一簡單圈， 過每邊

8、一次且僅一次。 歐拉圖：具有歐拉圈的圖。,一筆劃問題,8.1 圖與網(wǎng)絡基本知識,定理：連通多重圖G是歐拉圖，當且僅當G中無奇點 。 推論： 連通多重圖G有歐拉鏈，當且僅當G恰有兩個奇點。,五、歐拉回路與中國郵遞員問題,例8-3：哈密爾頓（Hamilton）回路是英國數(shù)學家哈密爾頓1857年提出。給出一個正12面體圖形，共有20個頂點表示20個城市，要求從某個城市出發(fā)沿著棱線尋找一條經(jīng)過每個城市一次而且僅一次，最后回到原處的周游世界線路（并不要求經(jīng)過每條邊）。,8.1 圖與網(wǎng)絡基本知識,8.1 圖與網(wǎng)絡基本知識,中國郵遞員問題,五、歐拉回路與中國郵遞員問題,一個郵遞員，負責某一地區(qū)的信件投遞。他

9、每天要從郵局出發(fā)，走遍該地區(qū)所有的街道再返回郵局，問應如何安排送信的路線可以使所走的總路程最短？,8.1 圖與網(wǎng)絡基本知識,中國郵遞員問題 奇偶點作業(yè)法：若圖中無奇點，問題已解決；,五、歐拉回路與中國郵遞員問題,否則： 1）第一可行方案的確定： 奇點配對，找奇點間的一條鏈。,3）最優(yōu)性判定：滿足a)和b)兩條。,8.1 圖與網(wǎng)絡基本知識,中國郵遞員問題,2）調(diào)整可行方案，使重復邊總長度下降。,a)最優(yōu)方案中， 每一邊上最多有一條重復邊。,b)最優(yōu)方案中，每個圈上重復邊的總權不大于圈總權的一半。,8.2 最短路問題,三種算法求解三類最短路問題： （1）Dijkstra算法：求無負權網(wǎng)絡最短路問題

10、；,（2）逐步逼近算法：求帶負權網(wǎng)絡最短路問題；,（3）Floyd算法：求網(wǎng)絡上任意兩點間的最短路問題。,8.2 最短路問題,一、Dijkstra算法：求無負權網(wǎng)絡最短路問題。,采用標號法： P標號和T標號(Permanent and Tentative Label),P標號：已確定出最短路的節(jié)點(永久性標號)。,T標號：未確定出最短路的節(jié)點，表示其距離的上限 （試探性標號）。,算法的每一步都把某一點的T標號改為P標號直至改完為止。,v4,8.2 最短路問題,一、 Dijkstra算法,8.2 最短路問題,一、 Dijkstra算法,解：（1）P(V1)=0 T(Vi)=+ (i=2,3,8)

11、,（2） 考察V1V2和V1V3兩邊：,T(V2)=minT(V2),P(V1)+l12=min+,0+4 =4,T(V3)=minT(V3),P(V1)+l13=min+,0+6 =6,比較所有T標號，T(V2)最小，有P(V2)=4。并記錄路徑(V1,V2)。,（3） 考察V2V4和V2V5兩邊：,T(V4)=minT(V4),P(V2)+l24=min+,4+5 =9,T(V5)=minT(V5),P(V2)+l25=min+,4+4 =8,比較所有T標號，T(V3)最小，有P(V3)=6。并記錄路徑(V1,V3)。,8.2 最短路問題,一、 Dijkstra算法,（4） 考察V3V4和

12、V3V5兩邊：,T(V4)=minT(V4),P(V3)+l34=min9,6+4 =9,T(V5)=minT(V5),P(V3)+l35=min8,6+7 =8,比較所有T標號，T(V5)最小，有P(V5)=8。并記錄路徑(V2,V5)。,（3） 考察V5V6和V5V7兩邊：,T(V6)=minT(V6),P(V5)+l56=min+,8+5 =13,T(V7)=minT(V7),P(V5)+l57=min+,8+6 =14,比較所有T標號，T(V4)最小，有P(V4)=9。并記錄路徑(V2,V4)。,依此類推，一直計算到（8） （8）考察V8點，只有一個T標號，T(V8)=15，令P(V8

13、)=15)，記錄路徑（V7，V8），計算結(jié)束。,反推得最V1至V8的最短路為V1V2 V5 V7 V8,路長15。,8.2 最短路問題,一、Dijkstra算法：求無負權網(wǎng)絡最短路問題。,計算步驟：,（1）給Vs以P標號，P（Vs）=0，其余各點給T標號，T（Vi）=+；,（2）若Vi點為剛得到P標號的點，考慮點Vj: (Vi,Vj)屬于E，且Vj為T標號。則修改T(Vj) T(Vj)=minT(Vj),P(Vi)+lij；,（3）比較所有T標號的點，把最小者改為P標號，即：P（Vi）=minT(Vi) 當存在兩個以上最小者時，可同時改為P標號。,二、逐次逼近法 基本思想：令P1j表示從v1到

14、vj的最短路長，P1i為v1到vi的最短路長，則必有下列方程： P1j=min(P1i+lij),8.2 最短路問題,i,8.2 最短路問題,例：求圖示中V1點到各點的最短路。,8.2 最短路問題,解：初始條件為： P11(1)=0， P12(1)=2， P13(1)=5， P14(1)=-3， P15(1)=P16(1)= P17(1)= P18(1)= ,第一輪迭代： P11(2)=minP11(1) +l11 ，P12(1) +l21 ， P13(1) +l31 ， P14(1) +l41 ， P15(1) +l51 ，P16(1) +l61 ，P17(1) +l71， P18(1) +

15、l81 =0,求解：見Excel表格求解。,P12(2)=minP11(1) +l12 ，P12(1) +l22 ， P13(1) +l32 ， P14(1) +l42 ， P15(1) +l52 ，P16(1) +l62 ，P17(1) +l72， P18(1) +l82 =2,依此類推。,8.2 最短路問題,10,10,10,15,M,M,0,-1,M,3,M,M,M,M,V8,9,9,14,M,M,M,M,0,2,M,7,M,M,M,V7,6,6,6,6,11,M,4,M,0,-3,M,M,M,M,V6,3,3,3,6,6,M,M,M,M,0,M,M,M,M,V5,-3,-3,-3,-3

16、,-3,-3,M,M,M,M,0,4,M,M,V4,0,0,0,0,0,5,M,M,6,M,M,0,M,M,V3,2,2,2,2,2,2,M,M,M,4,M,-2,0,M,V2,0,0,0,0,0,0,M,M,M,M,-3,5,2,0,V1,V8,V7,V6,V5,V4,V3,V2,V1,P(6)1j,P(5)1j,P(4)1j,P(3)1j,P(2)1j,P(1)1j,lij,j i,8.2 最短路問題,三、Floyd算法,算法功能：求網(wǎng)絡上任意兩點間的最短路。,算法步驟：,（1）令網(wǎng)絡的權矩陣為D=(dij)nn，lij為Vi到Vj的距離。,其中：,（2）輸入權矩陣為D(0)=D。,（3）

17、計算D(k) =(dij(k)nn (k=1,2,3,n)。,其中：,三、Floyd算法,8.2 最短路問題,例13： P267。 求解：見手工和Excel。,8.3 最大流問題,一、基本概念和基本定理 1。網(wǎng)絡與流 定義： 對有向圖G=(V，E)： vs 發(fā)點，vt 收點，其余 - 中間點,c(vi,vj) - 弧(vi，vj)的容量，簡寫為cij,G=(V，A，C) 容量網(wǎng)絡,fij - 弧(vi，vj)上的流量,2?？尚辛髋c最大流 可行流滿足：,8.3 最大流問題,3。增廣鏈: 幾個概念: 對可行流,8.3 最大流問題,8.3 最大流問題,增廣鏈： 設f是一可行流，是從始點到終點的一條鏈

18、，若滿足下列條件，稱其為一條增廣鏈。,4。割集和割量（截集和截量）、最小割,割集(S，T)的容量之和，稱為（S，T）的割集容量（割量），其中最小者為G的最小割集容量（最小割）。,8.3 最大流問題,定義：G=(V,A,C)中，Vs,Vt為發(fā)、收點，若有弧集E ，把圖G分為兩個子圖G1，G2，其頂點集分別記為S 和T， Vs,Vt分屬S，T中，有：,G（V，E-E）不連通；,E為E的真子集，而G（V，E-E）仍連通, 則稱E為G的割集，記E=（S，T）,5。最大流-最小割定理,8.3 最大流問題,任一圖G中，從Vs到Vt的最大流的流量等于分離Vs、Vt的最小割的容量。,8.3 最大流問題,6。求最大流的標號算法,分兩步： 第1步：標號過程，通過標號來尋找可增廣鏈；,第2步：調(diào)整過程，沿可增廣鏈調(diào)整f以增加流量。,8.3 最大流問題,6。求最大流的標號算法,（1）標號過程：,發(fā)點標號：（，+）,選擇一個已標號頂點Vi，對于Vi所有未標號的鄰接點Vj進行標號，處理規(guī)則如下：,(a) (Vj,Vi) E，且fji0，則令j=min(fji, i)，并給Vj標號(-Vi, j)。,(b) (Vi,Vj) E，且fij0，則令j=min(cij-fij, i)，并給Vj標號(+Vi, j)。,重復上述