第八章---圖與網(wǎng)絡(luò)分析

1、第八章圖與網(wǎng)絡(luò)分析,1,本章內(nèi)容,圖的基本概念 最短路問題 最小樹問題 最大流問題 推銷員及中國郵路問題,2,引言,1736年瑞士科學(xué)家歐拉發(fā)表了關(guān)于圖論方面的第一篇科學(xué)論文，解決了著名的哥尼斯堡七座橋問題。 德國的哥尼斯堡城有一條普雷格爾河，河中有兩個(gè)島嶼，河的兩岸和島嶼之間有七座橋相互連接，如圖。,3,哥尼斯堡七座橋問題圖,4,哥尼斯堡七座橋問題,問題：一個(gè)漫步者如何能夠走過這七座橋，并且每座橋只能走過一次，最終回到原出發(fā)地。 1736年歐拉將這個(gè)問題抽象成由點(diǎn)和線構(gòu)成的一筆畫問題圖形：能否從某一點(diǎn)開始不重復(fù)地一筆畫出這個(gè)圖形，最終回到原點(diǎn)，歐拉證明了這是不可能的。 這是古典圖論中的著名問

2、題之一。,5,哥尼斯堡七橋一筆畫問題,6,A,C,D,B,引言,在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从呈挛镏g的關(guān)系，常常在紙上用點(diǎn)和線來畫出各式各樣的示意圖。 例8-1 我國北京、上海、重慶等14個(gè)城市之間的鐵路交通可以通過用點(diǎn)表示城市，用點(diǎn)與點(diǎn)之間的線表示城市之間的鐵路線，畫出關(guān)系示意圖。 諸如此類還有城市中的市政管道圖、民用航空線圖等。,7,14個(gè)城市之間的鐵路交通示意圖,8,太原,重慶,武漢,南京,徐州,連云港,上海,鄭州,石家莊,塘沽,青島,濟(jì)南,天津,北京,第一節(jié) 圖的基本概念,圖論中圖的基本要素是點(diǎn)和點(diǎn)之間的線。一般來說，通常用點(diǎn)表示研究對(duì)象、用點(diǎn)與點(diǎn)之間的線表示研究對(duì)象之間的特定關(guān)

3、系。 在一般情況下，圖中的相對(duì)位置如何，點(diǎn)與點(diǎn)之間線的長短曲直，對(duì)于反映研究對(duì)象之間的關(guān)系并不重要。 因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。,9,基本概念,圖 設(shè)V=v1,v2 ,vn, E=e1,e2,em,若對(duì)于任一ejE，均有vs,vtV與之對(duì)應(yīng)，則稱VE為圖，記為G =(V，E)。 頂點(diǎn)、邊、端點(diǎn)、關(guān)聯(lián)邊、鄰接點(diǎn) 在G中，稱vi為G的頂點(diǎn)，ej為的邊，并記為ej=(vs ,vt )=(vt ,vs )，稱vs 、vt 是ej 的端點(diǎn)， ej 是與vs 、vt 關(guān)聯(lián)的邊， vs 、vt 稱為鄰接的點(diǎn)。,10,圖的基本概念,下列無向圖G=（V，E），其中 V = v1,v2,v

4、3,v4 E = (v1,v2), (v2,v1), (v2,v3), (v3,v4), (v1,v4), (v2,v4), (v3,v3) = e1, e2, e3, e4, e5, e6, e7 ,v3,v2,v1,v4,v5,e1,e2,e3,e4,e5,e6,e7,11,圖的基本概念,環(huán)、多重邊、簡單圖 如果圖中某一邊的兩個(gè)端點(diǎn)相同，則稱為環(huán)，如圖中的e8。如果圖中兩邊(或多邊)具有相同的一對(duì)端點(diǎn)，則稱為多重邊(或平行邊)，如圖中的e2、e3。 無環(huán)和無多重邊的圖 稱為簡單圖。 注意：當(dāng)兩個(gè)圖的形狀看似 不同，但如果它們的頂點(diǎn)集、 邊集以及邊與點(diǎn)的關(guān)系一 一對(duì)應(yīng)，則可視為同一個(gè)圖。,v

5、3,v2,v1,v4,v5,e1,e2,e3,e4,e5,e6,e7,e8,12,圖的基本概念,次數(shù), 孤立點(diǎn), 奇點(diǎn), 偶點(diǎn), 懸掛點(diǎn), 懸掛邊 與頂點(diǎn)相關(guān)聯(lián)的邊數(shù)稱為的次數(shù)，記為d(v) 圖中, d(v1)=3 , d(v2)=5 , d(v3)=4 , d(v4)=3 , d(v5)=1 。次數(shù)為零的點(diǎn)稱為孤立點(diǎn)，如v6；次數(shù)為奇數(shù)的點(diǎn)稱為奇點(diǎn)； 次數(shù)為偶數(shù)的點(diǎn)稱為 偶點(diǎn)；次數(shù)為 1 的點(diǎn) 為懸掛點(diǎn)；與懸掛點(diǎn) 關(guān)聯(lián)的邊稱為懸掛邊。,v3,v2,v1,v4,v5,e1,e2,e3,e4,e5,e6,e7,v6,13,基本定理,定理 8-1 任一圖中頂點(diǎn)次數(shù)之和等于邊數(shù)的二倍，即： 定理8-

6、 2 任一圖中奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。,14,圖的基本概念,鏈、初等鏈、簡單鏈 在圖中, 從一頂點(diǎn)出發(fā), 經(jīng)過邊, 點(diǎn), 邊,點(diǎn), ，最后到達(dá)某一點(diǎn)，稱為中的一條鏈，用經(jīng)過這條鏈的頂點(diǎn)或邊表示。(v1, v2,v3,v4)是一條鏈，也可表為(e1, e5,e6) 。 若鏈中的頂點(diǎn)均不同， 則稱為初等鏈；若鏈中 所含的邊均不同，則稱 之為簡單鏈。簡單鏈也 稱為通路，簡稱路。,v3,v2,v1,v4,v5,e1,e2,e3,e4,e5,e6,e7,15,圖的基本概念,圈、初等圈、簡單圈 若鏈中兩端的頂點(diǎn)相同，則稱此鏈為一個(gè)圈。若圈中的點(diǎn)都是不同的，則稱之為初等圈；若圈中所含的邊均不相同，則稱之為簡單圈

7、。 連通圖、不連通圖、子圖 圖中若任意兩點(diǎn)之間至少存 在一條鏈，則稱該圖為 連通圖，否則為不連通 圖。若取某圖其全部或 部分頂點(diǎn)及全部或部分 邊，如果構(gòu)成圖，則稱 為某圖的子圖。,v3,v2,v1,v4,v5,e1,e2,e3,e4,e5,e6,e7,16,子圖,子圖： 設(shè) G1= V1 , E1 , G2= V2 ,E2 子圖定義：如果 V2 V1 , E2 E1 稱 G2 是 G1 的子圖； 真子圖：如果 V2 V1 , E2 E1 稱 G2 是 G1 的真子圖； 部分圖（支撐子圖）：如果 V2 = V1 , E2 E1 稱 G2 是 G1 的部分圖； 導(dǎo)出子圖：若V2 V1, E2=vi

8、,vj:vi,vjV2, 稱 G2 是 G1 中由V2 導(dǎo)出的導(dǎo)出子圖。,17,有向圖,許多實(shí)際問題用前述無向圖無法描述，例如交通圖中的單行道，一項(xiàng)工程各工序間的先后次序關(guān)系等，所以需要用有向圖描述。 定義：設(shè)V=v1,v2 ,vn, A=a1,a2,am, 若對(duì)于任一ajA, 均有有序?qū)?vs,vt)與之對(duì)應(yīng), 則稱V A為有向圖, 記作D =(V, A)。稱為 vs 頂點(diǎn)，aj 為弧，記為aj=(vs, vt)，在不至于混淆時(shí)也稱為邊。,18,圖的基本概念有向圖,有向圖D =（V，A） 其中V = v1,v2,v3,v4,v5, A = (v1 ,v2),(v1 ,v3),(v2 ,v3)

9、, (v2 ,v4), (v2 ,v5), (v3 ,v5), (v4 ,v5), (v5 ,v4) = a5 , a2 , a3 , a4 , a5 , a6 , a7 , a8 ,19,圖的基本概念有向圖,有向圖D中, 從一頂點(diǎn)出發(fā), 順著弧的方向,經(jīng)過弧, 點(diǎn), 弧, 點(diǎn), , 最后到達(dá)某一點(diǎn)，稱為D中的一條單向鏈或通路，簡稱路。用經(jīng)過這條單向鏈的頂點(diǎn)或弧表示。(v1, v2,v5,v4)是一條單向鏈，也可表為(a1, a5, a8) 。 在有向圖中，頂點(diǎn)的 次數(shù)分為入次和出次 （入度和出度）：,20,圖的基本概念賦權(quán)圖,如果對(duì)于給定圖G=(V, E) 的任意一邊e，有一實(shí)數(shù) W(e)與

10、之對(duì) 應(yīng)，則稱G為賦 權(quán)圖，稱 W(e) 為邊e的權(quán)。 圖中，權(quán) 賦權(quán)圖的應(yīng)用比較廣泛，例如交通圖中，權(quán)數(shù)可以是兩點(diǎn)之間的距離，也可以是兩地之間的單位運(yùn)費(fèi)、運(yùn)能等，工程網(wǎng)絡(luò)圖中，權(quán)數(shù)代表工序的時(shí)間。,21,圖的基本概念賦權(quán)圖,設(shè)在賦權(quán)圖中存在一條通路，則通路上所有邊的權(quán)數(shù)之和稱為這條通路的權(quán)。 對(duì)于一個(gè)有向圖也可以定義權(quán)數(shù)使之成為有向賦權(quán)圖。 一個(gè)連通圖連同定義在其邊集上的實(shí)函數(shù) 一起稱為一個(gè)網(wǎng)絡(luò)。 若一個(gè)網(wǎng)絡(luò)的每條邊均有方向，稱為有向網(wǎng)絡(luò)；每一條邊均無方向，稱為無向網(wǎng)絡(luò)；若有些邊有向，另一些邊無向，則稱為混合網(wǎng)絡(luò)。,22,圖的矩陣描述,為便于計(jì)算機(jī)直接處理圖論問題，需矩陣化圖形。 (1) 無

11、權(quán)圖的鄰接矩陣表示 在圖中兩頂點(diǎn)之間有邊相連的記為1，無邊相連的記為0，對(duì)角線位置數(shù)據(jù)記為0，這樣就得到無權(quán)圖的鄰接矩陣，該矩陣一定是對(duì)稱矩陣。,23,圖的矩陣描述,（2）賦權(quán)無向圖的鄰接矩陣表示 圖中，兩頂點(diǎn)之間有邊相連的，寫上它們的權(quán)數(shù)，無邊相連的記為 ，表示此兩點(diǎn)之間是不通。對(duì)角線上的數(shù)值仍然為0。賦權(quán)無向圖對(duì)應(yīng)的矩陣也是對(duì)稱的。,24,圖的矩陣描述,（3）賦權(quán)有向圖的鄰接矩陣表示 圖中矩陣左側(cè)第一列為各條弧的起點(diǎn)，在每一行中，以該點(diǎn)為起點(diǎn)，按弧的方向，依次填上到各點(diǎn)的權(quán)數(shù)，如果不存在到該點(diǎn)的弧，則權(quán)數(shù)為 ，如此得到的矩陣往往不是對(duì)稱矩陣。,25,第二節(jié) 最短路問題,最短路問題：在網(wǎng)絡(luò)中

12、，給定起點(diǎn)，要求找出其到另一點(diǎn)的權(quán)數(shù)最小的通路。 它是網(wǎng)絡(luò)分析中最重要的優(yōu)化問題之一，作為一個(gè)經(jīng)常被用到的基本工具，可以解決生產(chǎn)實(shí)際中的許多問題，比如城市中的管道鋪設(shè)，線路安排，工廠布局，設(shè)備更新，等等。也可以用于解決其他的最優(yōu)化問題。 本課件下面的討論針對(duì)有向賦權(quán)圖，對(duì)無向賦權(quán)圖，方法是相同的，請(qǐng)參考教材。,26,最短路問題例,如圖是單行線交通網(wǎng)，每個(gè)弧旁邊的數(shù)字表示這條單行線的長度?，F(xiàn)在要從 v1 出發(fā)，經(jīng)過這個(gè)交通網(wǎng)到達(dá) v8，如何尋求總路程最短的線路。,27,v1,1,最短路徑問題例,從v1到v8的路線是很多的。比如從v1出發(fā)，經(jīng)過v2、v5到達(dá) v8 或者從 v1出發(fā)，經(jīng)過v4，v6

13、v7到達(dá) v8 ,等等。但不同的路線，經(jīng)過的總長度是不同的。例如，按照第一個(gè)線路，總長度是6+1+6=13單位，按照第二個(gè)路線，總長度是1+10+2+4=17單位。,28,最短路問題,設(shè)賦權(quán)有向圖D=(V,A), 對(duì)每個(gè)弧a = (vi, vj)，相應(yīng)地有權(quán)wij。Vs、vt是D中的兩個(gè)頂點(diǎn)，p是D中從vs到vt的任意一條路，定義路的權(quán)是p中所有弧權(quán)的和，記作S(p)。 最短路問題就是求S(p0)=minS(p)。p0叫做從vs到vs的最短路。p0的權(quán)S(p0)叫做從vs到vt的距離，記作d（vs，vt）。 由于D是有向圖，很明顯d(vs,vt)與d(vt,vs)一般不相等(對(duì)無向圖是相等的，

14、無向圖的邊可以看做由兩條方向相反的弧構(gòu)成)。,29,一、 最短路的標(biāo)號(hào)算法,下面介紹在賦權(quán)有向圖中尋求最短路的方法Dijkstra (狄克斯拉方法)算法，是在1959年提出來的。目前公認(rèn)，在所有的權(quán) wij 0時(shí)，這個(gè)算法是尋求最短路問題最好的算法。 這個(gè)算法實(shí)際上給出了從一個(gè)始點(diǎn)vs到任意一個(gè)點(diǎn)vj的最短路。,30,Dijkstra算法的基本思想,從vs出發(fā)，逐步向外尋找最短路。在運(yùn)算過程中，與每個(gè)點(diǎn)對(duì)應(yīng)，記錄一個(gè)數(shù)，叫做一個(gè)點(diǎn)的標(biāo)號(hào),分為兩類： P 標(biāo)號(hào)：表示從vs到該點(diǎn)的最短路權(quán) T 標(biāo)號(hào)：表示從vs到該點(diǎn)最短路權(quán)的上界。 算法的每一步是去修改T 標(biāo)號(hào)，把某一個(gè)具有T 標(biāo)號(hào)的點(diǎn)改變?yōu)榫哂?/p>

15、P 標(biāo)號(hào)的點(diǎn)，使圖D 中具有P 標(biāo)號(hào)的頂點(diǎn)多一個(gè)。這樣，至多經(jīng)過P -1步，就可求出從vs到各點(diǎn)vj的最短路。,31,說明：在例中,S=1。因?yàn)閣ij0，d (v1,v1)=0。這時(shí)，v1是具有P標(biāo)號(hào)的點(diǎn)。 再看從v1出發(fā)的三條弧(v1,v2)，(v1,v3)和(v1,v4)。如果從v1出發(fā)沿(v1,v2)到達(dá)v2，這時(shí)的路程是d (v1,v1) + w12= 6單位； 如果從v1出發(fā)，沿(v1,v3)到達(dá)v3，則是d (v1,v1) + w13 = 3單位； 同理，如果從v1出發(fā)沿(v1,v4)到達(dá)v4，是d（v1,v1）+ w14 = 1單位。,32,說明（續(xù)）,因此，從v1出發(fā)到達(dá)v4的

16、最短路必是（v1,v4），d（v1,v4）=1。這是因?yàn)閺膙1到達(dá)v4的任一條路，假如不是（v1,v4），則必先沿（v1,v2）到達(dá)v2，或者沿（v1,v3）到達(dá)v3，而這時(shí)的路程已是6或者3單位。由于wij 0，因此不論他如何再從v2或者v3到達(dá)v4，所經(jīng)過的總路程都不會(huì)比1少，于是就有d（v1,v4）=1。于是V4變成具有P標(biāo)號(hào)的點(diǎn)。,33,例說明：,從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(v1),1,34,再看從v1和v4指向其余點(diǎn)的?。簭膙1出

17、發(fā), 分別沿(v1,v2), (v1,v3 )到達(dá)v2, v3, 經(jīng)過的路程是6或者3單位；從v4出發(fā)沿(v4,v6)到達(dá)v6，經(jīng)過的路程是d(v1,v4)+w46=1+10=11單位。而 mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46=d（v1,v1）+w13=3單位。根據(jù)同樣的理由，可以斷定，從v1到達(dá)v3的最短路是（v1,v3），d（v1,v3）=3。這樣，又使點(diǎn)v3變?yōu)榫哂蠵 標(biāo)號(hào)的點(diǎn)，不斷重復(fù)以上過程，就可以求出從vs到達(dá)任一點(diǎn)vj的最短路。,35,例說明（續(xù)）：,再看從v1和v4指向其余點(diǎn)的弧, mind(v1,v1)+w12,d(v1,v1)+

18、w13,d(v1,v4)+w46=d（v1,v1）+w13=3 。,P(v1),P(V3),1,36,Dijkstra算法的實(shí)現(xiàn),Dijkstra算法中，以P、T 分別表示某一個(gè)點(diǎn)的P 標(biāo)號(hào)，T 標(biāo)號(hào)。Si表示在第i步時(shí)，具有P 標(biāo)號(hào)點(diǎn)的集合，為了在算出從vs到各點(diǎn)的距離的同時(shí)，也找出從vs到各點(diǎn)的最短路，于是，給每一個(gè)點(diǎn)v一個(gè)值。 當(dāng)算法結(jié)束時(shí)，表示含義： (v)= m 在從vs到v的最短路上，v的前一個(gè)點(diǎn)是vm (v)=M 在圖D中不含有從vs 到達(dá)v 的路 (v)=0 表示v = vs。,37,Dijkstra算法步驟,開始（i=0） 令S0=vs，P（vs）=0，(vs)=0，對(duì)每一個(gè)

19、v vs，令T（v）=+，(v)=M ，令k=s； （1）如果Si=V，則算法結(jié)束，對(duì)每一個(gè)vSi，d（vs,v）=P（v）。否則轉(zhuǎn)入（2）。,38,（2）考察每一個(gè)使(vk,vj)A，且 vjSi 的點(diǎn) vj ，如果 T(vj) P(vk) + wkj ，則 把 T(vj) 改變?yōu)?P(vk) + wkj，把(vj)改變?yōu)閗，否則轉(zhuǎn)入（3）。,39,（3）令T(vji)=minT(vj)vjSi，如果T(vji)+，則把vji的T 標(biāo)號(hào)改變?yōu)镻 標(biāo)號(hào)P(vji)=T(vji)，令Si+1=Sivji，k=ji，把i換成i+1，轉(zhuǎn)入（1）；否則結(jié)束。 這時(shí)，對(duì)vSi，d(vs,v) = P(v

20、)； 對(duì)vSi，d(vs,v) =T(v)。,40,Dijkstra算法求解例,vs為起點(diǎn); 開始, s =1, i=0; S0=v1, P(v1)=0, (v1)=0, T(vi)=+,(vi)=M, i=2,3,9, k=1。 (2) (v1,v2)A，v2S0，P(v1)+w12T(v2)，故將T(v2)改變?yōu)镻(v1)+w12=6，(v2)改變?yōu)?。同理，將T(v3)改變?yōu)镻(v1)+w13=3，(v3)改變?yōu)?，將T(v4)改變?yōu)镻(v1)+w14=1，(v4)改變?yōu)?。,41,Dijkstra算法求解例,（3）在所有的T標(biāo)號(hào)中，T(v4)=1最小，于令P(v4)=1，S1=S0v4

21、=v1,v4, k=4。 i=1： （2）將 T(v6) 改變?yōu)镻(v4) + w46 = 11，(v6) 改變?yōu)?。 （3）在所有的T標(biāo)號(hào)中，T(v3)=3最小，于是令P(v3)=3，S2=v1,v4,v3，k=3。,42,Dijkstra算法求解例,i=2： （2）(v3,v2)A，v2S2, T(v2) w32 + P(v3) ，將T(v2)改變?yōu)镻(v3) + w32= 5 ,(v2) 改變?yōu)?。 （3）在所有 T 標(biāo)號(hào)中, T(v2) = 5 最小, 于是令 P (v2) = 5, S3=v1,v4,v3，k = 2。,43,Dijkstra算法求解例,i = 3 ： （2）將T(v

22、5)改變?yōu)?P(v2)+w25= 6，(v5) 改變?yōu)?2。 （3）在所有T標(biāo)號(hào)中, T(v5) = 6 最小, 于是令P(v5) = 6, S4= v1,v4,v3，k=5。,44,Dijkstra算法求解例,i = 4 : （2）將T(v6)、T(v7)、T(v8)分別改變?yōu)?0, 9，12，將(v0)、(v7)、(v8)改變?yōu)?。 （3）在所有T標(biāo)號(hào)中, T(v7) = 9最小, 令 P(v7) = 9, S5 = v1,v4,v3,v2,v5,v7 ， v = 7。,45,Dijkstra算法求解例,i = 5： （2）（v7,v8）A，v8S5，但是 T(v8) w78+P(v7)，

23、故T(v8)不變。 （3）在所有的T標(biāo)號(hào)中，T(v6)=10最小, 于是, 令P(v6)=10, S6=v1,v4,v3,v2,v5,v7 , v6， k=6。,46,Dijkstra算法求解例,i=6： （2）從v6出發(fā)沒有弧指向不屬于S6的點(diǎn)，因此轉(zhuǎn)入（3）。 （3）在所有T標(biāo)號(hào)中，T(v8)=12最小，令 P (v8) = 12 ， S7 = v1,v4,v3,v2,v5,v7 ,v6 ,v8，k = 8 。,47,Dijkstra算法求解例,i=7： 僅有 T 標(biāo)號(hào)的點(diǎn)為 v9 ， T（v9）= +，算法結(jié)束。 此時(shí)，把P標(biāo)號(hào)和值標(biāo)在圖中，如圖所示。,48,例題求解圖示（1）,T(v6

24、)= +,T(v7)= +,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=M,(v5)=M,T(v2)= 6,T(v5)= +,T(v8)= +,(v7)=M,(v2)=1,(v8)=M,T(v9)=+,(v9)=M,T(v3)= 3,(v3)=1,1,i = 0 S1=S0v4=v1,v4,v1,v3,49,例題求解圖示（2）,T(v6)=11,T(v7)=+,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=4,(v5)=M,T(v2)=6,T(v5)=+,T(v8)=+,(v7)=M,(v2)=1,(v8)=M,T(v9)=+,(v9)=M,P

25、(v3)=3,(v3)=1,1,i = 1 S2=S1v3=v1,v4,v3,v1,v3,50,例題求解圖示（3）,T(v6)=11,T(v7)=+,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=4,(v5)=M,P(v2)=5,T(v5)=+,T(v8)=+,(v7)=M,(v2)=3,(v8)=M,T(v9)=+,(v9)=M,P(v3)=3,(v3)=1,1,i = 2 S3=S2v2=v1,v4,v3,v2,v1,v3,51,例題求解圖示（4）,T(v6)=11,T(v7)=+,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=4,(v5)=

26、2,P(v2)=5,P(v5)=6,T(v8)=+,(v7)=M,(v2)=3,(v8)=M,T(v9)=+,(v9)=M,P(v3)=3,(v3)=1,1,i = 3 S4=S3v5=v1,v4,v3,v2,v5,v1,v3,52,例題求解圖示（5）,T(v6)=10,P(v7)=9,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=5,(v5)=2,P(v2)=5,P(v5)=6,T(v8)=12,(v7)=5,(v2)=3,(v8)=5,T(v9)=+,(v9)=M,P(v3)=3,(v3)=1,1,i = 4 S5=S4v7=v1,v4,v3,v2,v5,v7,v1

27、,v3,53,例題求解圖示（6）,P(v6)=10,P(v7)=9,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=5,(v5)=2,P(v2)=5,P(v5)=6,T(v8)=12,(v7)=5,(v2)=3,(v8)=5,T(v9)=+,(v9)=M,P(v3)=3,(v3)=1,1,i = 5 S6=S5v6=v1,v4,v3,v2,v5,v7,v6,v1,v3,54,例題求解圖示（7）,P(v6)=10,P(v7)=9,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=5,(v5)=2,P(v2)=5,P(v5)=6,P(v8)=12,(v7)

28、=5,(v2)=3,(v8)=5,T(v9)=+,(v9)=M,P(v3)=3,(v3)=1,1,i = 6 S7 =S6v8=v1,v4,v3,v2,v5,v7,v6,v8,v1,v3,55,例題求解圖示（8）,P(v6)=10,P(v7)=9,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=5,(v5)=2,P(v2)=5,P(v5)=6,P(v8)=12,(v7)=5,(v2)=3,(v8)=5,T(v9)=+,(v9)=M,P(v3)=3,(v3)=1,1,最短路：v1-(v4)v3-v2-v5-(v6,v7)v8,v1,v3,56,Dijkstra算法求解例,圖

29、中，從v1到v8的最短路：因?yàn)?v8)=5，故最短路經(jīng)過點(diǎn)v5；又因?yàn)?v5)=2，故最短路經(jīng)過點(diǎn)v2；依次類推，(v2)=3，(v3)=1于是，最短路經(jīng)過點(diǎn)v3、v1。這樣，從v1到v8的最短路是（v1，v3，v2，v5，v8）。同理，可以求出從v1到任一點(diǎn)vi的最短路，顯然不存在從v1到v9的最短路。,57,Dijkstra算法,對(duì)于一個(gè)賦權(quán)(無向)圖G=(V，E)，因?yàn)檫卾i,vj可以看做2條?。╲i,vj）和(vj,vi)，并且具有相同的權(quán)wij。這樣，在一個(gè)賦權(quán)（無向）圖中，如果有所有的權(quán)wij0，只要將Dijkstra算法中的 “(2)看做每一個(gè)使(vk,vj)A，且vjSj的點(diǎn)v

30、j”改變?yōu)椤?2)看做每一個(gè)使vk,vjE，且vjSj的點(diǎn)vj”而其他的條件不變，同樣可以求出從vs到各點(diǎn)的最短路（對(duì)于無向圖叫做最短鏈）。,58,最短路的矩陣算法,最短路的標(biāo)號(hào)算法可以通過將圖表達(dá)成矩陣形式，然后用矩陣計(jì)算出最短路，這就是矩陣算法。矩陣算法有利于計(jì)算機(jī)處理。 矩陣算法的步驟為： 將圖表示成矩陣形式； 確定起點(diǎn)行，將其標(biāo)號(hào)確定為0，將相應(yīng)的列在矩陣表中劃去；,59,最短路的矩陣算法,在已標(biāo)號(hào)行未劃去的元素中，找出最小元素 aij 圈起來，并把第 j 列劃去，同時(shí)給第 j行標(biāo)號(hào)aij ，同時(shí)把第 j 行中未劃去的各元素都加上 aij ，注意標(biāo)號(hào)的含義同標(biāo)號(hào)算法一樣； 若還存在某些

31、行未標(biāo)號(hào)，則返回上一步驟，如果各行均已獲得標(biāo)號(hào)（或終點(diǎn)行已經(jīng)獲得標(biāo)號(hào)）則終止計(jì)算，并利用反向追蹤，求得自起點(diǎn)到各點(diǎn)的最短路。（例題見教材）,60,最短路標(biāo)號(hào)算法應(yīng)用例,某公司在最近五年需要使用一種設(shè)備，購買和維修該設(shè)備的費(fèi)用列表如下，問采用怎樣的使用策略可使總費(fèi)用最低。 表1 五年內(nèi)各年初的購買價(jià)格 時(shí)間 1 2 3 4 5 價(jià)格 200 210 230 240 260 表2 使用期間的維護(hù)費(fèi) 使用時(shí)間 01 12 23 34 45 價(jià)格 30 130 190 270 390,61,最短路標(biāo)號(hào)算法應(yīng)用例-分析,構(gòu)造設(shè)備更新有向圖，其中包含6個(gè)頂點(diǎn)v1 v6 ，分別代表第1年年初到第5年年末共6

32、個(gè)不同時(shí)刻，從頂點(diǎn) 分別引出至終點(diǎn)的有向邊，邊的權(quán)重等于從起點(diǎn)時(shí)刻購買設(shè)備并用到終點(diǎn)時(shí)刻所需的購買費(fèi)用和維護(hù)費(fèi)用總和。,62,計(jì)算從略,補(bǔ)充：Dijkstra算法的局限,Dijkstra算法僅適合于所有的權(quán)wij0的情形。如果當(dāng)賦權(quán)有向圖中存在有負(fù)權(quán)弧時(shí)，則該算法失效。 例如下圖，根據(jù)Dijkstra算法，可以得出從v1到v2最短路權(quán)是2，但是這顯然不對(duì)，因?yàn)閺膙1到v2的最短路是（v1,v3,v2）,權(quán)是-1。,v1,v3,v2,2,2,-3,63,最短路問題-補(bǔ)充,Ford(福德)算法: 當(dāng)賦權(quán)有向圖存在負(fù)權(quán)弧時(shí)，求最短路的方法: 首先，設(shè)從任一點(diǎn) vi 到任一點(diǎn)vj 都有一條弧，如果在圖

33、 D 中，（vi,vj）不屬于A,則添加弧(vi,vj),并且令 wij = +.,64,補(bǔ)充：Ford算法,從 vs 到 vj 的最短路是從 vs 點(diǎn)出發(fā)，沿著這條路到某個(gè)點(diǎn)vi，再沿弧(vi,vj)到點(diǎn)vj。 顯然，從vs到vi的這條路必定是從vs到vi的最短路。否則從vs到vj的這條路將不是最短路。于是，從vs到vj的距離d(vs,vj)滿足以下條件 d(vs,vj)=min d (vs,vi) + wij , i i=1, , p, p = p(D),65,補(bǔ)充：Ford算法,這個(gè)關(guān)系式的解d(vs,v1)d(vs,vp).可利用如下的 遞推公式 求解 d(1)(vs,vj) = ws

34、j , j =1, , p d(t)(vs,vj) = min d(t-1)(vs,vi)+ wij, t=2,3 i 當(dāng)計(jì)算到第k步時(shí),對(duì)一切的j =1, , p, 有 d(k)(vs,vj) = d(k-1)(vs,vj ) 則d(k)(vs,vj), j = 1, , p,就是從vs到各點(diǎn)vj的最短路徑的權(quán)。,66,補(bǔ)充：Ford算法,設(shè)C是賦權(quán)函數(shù)有向圖D中的一個(gè)回路。如果回路C的權(quán) S(C) 是負(fù)數(shù)那么稱 C 是 D 中的一個(gè)負(fù)回路。 可以證明以下結(jié)論： (1)如果賦權(quán)有向圖 D 不含負(fù)回路，那么從vs到任一點(diǎn)的最短路至多包含 p 2 個(gè)中間點(diǎn)，并且必可取為初等路。,67,補(bǔ)充：Fo

35、rd算法,(2) 如果賦權(quán)有向圖 D 不含有負(fù)回路，那么上述遞推算法至多經(jīng) p-1 次迭代收斂，可求出從vs到各個(gè)點(diǎn)最短路的權(quán)。 (3) 如果上述算法經(jīng)過 p-1 次迭代，還存在在著某個(gè)j，使得 d(p)(vs,vj) d(p-1)(vs,vj) 那么D中含有負(fù)回路。這時(shí)，不存在從 vs 到 vj 的路（權(quán)無界）。,68,補(bǔ)充：Ford算法例,在如圖所示的賦權(quán)有向圖中求從v1到各點(diǎn)的最短路。,69,1,1,1,1,1,1,2,3,3,5,5,2,2,3,6,7,8,補(bǔ)充：Ford算法例,解: 利用上述遞推公式，將求解結(jié)果列出如下表所示。 可以看出，當(dāng)t =4 時(shí)，有 d(t)(vs,vj)=d

36、(t-1)(vs,vj) ( j =1, , 8 ) 因此，表中的最后一列，就是從v1到v1,v2 ,v8的最短路權(quán)。,70,wij,d(t)(vs,vj),71,補(bǔ)充：Ford算法例,為了求出從v1到各個(gè)點(diǎn)的最短路，一般采用反向追蹤的方法：如果已知d(vs,vj),那么尋求一個(gè)點(diǎn)vk,使得d(vs,vk)+wkj=d(vs,vj),然后記錄下(vk,vj).在看d(vs,vk),尋求一個(gè)點(diǎn)vi,使得d(vs,vi)+wik=d(vs,vk)依次類推，一直到達(dá)vs為止。這樣，從vs到vj的最短路是（vs ,vi ,vk ,vj）。,72,補(bǔ)充：Ford算法例,在例中，由上表知，d(v1,v8)

37、=6,由于d(v1,v6)+w68 = (-1) + 7 ，記錄下v6 ; 由于d (v1,v3) + w36= d (v1,v6), 記錄下v3; 由于d(v1,v1)+w13=d(v1,v3), 于是，從v1到v8的最短路是 (v1,v3,v6,v8),73,第三節(jié) 最小樹問題,一、 樹、最小樹的定義及性質(zhì) 在各種圖中，有一類圖是十分簡單且非常具有應(yīng)用價(jià)值的圖，這就是樹。 例 已知有6個(gè)城市，它們之間要架設(shè)電話線，要求任意兩個(gè)城市均可以互相通話，并且電話線的總長度最短。,74,樹、最小樹的定義及性質(zhì)例,如果用6個(gè)點(diǎn)v1，v6代表這六個(gè)城市，在任意兩個(gè)城市之間架設(shè)電話線，即在相應(yīng)的兩個(gè)點(diǎn)之間

38、連成一條邊。這樣，6個(gè)城市的一個(gè)電話網(wǎng)就作成一個(gè)圖。由于任意兩個(gè)城市之間均可以通話，這個(gè)圖必須是連通圖。并且，這個(gè)圖必須是無圈的。否則，從圈上任意去掉一條邊，剩下的圖仍然是六個(gè)城市的一個(gè)電話網(wǎng)。下圖是一個(gè)不含圈的連通圖，代表了一個(gè)電話線網(wǎng)。,75,樹、最小樹的定義及性質(zhì)例,代表電話線網(wǎng)的無圈連通圖,76,v6,v3,v4,v2,v5,v1,樹、最小樹的定義及性質(zhì),(1) 樹的定義 在無向圖中的鏈 中, 若v1=vn，則稱此鏈為一個(gè)圈, 若圈中的點(diǎn) 都是不同的，則稱之為初等圈。 定義 無圈的連通圖叫做樹。 (2) 樹的重要性質(zhì)： 設(shè)圖G=(V, E)是一個(gè)多于2個(gè)節(jié)點(diǎn)的樹，那么圖G中至少有兩個(gè)懸

39、掛點(diǎn)。 圖G=(V, E)是一個(gè)樹的充要條件是G不含圈，并且有且僅有n -1條邊，即邊數(shù)m=n-1。,77,樹的重要性質(zhì),從一個(gè)樹中任意去掉一條邊，那么剩下的圖不是連通圖。亦即，在點(diǎn)集合相同的圖中，樹是含邊數(shù)最少的連通圖。 在樹中任意不相鄰的兩個(gè)點(diǎn)之間加上一條邊，那么恰好得到一個(gè)圈。所以樹也是具有相同頂點(diǎn)的無圈圖中邊數(shù)最多的。,78,樹、最小樹的定義及性質(zhì),(3) 生成樹、最小生成樹 設(shè)圖K=(V,E)是圖G=(V,E)的生成子圖, 如果圖K=(V,E)是樹, 那么稱K是G的生成樹。 下面右圖是左圖的一個(gè)生成樹。,v6,v5,v2,v3,v4,v1,v6,v5,v2,v3,v4,v1,79,最

40、小生成樹,如果圖T = (V, E) 是圖G 的一個(gè)生成樹，那么稱 E 上所有邊的權(quán)之和為生成樹 T 的權(quán)，記為S( T )。 若圖G的生成樹T * 的權(quán)S(T * )，在G 的所有生成樹 T 中的權(quán)最小，即 S(T * ) = min S(T ) ，那么稱T*是G 的最小生成樹。,80,二、 最小生成樹的求解,常用的有破圈法和避圈法兩個(gè)方法： 破圈法 在網(wǎng)絡(luò)圖中尋找一個(gè)圈。若不存在圈，則已經(jīng)得到最小生成樹或網(wǎng)絡(luò)不存在最小生成樹；否則 去掉該圈中權(quán)數(shù)最大的邊； 反復(fù)重復(fù) 兩步，直到得到最小生成樹。,81,最小生成樹破圈法例,某 6 個(gè)城市之間的道路網(wǎng)如圖所示，要求沿著已知長度的道路聯(lián)結(jié) 6 個(gè)

41、城市的電話線網(wǎng)，使得電話線的總長度最短。,82,最小生成樹破圈法例,順序：綠，藍(lán)，紅，黑,v6,v5,v2,v3,v4,v1,6,2,7,5,3,5,4,4,v3,v2,v1,v4,v6,v5,5,1,3,1,4,2,最小生成樹,83,最小生成樹破圈法例,解：如圖，用破圈法求解最小生成樹。 1) 圈 v1,v2,v3,v1 ,刪圈中權(quán)最大邊(v1,v3)； 2) 圈 v3,v5,v2,v3 ，去掉邊(v2,v5)； 3) 圈 v3,v5,v4 ,v2,v3 ，去掉邊(v3,v5)； 4) 圈 v5,v6,v4 ,v5 ，這里有兩條權(quán)最大的邊(v5,v6)和(v4,v6)。任刪一條，如(v5,v

42、6)。 這時(shí)得到一個(gè)不含圈的圖，即是最小生成樹。,84,最小生成樹的求解,避圈法 從網(wǎng)絡(luò)圖中依次尋找權(quán)數(shù)較小的邊，尋找過程中，節(jié)點(diǎn)不重復(fù)，即不構(gòu)成圈。注意在找較小權(quán)數(shù)邊時(shí)不考慮已選過的邊和可能造成圈的邊。如此反復(fù)進(jìn)行，直到得到最短樹或證明網(wǎng)絡(luò)不存在最短樹。,85,最小生成樹避圈法例,用“避圈法”求解上例。 解：考慮該賦權(quán)圖，任取一點(diǎn)，如 從v1 取權(quán)較小的邊（v1 ,v2 ）； 從v2 取權(quán)較小的邊（v2 ,v3 ）； 從v3 取權(quán)較小的邊（v3 ,v4 ）； 同理依次?。╲4 ,v5），（v4 ,v6 ）。 這時(shí)得到了如圖所示的最小生成樹。,86,v6,v5,v2,v3,v4,v1,6,2,

43、7,5,3,5,4,4,v3,v2,v1,v4,v6,v5,5,1,3,1,4,2,最小生成樹,最小生成樹破圈法例,順序：綠，黑，紅，藍(lán)，棕,87,第四節(jié) 最大流問題,在許多實(shí)際網(wǎng)絡(luò)系統(tǒng)中都存在著流量和最大流問題。例如鐵路運(yùn)輸系統(tǒng)中的車輛流，城市給排水系統(tǒng)的水流問題等。網(wǎng)絡(luò)系統(tǒng)流最大流問題是圖與網(wǎng)絡(luò)流理論中十分重要的最優(yōu)化問題，它對(duì)于解決生產(chǎn)實(shí)際問題起著十分重要的作用。,88,一、 最大流的基本知識(shí),容量網(wǎng)絡(luò)圖 N=(V,A,C,x,y) 弧旁邊的權(quán)c(vi,vj)就是對(duì)應(yīng)弧的容量，x為源 (發(fā)點(diǎn)vs), y為匯(收點(diǎn)vt) 。要求一個(gè)運(yùn)輸方案，使得從x到y(tǒng)的貨運(yùn)量最大。這是尋求網(wǎng)絡(luò)系統(tǒng)的最大

44、流問題。,vt,v3,v2,v1,v4,vs,17,3,5,10,8,6,11,4,5,3,Cij,89,最大流問題的基本概念,定義: 設(shè)賦權(quán)有向圖D=(V,A), 在V中指定一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt , 其他的點(diǎn)叫做中間點(diǎn)。對(duì)于D中的每一個(gè)弧 (vi ,vj)A, 都有一個(gè)權(quán) cij ，叫做弧的容量。我們把這樣的圖 D 叫做一個(gè)網(wǎng)絡(luò)系統(tǒng)，簡稱網(wǎng)絡(luò)，記做 D =（V，A，C，vs，vt）。,90,網(wǎng)絡(luò)D上的流,定義在弧集合A上的一個(gè)函數(shù) f = f(vi,vj) = fij ; f(vi,vj)=fij 叫做弧 (vi,vj) 上的流量。,91,網(wǎng)絡(luò)上的流,圖：網(wǎng)絡(luò)上的一個(gè)流（運(yùn)輸方案），弧

45、上的流量 fij 就是運(yùn)輸量,例如fs1=5, fs2=3, f13=2等.,v3,v2,v1,v4,vs,17(2),3(3),5(2),10(5),8(3),6(3),11(6),4(1),5(1),3(2),Cij (fij),vt,92,網(wǎng)絡(luò)系統(tǒng)上流的特點(diǎn),(1)發(fā)點(diǎn)的總流出量和收點(diǎn)的總流入量必相等。 (2)每一個(gè)中間點(diǎn)的流入量與流出量的代數(shù)和等于零。 (3)每一個(gè)弧上的流量不能超過它的最大通過能力（即容量）。,93,網(wǎng)絡(luò)系統(tǒng)的可行流,定義 網(wǎng)絡(luò)上的一個(gè)流 f 叫做可行流，如果 f 滿足以下條件： (1) 容量條件： 對(duì)于每一個(gè)弧(vi,vj)A, 有 0 fij cij ； (2)

46、平衡條件： 對(duì)于發(fā)點(diǎn)vs，有fsj -fjs= v( f ) 對(duì)于收點(diǎn)vt，有ftj -fjt =-v( f ) 對(duì)于中間點(diǎn)，有fij -fji=0 其中發(fā)點(diǎn)的總流量(或收點(diǎn)的總流量) v(f )叫做這個(gè)可行流的流量。,94,網(wǎng)絡(luò)系統(tǒng)的可行流,任意一個(gè)網(wǎng)絡(luò)上的可行流總是存在的。例如零流 v ( f ) = 0, 就是滿足以上條件的可行流。 網(wǎng)絡(luò)系統(tǒng)中最大流問題就是在給定的網(wǎng)絡(luò)上尋求一個(gè)可行流 f, 其流量 v ( f ) 達(dá)到最大值。,95,二、 最大流的標(biāo)號(hào)算法,飽和弧與零流弧 設(shè)流 f = fij 是網(wǎng)絡(luò)D上的一個(gè)可行流。我們把 D 中 fij = cij 的弧叫做飽和弧， fij 0 的

47、弧為非零流弧， fij = 0 的弧叫做零流弧。,96,最大流的標(biāo)號(hào)算法,前向弧和反向弧 設(shè)是網(wǎng)絡(luò)D中連接發(fā)點(diǎn)s和收點(diǎn)vt的一條鏈。定義鏈的方向是從vs到vt，于是鏈上的弧被分為兩類： 1)弧的方向與鏈的方向相同，叫做前向弧。前向弧的集合記做+。 2) 弧的方向與鏈的方向相反，叫做反向弧。反向弧的集合記做-。,97,例,在下圖中，(v4,v3)是飽和弧，其他弧均是非飽和弧、非零流弧。 如圖，在鏈（vs,v1,v2,v3,v4,vt)中，反向弧-=(v4,v3)； 前向弧+=(vs,v1),(v1,v2),(v2,v3),(v4,vt)。,v3,v2,v1,v4,vs,17(2),3(3),5(

48、2),10(5),8(3),6(3),11(6),4(1),5(1),3(2),fij,vt,98,最大流的標(biāo)號(hào)算法,定義：如果鏈 滿足以下條件： 在弧(vi,vj)+上，有0 fij cij ,即+中的每一條弧是非飽和??； 在弧(vi,vj)- 上，有0 fij cij ,即- 中的每一條弧是非零流弧。 稱鏈為關(guān)于可行流 f 的一條增廣鏈。,99,例,在圖中，鏈（vs,v1,v2,v3,v4,vt)是一條增廣鏈。,v3,v2,v1,v4,vs,17(2),3(3),5(2),10(5),8(3),6(3),11(6),4(1),5(1),3(2),fij,vt,100,增廣鏈性質(zhì),若網(wǎng)絡(luò)存在

49、關(guān)于可行流 f 的增廣鏈 令 按增廣鏈的定義，這里 0 。取,101,最大流的標(biāo)號(hào)算法,由上可知，存在增廣鏈就意味著可以找到流量更大的可行流。于是有下列定理： 定理 網(wǎng)絡(luò)中的一個(gè)可行流 f * 是最大流的充分必要條件是不存在關(guān)于 f * 的增廣鏈。,102,最大流的標(biāo)號(hào)算法,定理提供了求網(wǎng)絡(luò)系統(tǒng)最大流的方法 如果網(wǎng)絡(luò) D 中有一個(gè)可行流 f ，只要判斷網(wǎng)絡(luò)是否存在關(guān)于可行流 f 的增廣鏈： 若沒有增廣鏈，那么 f 一定是最大流。 若有增廣鏈，那么可以按照前面說明，不斷改進(jìn)和增大可行流 f 的流量，最終可以得到網(wǎng)絡(luò)中的最大流。,103,最大流的標(biāo)號(hào)算法,用給頂點(diǎn)標(biāo)號(hào)的方法來定義V1*。在標(biāo)號(hào)過程

50、中，有標(biāo)號(hào)的頂點(diǎn)是V1*中的點(diǎn)，沒有標(biāo)號(hào)的點(diǎn)不是V1*中的點(diǎn)。如果 vt 有了標(biāo)號(hào)，則表示存在一條關(guān)于 f 的增廣鏈。如果標(biāo)號(hào)過程無法進(jìn)行下去，并且 vt 未被標(biāo)號(hào)，則表示不存在關(guān)于 f 增廣鏈。這樣，就得到了網(wǎng)絡(luò)中的一個(gè)最大流。,104,最大流的標(biāo)號(hào)算法,(1) 標(biāo)號(hào)過程 在標(biāo)號(hào)過程中，網(wǎng)絡(luò)中的點(diǎn)或者是標(biāo)號(hào)點(diǎn)（分為已檢查和未檢查兩種），或者是未標(biāo)號(hào)點(diǎn)。每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分：第一個(gè)標(biāo)號(hào)表示這個(gè)標(biāo)號(hào)是從那一點(diǎn)得到的。以便找出增廣鏈。第二個(gè)標(biāo)號(hào)是為了用來確定增廣鏈上的調(diào)整量。,105,最大流的標(biāo)號(hào)算法,標(biāo)號(hào)過程開始，先給vs標(biāo)號(hào)(0, +)。這時(shí)，vs是標(biāo)號(hào)未檢查的點(diǎn)，其他都是未標(biāo)號(hào)點(diǎn)。一般

51、地，取一個(gè)標(biāo)號(hào)未檢查點(diǎn)vi，對(duì)一切未標(biāo)號(hào)點(diǎn)vj： a) 如果在弧 (vi,vj)上，fij cij , 那么給 vj標(biāo)號(hào)(vi, l(vj) ), 其中l(wèi)(vj) = minl(vi), cij-fij。這時(shí)，vj 成為標(biāo)號(hào)未檢查的點(diǎn)。,106,最大流的標(biāo)號(hào)算法,b）如果在弧(vj ,vi)上，fij 0, 那么給vj標(biāo)號(hào)(-vi , l(vj) )，其中l(wèi)(vj) = min l(vi), fij。這時(shí)，vj 成為標(biāo)號(hào)未檢查點(diǎn)。 于是vi成為標(biāo)號(hào)已檢查的點(diǎn)。重復(fù)以上步驟，如果所有的標(biāo)號(hào)都已經(jīng)檢查過，而標(biāo)號(hào)過程無法進(jìn)行下去，則標(biāo)號(hào)法結(jié)束。這時(shí)的可行流就是最大流。但是，如果 vt 被標(biāo)上號(hào)，表示

52、得到一條增廣鏈，轉(zhuǎn)入下一步調(diào)整過程。,107,最大流的標(biāo)號(hào)算法,(2) 調(diào)整過程 首先按照vt和其他的點(diǎn)的第一個(gè)標(biāo)號(hào)，反向追蹤，找出增廣鏈。例如，令vt的第一個(gè)標(biāo)號(hào)是vk，則弧（vk,vt）在上。再看vk的第一個(gè)標(biāo)號(hào)，若是vi，則弧(vi,vk)都在上。依次類推，直到vs為止。這時(shí)，所找出的弧就成為網(wǎng)絡(luò)D的一條增廣鏈 。取調(diào)整量 = l(vt), 即vt的第二個(gè)標(biāo)號(hào)。,108,最大流的標(biāo)號(hào)算法,fij+，當(dāng)(vi ,vj)+ 令f ij= fij -，當(dāng)(vi ,vj) - 其他不變 再去掉所有的標(biāo)號(hào)，對(duì)新的可行流 f = f ij ,重新進(jìn)行標(biāo)號(hào)過程，直到找到網(wǎng)絡(luò)D的最大流為止。,109,最

53、大流的標(biāo)號(hào)算法例,尋找下列網(wǎng)絡(luò)D=(V, A, C, vs , vt ) 的最大流。,110,v4,v1,v2,v3,vs,（2,1）,（3,0）,（4,3）,（3,3）,（5,1）,（2,2）,（5,3）,（1,1）,（1,1）,(Cij,fij),vt,最大流的標(biāo)號(hào)算法例,求網(wǎng)絡(luò)最大流, 弧旁的權(quán)數(shù)表示(cij , fij)。用標(biāo)號(hào)法解: (1) 標(biāo)號(hào)過程。 a) 首先給vs標(biāo)號(hào)（0，+）。 b) 看vs: 在弧(vs ,v2)上, fs2=cs3=3, 不具備標(biāo)號(hào)條件。在弧(vs ,v1)上, fs1=1cs1=5, 故給v1標(biāo)號(hào)(vs, l(v1),其中 l(v1)=minl(vs),

54、(cs1-fs1)=min+,5-1=4,111,最大流的標(biāo)號(hào)算法例,看v1:弧(v1,v3)上, f13=c13=2,不具備標(biāo)號(hào)條件?；?v2,v1)上, f21=10, 故給v2標(biāo)號(hào)(-v1, l(v2), 其中 l(v2)=minl(v1), f21=min4,1=1 看v2:在?。╲2,v4）上，f24=3 0, 故給 v3 標(biāo)號(hào) （-v2，l(v3), 其中 l (v3)=minl(v2),f32=min1,1=1,112,最大流的標(biāo)號(hào)算法例,在v3 、v4中任意選一個(gè)，比如v3,在弧( v3 ,vt )上，f3t = 1 c3t = 2, 故給 vt 標(biāo)號(hào)(v3, l(vt),其中

55、 l(vt)=minl(v3),(c3t-f3t)=min1,1=1 因?yàn)関t被標(biāo)上號(hào)，根據(jù)標(biāo)號(hào)法，轉(zhuǎn)入調(diào)整過程。,113,最大流的標(biāo)號(hào)算法例,標(biāo)號(hào)過程得到增廣鏈,114,v4,v1,v2,v3,vs,（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),(v3,1),最大流的標(biāo)號(hào)算法例,(2) 調(diào)整過程 從vt開始，按照標(biāo)號(hào)點(diǎn)的第一個(gè)標(biāo)號(hào)，用反向追蹤的方法，找出一條從vs到vt的增廣鏈，如圖中雙箭線所示。 +=(vs,v1),(v3,

56、vt),-=(v2,v1),(v3,v2) 取=1，在上調(diào)整f，得到 fs1+=1+1=2 在+上 f3t+=1+1=2 在+上 f * = f21-=1-1=0 在-上 f32-=1-1=0 在-上 其他的不變,115,最大流的標(biāo)號(hào)算法例,調(diào)整后的可行流f*，如圖所示，再對(duì)這個(gè)可行流從新進(jìn)行標(biāo)號(hào)過程，尋找增廣鏈。 首先給vs標(biāo)號(hào)（0，+），看vs , 給v1標(biāo)號(hào)（vs , 3）?？磛1,在?。╲1,v3）上，f13=c13,弧（v2,v1）上，f21=0,均不符合條件。因此標(biāo)號(hào)過程無法進(jìn)行下去，不存在從vS到vt的增廣鏈，算法結(jié)束。,116,最大流的標(biāo)號(hào)算法例,這時(shí)，網(wǎng)絡(luò)中的可行流f*即是最

57、大流，最大流的流量為 v ( f * ) = fs1 + fs2 = 5 注：在實(shí)際計(jì)算中，選擇不同的增廣鏈，可得到兩條路徑不同的最大流路徑，流量相同是5 。,117,最大流的標(biāo)號(hào)算法例,繼續(xù)調(diào)整標(biāo)號(hào)調(diào)整過程；得到最大流。,v4,v1,v2,v3,vs,（2,2）,（3,0）,（4,3）,（3,3）,（5,2）,（2,2）,（5,3）,（1,0）,vt,( 0,+),(vs,3),(Cij,fij),（1,0）,118,最大流的標(biāo)號(hào)算法例（另一路徑）,另一條增廣鏈,119,v4,v1,v2,v3,vs,（2,1）,（3,0）,（4,3）,（3,3）,（5,1）,（2,2）,（5,3）,（1,1

58、）,（1,1）,( Cij , fij ),vt,(V2,1),(0，+),(-v1,1),(vs,4),(-v2,1),(v4,1),最大流的標(biāo)號(hào)算法例（另一路徑）,調(diào)整后得到另一最大流路徑,v4,v1,v2,v3,vs,（2,1）,（3,0）,（4,4）,（3,3）,（5,2）,（2,2）,（5,4）,（1,0）,（1,1）,( Cij , fij ),vt,(0，+),(vs,3),120,第五節(jié) 推銷員及中國郵路問題,一、 推銷員問題 一個(gè)推銷商到n個(gè)城市開拓市場推銷產(chǎn)品，他從某個(gè)城市出發(fā)，遍歷其他所有城市，且每個(gè)城市只到一次，最后回到起點(diǎn)城市。這個(gè)推銷商如何安排他的商業(yè)營銷線路計(jì)劃可使總的路程距離最短，這就是推銷員問題，也被稱為貨郎擔(dān)問題。 對(duì)一個(gè)圖而言，若一個(gè)回路過每個(gè)點(diǎn)且僅過一次，則稱是圖的一個(gè)Hamilton回路。,121,推銷員問題,已證明：若頂點(diǎn)數(shù) n 3 的圖G(V,E)中，任