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

《第七章圖與網(wǎng)絡(luò)分析》由會員分享，可在線閱讀，更多相關(guān)《第七章圖與網(wǎng)絡(luò)分析（28頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 第七章 圖與網(wǎng)絡(luò)分析 圖與網(wǎng)絡(luò)分析（Graph Theory and Network Analysis），是近幾十年來運籌學(xué)領(lǐng)域中發(fā)展迅速、而且十分靈活的一個分支。由于它對實際問題的描述，具有直觀性，故廣泛應(yīng)用與物理學(xué)、化學(xué)、信息論、控制論、計算機科學(xué)、社會科學(xué)、以及現(xiàn)代經(jīng)濟管理科學(xué)等許多科學(xué)領(lǐng)域。 圖與網(wǎng)絡(luò)分析的內(nèi)容十分豐富。本章只介紹圖與網(wǎng)絡(luò)的基本概念以及圖論在路徑問題、網(wǎng)絡(luò)流問題等領(lǐng)域中應(yīng)用。重點講明方法的物理概念、基本概念及計算步驟。 1 圖與網(wǎng)絡(luò)的基本概念 定義1 圖是由表示具體事物的點（頂點）的集合V=｛v1,v2,…，vn｝和表示事物之間

2、關(guān)系邊的集合E=｛e1,e2,…，em｝所組成，且E中元素ei是由V中的無序元素對[vi,vj]表示，即ei=[vi,vj]，記為G=（V，E），并稱這類圖為無向圖。 例如，圖7-1中，有８條邊，６個頂點，即V=｛v1,v2,…,v6｝;E=｛e1,e2,…,e8｝其中 e1 = [v1 , v2] = [v2 , v1]; e7 = [v2 , v5] = [v5 , v2]; e2 = [v2 , v3] = [v3 , v2]; e6 =

3、 [v4, v5] = [v5 , v4]. 定義２　 （１）頂點數(shù)和邊數(shù)：圖G(Ｖ,Ｅ)中，Ｖ中元素的個數(shù)稱為圖Ｇ的頂點數(shù)，記作p(G)或簡記為p；Ｅ中元素的個數(shù)稱做圖Ｇ的邊數(shù)，記為q(G)，或簡記q。 （２）端點和關(guān)聯(lián)邊：若ei=[vi,vj]∈Ｅ，則稱點vi,vj是邊ei的端點，邊ei是點vi和vj的關(guān)聯(lián)邊。 （３）相鄰點和相鄰邊：同一條邊的兩個端點稱為相鄰點，簡稱鄰點；有公共端點的兩條邊稱為相鄰邊，簡稱鄰邊。 （４）多重邊與環(huán)：具有相同端點的邊稱為多重邊或平行邊；兩個端點落在一個頂點的邊稱為環(huán)。 （５）多重圖和簡單圖：含有多重邊的圖稱為多重圖；無環(huán)也無多重邊的圖稱為簡單

4、圖。 （６）次：以vi為端點的邊的條數(shù)稱為點vi的次，記作d(vi)。 （７）懸掛點和懸掛邊：次為１的點稱為懸掛點：與懸掛點相聯(lián)的邊稱為懸掛邊。 （８）孤立點：次為零的點稱為孤立點。 （９）奇點與偶點：次為奇數(shù)的點稱為奇點；次為偶數(shù)的點稱為偶點。 例如，圖7-1中,p(G)=8,q(G)=6;e3=[v4,v3]，v4與v3是e3的端點，e3是v4和v3的關(guān)聯(lián)邊；v2與v5是鄰點，e3與e2是鄰邊；e7與e8是多重邊，e4是一個環(huán)；圖９.５是一個多重圖；v1是懸掛點，e１是懸掛邊；v６是孤立點；v２是奇點，v３是偶點。 定理１　圖Ｇ＝（Ｖ，Ｅ）中，所有點的次之和是邊數(shù)的兩倍

5、。即 。 定理１是顯然的，因為在計算各點的次時，每條邊都計算兩次，于是圖Ｇ中全部頂點的次之和就是邊數(shù)的２倍。 定理２　任一圖Ｇ＝（Ｖ，Ｅ）種，奇點的個數(shù)為偶數(shù)。 證　設(shè)Ｖ１，Ｖ２分別是Ｇ中奇點和偶點的集合，由定理１可知 　　　　　　　　 （7.１） 因為 是偶數(shù)，而 也是偶數(shù)，故 也必是偶數(shù)，由于偶數(shù)個奇數(shù)才能導(dǎo)致偶數(shù)，所以有奇點的個數(shù)必須為偶數(shù)。 定義３ 　（１）鏈在一個圖Ｇ＝（Ｖ，Ｅ）中，一個由點與邊構(gòu)成的交錯序列（vi1,ei1, vi2,ei2,…，vik-1,eik-1,vik）如果滿足ei t= [eit, ei t+1] (t=1,2,…,k

6、-1), 則稱此序列為一條聯(lián)結(jié)vil, eik,的鏈，記為μ=（vi1,vi2,…，vik）,則稱點vi２,vi3,…, vik-1為鏈的中間點。 （２）閉鏈與開鏈：若鏈μ中vi1＝vik 即始點與終點重合，則稱此鏈為閉鏈（圈）。否則稱之為開鏈。 （３）簡單鏈與初等鏈：若鏈μ中，若含的邊數(shù)均不相同，則稱之為簡單鏈；若鏈μ中，頂點vi1,vi2,…，vik都不相同，則稱此鏈為初等鏈。除非特別交代，以后我們討論的均指初等鏈。 例如，圖7-1中，μ1= ( v2,e2, v3,e3, v4,e6, v5) 是一條鏈，由于鏈μ1里所含的邊和點均不相同，故是一條初等鏈；而μ2= ( v1,e

7、1, v2,e2, v3,e3, v4,e5,v2,e1,v1) 是一條閉鏈。 定義４ （１）回路：一條閉的鏈稱為回路。 （２）通路：一條開的初等鏈稱為通路。 （３）簡單鏈回路和初等回路；若回路中的邊都不相同，則稱為簡單回路；若回路中的邊和頂點都互不相同，則稱為初等回路或圈。 定義５　一個圖Ｇ的任意兩頂點之間，如果至少有一條通路將它們連接起來，則這個圖Ｇ就稱為連通圖，否則稱為不連通圖。 例如，圖7-1中，v1與v6沒有一條通路把它們連接起來，故此圖是不連通圖。本章以后討論的圖，除特別聲明外，都是指連通圖。 定義６　 （１）子圖：設(shè)Ｇ1＝｛Ｖ1，Ｅ1｝Ｇ2＝｛Ｖ2，

8、Ｅ2｝如果Ｖ1 V2，又Ｅ1 E2,則稱Ｇ1為G2的子圖。 （２）真子集：若V1 V2,E1 E2即G1中不包含G2中所有的頂點和邊，則稱G1是G2的真子圖。 （３）部分圖：若V1=V2,E1 E2,即Ｇ1中不包含G2中所有的邊，則稱G1是G2的一個部分圖。 （４）支撐子圖：若G1 是G2的部分圖，且G1是連通圖，則稱G1是G2的支撐子圖。 （５）生成子圖：若G1 是G2的真子圖，且G1是不連通圖，則稱G1是G2的生成子圖。 例如，圖7-2中，（b）是(a)的真子圖,(c) 是(a)的部分圖，(d)是(a)上午支撐子圖，(e)是(a)的生成子圖。 定義7 設(shè)G

9、=(V , E)中，對任意一條邊e∈E,如果相應(yīng)都有一個權(quán)值w(e)，則稱G為賦權(quán)圖。w(e) 稱為邊e的權(quán)。 圖7-2是一個賦權(quán)圖。 e1 = [v1 , v2] , w(e1) = 1 ; e2 = [v1 , v3] , w(e2) = 4 ; e3 = [v2 , v3] , w(e3) = 2 e4 = [v2 , v4] , w(e4) = 3 ; e5 = [v3 , v4] , w(e5) = 1 ; e6 = [v2 , v5] , w(e6) = 5 e7 = [v4 , v5] , w(e7) = 2 ; e8 = [v2 , v5] ,

10、w(e8) = 3 可見，賦權(quán)圖不僅指出各點之間的鄰接關(guān)系，而且也表示各點之間的數(shù)量關(guān)系。所以賦權(quán)圖在圖的理論及其應(yīng)用方面有著重要的地位。 在很多實際問題中，事物之間的聯(lián)系是帶有方向性的。例如圖7-4所示。v1表示某一水系的發(fā)源地，v6表示這個水系的入?？冢瑘D中的箭頭則表示各支流的水流方向，圖7-4是水系流向圖。 可見圖7-4中的邊是有方向的，稱這類圖為有向圖。 定義8 設(shè)V=｛v1,v2, …，vn｝是由n個頂點組成的非空集合，A=｛a1,a2,…，am｝是由m條邊組成的集合，且有A中元素ai是V中一個有序元素對(vi,vj)，則稱V和A構(gòu)成一個有向圖，記作G= (V

11、, A),ai=(vi,vj)表明vi和vj分別為ai邊的起點和終點，稱有方向的邊ai為?。ㄔ趫D中用帶有箭頭的線表示）。 例如，圖7-4中，(v1,v2),(v1,v3),(v2,v5)都是A中的元素，A是弧的集合。 在有向圖的討論中，類似無向圖，可以對多重邊、環(huán)、簡單圖、鏈等概念進行定義，只是在無向圖中，鏈與路、閉鏈與回路概念是一致的，而在有向圖中，這兩個概念不能混為一談。概括地說，一條路必定是一條鏈。然而在有向圖中，一條鏈未必是一條路，只有在每相鄰的兩弧的公共結(jié)點是其中一條弧的終點，同時又是另一條弧的始點時，這條鏈才能叫做一條路。 例如，圖7-4中，｛v1,(v1,v2),v

12、2,(v2,v5),v5,(v5,v6),v6｝是一條鏈，也是一條路。而｛v1,(v1,v2),v2,(v2,v5),v5,(v3,v5),v3｝是一條鏈但不是一條路。 我們還會碰到這樣一類有向圖（見圖7-5），這是某地區(qū)的交通運輸分布、走向及相應(yīng)費用示意圖。箭頭表示走向，箭頭旁邊的數(shù)字表示費用，稱這類圖為賦權(quán)有向圖。 定義9 設(shè)在有向圖G= ( V，A )中對任意一條弧aij∈A，如果相應(yīng)都有一個權(quán)值w(aij)則稱G為賦權(quán)有向圖。W(aij)稱為弧aij的權(quán)。簡記為wij（權(quán)可以表示距離、費用和時間等）。 在實際工作中，有很多問題的可行解方案都可以通過一個賦權(quán)有向圖表

13、示，例如：物流渠道的設(shè)計、物資運輸路線的安排、裝卸設(shè)備的更新、排水管道的鋪設(shè)等、所以賦權(quán)圖被廣泛應(yīng)用于解決工程技術(shù)及科學(xué)管理等領(lǐng)域的最優(yōu)化問題。 通常我們稱賦權(quán)圖為網(wǎng)絡(luò)，賦權(quán)有向圖為有向網(wǎng)絡(luò)，賦權(quán)無向圖為無向網(wǎng)絡(luò)。本章將在后面幾節(jié)逐一介紹。 2 樹及最小樹問題 樹是圖論中一個重要概念，由于樹的模型簡單實用，它在企業(yè)管理、線路設(shè)計等方面都有很重要的應(yīng)用。 2.1 樹與樹的性質(zhì) 例1 例1 某企業(yè)的組織機構(gòu)如下所示 如果用圖表示，見圖7-6是一個呈樹枝形狀的圖，“樹”的名稱由此而來。 圖7-6 定義10 一個無回路（圈）的連通無向圖稱為樹。

14、 樹的性質(zhì) （1）必連通，但無回路（圈）； （2）n個頂點的樹必有n-1條邊； （3）樹中任意兩點間，恰有一條初等鏈； （4）樹連通，但去掉任意一條邊，必變?yōu)椴贿B通； （5）樹無回路（圈），但不相鄰頂點連一條邊，恰得一回路（圈）。 2.2 支撐樹與最小樹 定義11 設(shè)圖 是圖 的支撐子圖，如果是一棵樹 ，記 。則稱 是 的一棵支撐樹。 定理3 圖G有支撐樹的充分必要條件是圖G是連通的。 證 必要性是顯然的。 充分性：設(shè)G是連通圖。 （i）如果G不含圈，由定義10可知，G本身就是一棵樹，從而G是它自身的支撐樹。 （ii）如果G含圈，任取一圈，

15、從圈中任意去掉一條邊，得到圖G的一個支撐子圖G1。如果G1不含圈，那么G1是G的一棵支撐樹（因為易見G1是連通的）；如果G1仍含圈，那么從G1中任取一個圈，從圈中再任意去掉一條邊，得到圖G的一個支撐子圖G2，如此重復(fù)，最終可以得到G的一個支撐子圖Gk，它不含圈，則Gk是圖G的一棵支撐樹。 由以上充分性的證明中，提供了一個尋求連通圖的支撐樹的方法。稱這種方法為“破圈法”。 例2 在圖7-2（a）中，用破圈法求出圖的一棵支撐樹。 解: 取一圈｛v1 e1 v2 e3 v3 e2 v1｝去掉e3；取一圈｛v1 e1 v2 e4 v4 e5 v3 e2 v1｝去掉e5；取一圈｛v2 e4

16、v4 e7 v5 e6 v2｝去掉e7；取一圈｛v1 e1 v2 e6 v5 e8 v3 e2 v1｝去掉e6； 如圖7-7所示，此圖是圖7-2(a)的一個支撐子圖，且為一棵樹（無圈），所以我們找到一棵支撐樹T1=｛V,E1｝，其中E1=｛e1,e4,e2,e8｝。 7-2（a） 不難發(fā)現(xiàn)，圖的支持樹不是唯一的，對于上例若這樣做： 取一圈｛v1 e1 v2 e3 v3 e2 v1｝去掉e3；取一圈j｛v1 e1 v2 e4 v5 e5 v3 e2 v1｝去掉e4；取一圈｛v1 e1 v2 e6 v5 e8 v3 e2 v1｝去掉e6；取一圈｛v4 e7 v5 e8 v3 e5 v4

17、｝去掉e8。 如圖7-8所示，得到圖7-2(a)的另一棵支撐樹T2=｛V,E2｝，其中，E2=｛e1,e2,e5,e7｝。 求圖G的支撐樹還有另一種方法“避圈法”，主要步驟是在圖中任取一條邊e1，找出一條不與e1構(gòu)成圈的邊e2，再找出不與｛e1,e2｝構(gòu)成圈的邊e3。一般地，設(shè)已有｛e1,e2,…，ek｝，找出一條不與｛e1,e2,…，ek｝構(gòu)成圈的邊ek+1，重復(fù)這個過程，直到不能進行下去為止。這是，由所有取出的邊所構(gòu)成的圖是圖G的一棵支撐樹。 定義12 設(shè)T=(V,)是賦權(quán)圖G=(V,E)的一棵支撐樹，稱中全部邊上的權(quán)數(shù)之和為支撐樹T的權(quán)，記為w(T)。即

18、 (7.2) 如果支撐樹T*的權(quán)W(T*)是G的所有支撐樹的權(quán)中最小者，則稱T*是G的最小支撐樹，簡稱最小樹。即 (7.3) 式中對G的所有支撐樹T取最小。 求最小樹通常用以下兩種方法。 (1).破圈法：在給定連通圖G中，任取一圈，去掉一條最大權(quán)邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條邊），在余圖中（是圖G的支撐子圖）任取一圈，去掉一條最大權(quán)邊，重復(fù)下去，直到余圖中無圈為止，即可得到圖G的最小樹。 例

19、3 用破圈法求解圖7-3的最小樹。 解: 取一圈｛v1 e1 v2 e3 v3 e2 v1｝去掉e2；取一圈｛v2 e6 v5 e8 v3 e3 v2｝去掉e6；取一圈｛v2 e4 v4 e5 v3 e3 v2｝去掉e8；取一圈｛v4 e7 v5 e8 v3 e5 v4｝去掉e8。 如圖7-9所示，得到一棵支撐樹，即為所求最小樹T*,w(T*)=1+2+1+2=6。 （2）避圈法（kruskal算法）：在連通圖G中，任取權(quán)值最小的一條邊（若有兩條或兩條以權(quán)數(shù)相同且最小，則任取一條），在未選邊中選一條權(quán)值權(quán)值最小的邊，要求所選邊與已選邊不構(gòu)成圈，重復(fù)下去，直到不存在與已選邊不構(gòu)成圈的

20、邊為止。已選邊與頂點構(gòu)成的圖T就是所求最小樹。 算法的具體步驟如下： 第1步：令i=1，E0=Φ（空集）。 第2步：選一條邊ei∈E\Ei，且ei是使圖Gi=(V , Ei-1∪｛e｝)中不含圈的所有邊中權(quán)最小的邊e(e∈E\Ei)。如果這樣的邊不存在，則T=(V,Ei-1)是最小樹。 第3步：把i換成i+1，返回第2步。 例4 用避圈法求圖7-3的最小樹。 解 在｛e1,e2,…，e8｝中權(quán)值最小的邊有e1,e5，從中任取一條e1；在｛e2,e3,…，e8｝中選取權(quán)值最小的邊e5；在｛e2,e2,…，e8｝中權(quán)值最小的邊有e3,e7，從中任取一條邊e3；在｛e2,e4

21、,e6,e7,e8｝中選取e7；在｛e2,e4,e6,e8｝中選取e4,e8。但e4與e8都會與已選取邊構(gòu)成圈，故停止。得到與圖7-9一樣的結(jié)果。 結(jié)果。 3 最短路問題 最短路問題是網(wǎng)絡(luò)分析中的一個基本問題，它不僅可以直接應(yīng)用于于解決生產(chǎn)實際的許多問題，若管道鋪設(shè)、線路安排、廠區(qū)布局等，而且經(jīng)常被作為一個基本工具，用于解決其它的優(yōu)化問題. 定義 13 給定一個賦權(quán)有向圖D = (V,A)，記D中每一條弧 上的權(quán)為 。給定D中一個起點 和 終點，設(shè)P是D中從 到 的一條路.則定義路P的權(quán)是P中所有弧的權(quán)之和.記為 ，即

22、 (7.4) 又若P*是D圖中 到 的一條路，且滿足 (7.5) 式中對D的所有從 到 的路P取最小，則稱P*為從 到 的最短路， 為 從 到的最短距離. 在一個圖D=（V，A）中，求從 到 的最短路和最短距離的問題就稱為最短路問題. 3.1 Dijkstra標(biāo)號法 下面介紹在一個賦權(quán)有向圖中尋求最短路的方法，這種方法實際上求出了從給定到任一個頂點的最短路. 如下事實是經(jīng)常要利用的，即如果P是D中從到的最短路，是P中的一點，那么從沿P到路也是從到的最短路.事實上，如果這個結(jié)論不

23、成立，設(shè)Q是從到的最短路，令P/是從沿Q到達，再從沿P到達的路，那么P/的權(quán)就比P的權(quán)小，這與P是從到的最短路矛盾. Dijkstra算法是沒有前公認最好的方法，它適合所有的的情形. Dijkstra算法是一種標(biāo)記法，它的基本思路是從起點 出發(fā)，逐步向外探尋最短路，執(zhí)行過程中，給每一個頂點 標(biāo)號 .其中 是正數(shù)，它表示獲得此標(biāo)號的前一點的下標(biāo)； 或表示從起點 到該點 的最短路的權(quán)（稱為固定標(biāo)號，記為P標(biāo)號）或表示從起點 到該點 的最短路的權(quán)的上界（稱為臨時標(biāo)號，記為T標(biāo)號）. 方法的每一步是去修改T標(biāo)號，并且把某一

24、個具有T標(biāo)號的點改變?yōu)榫哂蠵標(biāo)號的點，從而使D中具有標(biāo)號的頂點數(shù)為多一個.這樣至多經(jīng)過p-1步，就可以求出從到及各點的最短路.再根據(jù)每一點的第一個數(shù)反向追蹤找出最短路徑. 用P,T分別表示某個頂點的P標(biāo)號、T標(biāo)號,表示在第i步已具有P標(biāo)號點的集合. Dijkstra算法的具體步驟： （1）開始時，令 （1）如果 ，算法終止.這時，對每個 ；否則轉(zhuǎn)下一步。 （2） 設(shè) 是剛獲得P標(biāo)號的點.考察每個使 修改為即 （7.6） 如果 則把T(vj)修改為 ，把 修改為 ；否則不修改. （3）令 .

25、 （7.7） 如果 ，則把 的T標(biāo)號變?yōu)镻標(biāo)號，即令 ，令 ,k=ji,把i換成i+1，返回（1）；否則終止，這時對每一個 有 ；而對每一個 ，有 . 例1 如圖7-10所示是某地區(qū)交通運輸?shù)氖疽鈭D.試問：從 出發(fā)，經(jīng)哪條路線到達 才能使總行程最短？用Dijkstra算法求解. 解 開始時 ， ，令 （j=2,3,…，8），k=1.即給起點 標(biāo)（0，0），給其余的點表（1， ）.這時 為獲得P標(biāo)號的點，其余均為T標(biāo)號點.. 考察與相鄰的點(見圖7-11)： 因,故把的臨時標(biāo)號修改為

26、 ， 這時。同理，得 ， . （見圖7-11）.其余點的T標(biāo)號不變.在所有的T標(biāo)號中，最小的為, 于是令. i=1: 這時為剛獲得P標(biāo)號的點，考察與相鄰的點(見圖7-12)： 因，故把的臨時標(biāo)號修改為 。 這時，同理得 在所有的T標(biāo)號中，最小的為，于是令,=3. i=2: 這時為剛獲得P標(biāo)號的點，考察與相鄰的點（見圖7-13）. 因，故把的臨時標(biāo)號修改為 同理得 . 在所有的T標(biāo)號中，最

27、小的為()=5，于是令 ,=4. i=3: 這時為剛獲得P標(biāo)號的點.考察與相鄰的點(見圖7-14). 因為。故把的臨時標(biāo)號修改為 . 這時的臨時標(biāo)號不修改,故=3,同理得 在所有的臨時標(biāo)號中,最小的為, i=4: 這時為剛獲得P標(biāo)號的點,考察與相鄰的點(見圖7-15): 因為故把的臨時標(biāo)號修改為 . 這時，同理得 . 在所有的臨時標(biāo)號中，最小的為，于是令，。 i=5: 這時為剛獲得P標(biāo)號的點，考察與相鄰的點(見圖7-16)： 因為，故把的臨時標(biāo)號修改為

28、 。 這時. 這所有的臨時標(biāo)號中，最小的為，于是令,. i=6: 這時為剛獲得P標(biāo)號的點，考察與相鄰的點(見圖7-17)： 因為.故把的臨時標(biāo)號修改為 . 這時的臨時標(biāo)號不修改，故. 最后只剩下一個臨時標(biāo)號，故令 。 至此已找到從起點到終點的最短距離為12.再根據(jù)第一個標(biāo)號反向追蹤求出最短路徑為： 事實上，按照這個算法，也找出了起點到各個中間點的最短路徑和最短距離.例如

29、 就是從到最短路徑，距離為8. 為了簡化計算，還可以采用每次只記錄從起點到各點的最短距離或上界的方法.為此我們引入記號 表示在第i次標(biāo)號中各點的距離和上界.例如上例中，我們也可以接如下方式進行: 有“*”號的點表示P標(biāo)號點. 最后按后面的軌跡記錄反向追蹤可求得從起點到終點的最短路,且最后一輪標(biāo)號中所表示的就是從起點到各點的最短距離. 另外，本算法在給某個點標(biāo)號時，也可以通過找該點的各個來源點的方法來實現(xiàn)，具體作法如下： 開始時，給起點標(biāo)（0，0），即 一般地，在給起點標(biāo)號時，要找

30、出所有與有弧相聯(lián)且箭頭指向的各點（稱為的來源點）,不妨設(shè)是的來源點，其標(biāo)號為 為弧的權(quán)值 ，則給點標(biāo)以(,l()),其中 根據(jù)別爾曼優(yōu)化原理，由始點到的最短路徑必是由到某個的最短路徑再加上弧(,)的權(quán)值。是到最短路徑的點，且是的來源點，顯然，是到最段路徑的長度,所以給每個頂點以標(biāo)號即可獲得最短路徑和長度的信息. 下面，以圖7-10為例，說明標(biāo)號法的具體過程. 首先給始點標(biāo)號，第一個標(biāo)號表示的是來源點，第二個標(biāo)號表示.由于是始點,故令始點的第一個標(biāo)號為0，令，于是得到始點的標(biāo)號(0,0). 點的來源是，且可由(7.8）計算即

31、 得到的標(biāo)號（,3）. 點的來源點有，計算 , 得到的標(biāo)號（,4）. 的來源點有,計算 于是得到的標(biāo)號(,5). 的來源有，,但還未標(biāo)號，而的來源點,,都已經(jīng)獲得標(biāo)號，故可計算 。 因而得到的標(biāo)號(,6).計算 故的標(biāo)號為（,8）. 的來源點是, ,計算 ， 得到的標(biāo)號(,7). 最后終點的來源點是,,,計算 ， 所以在終點處標(biāo)上(,12)，標(biāo)號過程結(jié)束，見圖7-18所示. 我們沿著第一個標(biāo)號，由終點

32、反向跟蹤，很容易求得該網(wǎng)絡(luò)最短路徑，而終點的第二個標(biāo)號就是此最短路長度. 上述標(biāo)號過程中，不僅可以求得到的最短路，而且從到(=2,3,4,5,6,7)的最短路都可求得.例如，到的最短路是，最短路長度為8. 歸納上述例子，可以總結(jié)標(biāo)號法一般步驟如下： (1) (1) 始點 標(biāo)以（0.0）； (2) (2) 考慮需要標(biāo)號的頂點 ，設(shè) 的來源點 均已獲得標(biāo)號，則 處應(yīng)標(biāo)以 ，其中 按（7.8）式確定. (3) (3) 重復(fù)第（2）步，直至終點 也獲得標(biāo)號為止， 就是最短路徑的長度. (4) (4) 確定最短路徑，從網(wǎng)絡(luò)終點的第一個標(biāo)號反向跟蹤，即得到網(wǎng)絡(luò)的最短路徑. 以上例1是非負

33、權(quán)（即 ）網(wǎng)絡(luò)最短路徑的求解，對于含有負權(quán)（即 網(wǎng)絡(luò)的情形，此標(biāo)號法也是適用的，請看下面例題. 例 2 求圖7-19所示從始點 到各點的最短路徑. 解 首先在始點 標(biāo)以（0,0），然后在處標(biāo)以（ ,-2）,由于 所以在和處依次標(biāo)以（,-5）和(,-7)，然后在處標(biāo)以（,-1）. 由于 所以在和處分別標(biāo)以(,-4)和（，-5） 最后由于 所以在終點處應(yīng)標(biāo)以(,3). 所有點都獲得標(biāo)號，

34、標(biāo)號結(jié)果見圖7-20，反追蹤得到 至 的最短路為 .長度為3. 4 網(wǎng)絡(luò)最大流問題 網(wǎng)絡(luò)最大流問題是網(wǎng)絡(luò)的另一個基本問題。 許多系統(tǒng)包含了流量問題。例如交通系統(tǒng)有車流量，金融系統(tǒng)有現(xiàn)金流，控制系統(tǒng)有信息流等。許多流問題主要是確定這類系統(tǒng)網(wǎng)絡(luò)所能承受的最大流量以及如何達到這個最大流量。 4.1 基本概念與定理 1． 1． 網(wǎng)絡(luò)與流 定義14 （1）網(wǎng)絡(luò)： 例1 如圖7-20是連結(jié)某產(chǎn)品產(chǎn)地 和銷地 的交通圖?；?表示從 到 的運輸線，弧旁的數(shù)字表示這條運輸線的最大通過能力 ，括號內(nèi)的數(shù)字表示該弧上的實際流 ?，F(xiàn)要求制定一個運輸方案，使從 運到 的產(chǎn)品數(shù)量

35、最多。 可行流與最大流 在運輸網(wǎng)絡(luò)的實際問題中，我們可以看出，對于流有兩個基本要求： 一是每條弧上的流量必須是非負的且不能超過該弧的最大通過能力（即該弧的容量）； 二是起點發(fā)出的流的總和（稱為流量），必須等于終點接收的流的總和，且各中間點流入的流量之和必須等于從該點流出的流量之和，即流入的流量之和與流出的流量之和的差為零，也就是說各中間點只起轉(zhuǎn)運作用，它既不產(chǎn)出新的物資，也不得截留過境的物資。 因此有下面所謂的可行流的定義。 定義14 對于給定的網(wǎng)絡(luò)D=（V,A,C）和給定的流 ，若 滿足下列條件： （1） （1） 容量限制條件：對每一條弧 ，有

36、 (7.9) （2）平衡條件： 對于中間點： 流出量=流入量，即對于每一個i (i≠s,t)，有 (7.10) 對于出發(fā)帶點 ，有 (7.11) 對于收點 ，有 (7.12) 則稱 為一個可行流， 稱為這個可行流的流量。 注意，我們這里所

37、說的出發(fā)點 是指只有從 發(fā)出去的弧，而沒有指向 的弧；收點 是指只有弧指向 ，而沒有從它的發(fā)出去的弧。 可行流總是存在的。例如令所有弧上的流 ，就得到一個可行流，（稱為零流），其流量 。 如圖7-20中，每條弧上括號內(nèi)的數(shù)字給出的就是一個可行流 ，它顯然滿足定義中的條件（1）和（2）。其流量 。 所謂網(wǎng)絡(luò)最大流問題就是求一個流 ，使得總流量 達到最大，并且滿足定義15中的條件（1）和（2），即 max (7.13)

38、 網(wǎng)絡(luò)最大流問題是一個特殊的線性規(guī)劃問題。我們將會看到利用圖的特點，解決這個問題的方法較直線性規(guī)劃的一般方法要簡便和直觀的多。 例2 寫出圖7-20所表示的網(wǎng)絡(luò)最大流問題的線性規(guī)劃模型。 解 設(shè) ，則其線性規(guī)劃模型為 max 3. 增廣鏈 在網(wǎng)絡(luò)D=(V,A,C)中，若給定一個可行流 ，我們把網(wǎng)絡(luò)中使 的弧稱為飽和弧，使 的弧稱為非飽和弧。把 的弧稱為零流弧，把 的稱為非零流弧。 如圖7-20中的弧都是非飽和弧，而弧 為零流弧。 若 是網(wǎng)絡(luò)中聯(lián)

39、結(jié)發(fā)點 和收點 的一條鏈，我定義鏈的方向是從 到 S ，則鏈上的弧被分為兩： 一類是：弧的方向與鏈的方向一致，我們稱此類和為前向弧，所有前向弧的集合記為 。 另一類是：弧的方向與鏈的方向一致，我們稱此類弧為后向弧，所有后向弧的集合記為 。 如圖7-20中，設(shè) 是一條從 到 的鏈， 則 , 定義15 設(shè) 是網(wǎng)絡(luò)D=(V,A,C)上的一個可行流， 是從 到 的一條鏈，若 滿足下列條件： (1)在弧 (vi,vj)∈μ+上，即 中的每一條弧都是非飽和??； (2)在弧 上，即 中的每一條弧都是非零流弧。 則稱 是關(guān)于 的一條增廣鏈。 如前面所說的鏈就是一條增廣鏈。因為其中

40、μ+上的弧均非飽和，如(vs,v2) ∈μ+,fs2=50，。顯然這樣的增廣鏈不止一條。 4.截集與截量 定義16 給定網(wǎng)絡(luò)D=(V,A,C)，若點集V被分割成兩個非空集合V1和V2，使得V=V1+V2,V1∩V2=φ(空集)，且vs∈V1,vt∈V2，則把始點在V1,終點在V2的弧的集合稱為分離vs和vt的一個截集，記為(V1,V2)。 如圖9.26中，設(shè)V1=｛vs,v2,v5｝，V2=｛v3,v4,v6,vt｝則截集為 , 而弧(v3,v2)和(

41、v4,v5)不是該集中的弧。因為這兩條弧的起點在V2中，與定義17不符。 顯然，一個網(wǎng)絡(luò)的截集是很多的（但只有有限個），例如在圖7-20中，還可以取 , ，則截集為 另外，若把網(wǎng)絡(luò)D=(V,A,C)中某截集的弧從網(wǎng)絡(luò)D中去掉，則從vs到vt便不存在路，所以直觀上說，截集是從vs到vt的必經(jīng)之路。 定義17 在網(wǎng)絡(luò)D=(V,A,C)中，給定一個截集(V1,V2)，則把該截集中所有弧的容量之和，稱為這個截集的容量，簡稱為截量，記為c(V1,V2)，即 C(V1,V2)=

42、 (7.16) 例如在上面我們所舉的兩個截集中，有 而 顯然，截集不同，其截量也不同。由于截集的個數(shù)是有限的，故其中必有一個截集的容量是最小的，稱為最小截集，也就是通常所說的“瓶頸”。 不難證明，網(wǎng)絡(luò)D=(V,A,C)中，任何一個可行流f=｛fij｝的流量V(f)，都不會超過任一截集的容量，即 v( f ) ≤ c(V1,V2) (

43、7.17) 如果存在一個可行流f*=｛f*ij｝，網(wǎng)絡(luò)D=(V,A,C)中有一個截集 ，使得 (7.18) 則 必是最大流，而 必是D中的最小截集。 為了求網(wǎng)絡(luò)最大流f*，我們也說明下面的重要定理。 定理4 在網(wǎng)絡(luò)D=(V,A,C)中，可行流 是最大流的充要條件是D中不存在關(guān)于f*的增廣鏈。 證 先證必要性。用反證法。若f*是最大流，假設(shè)D中存在著關(guān)于f*的增廣鏈μ，令 (7.19)

44、由增廣鏈的定義可知θ>0，令 (7.20) 不難驗證 是一個可行流，且有 這與f*是最大流的假定矛盾。 再證充分性：即證明設(shè)D中不存在關(guān)于f*的增廣鏈，f*是最大流。 用下面的方法定義：令 若 ，且有 ，則令 ； 若 ，且有 ，則令 。 因為不存在著關(guān)于 的增廣鏈，故 記 ，于是得到一個截集(V*, )。顯然有 所以V(f*)=c ，于是f*必是最大流。定理得證。 由上述證明中可見，若 是最

45、大流，則網(wǎng)絡(luò)必定存在一個截集 ，使得(7.18)式成立。 定理5 （最大流——最小截集定理）對于任意給定的網(wǎng)絡(luò)D=(V,A,C)，從出發(fā)點vs到收點vt的最大流的流量必等于分割 和 的最小截集 的容量，即 由定理4可知，若給定一個可行流 ，只要判斷網(wǎng)絡(luò)D有無關(guān)于 的增廣鏈。如果有增廣鏈，則可以按定理4前半部分證明中的辦法，由公式(7.19)求出調(diào)整量Q，再按式（7.20）的方法求出新的可行流。如果流有增廣鏈，則得到最大流。而根據(jù)定理4后半部分證明中定義 的辦法，可以根據(jù)vt是否屬于 來判斷D中有無關(guān)于f的增廣鏈。 在實際計算時，我們是用給頂點標(biāo)號的方法來定義 的，在標(biāo)號過程中，

46、有標(biāo)號的頂點表示是 中的點，沒有標(biāo)號的點表示不是 中的點。一旦有了標(biāo)號，就表明找到一條從vs到vt的增廣鏈；如果標(biāo)號過程無法進行下去，而vt尚未標(biāo)號，則說明不存在從vs到vt的增廣鏈，于是得到最大流。這時將已標(biāo)號的點（至少有一個點vs）放在集合 中，將未標(biāo)號點（至少有一個點vt）放在集合 中，就得到一個最小截集 。 4.2 尋求最大流的標(biāo)號法（Ford , Fulkerson） 從一個可行流出發(fā) （若網(wǎng)絡(luò)中沒有給定 ，則可以設(shè) 是零流），經(jīng)過標(biāo)號過程與調(diào)整過程。 1） 1） 標(biāo)號過程 在這個過程中，網(wǎng)絡(luò)中的點或者是標(biāo)號點（又分為已檢查和未檢查兩種），或者是未標(biāo)號點，每個標(biāo)號

47、點的標(biāo)號包含兩部分：第一個標(biāo)號表明它的標(biāo)號是從哪一點得到的，以便找出增廣鏈；第二個標(biāo)號是為確定增廣鏈的調(diào)整量θ用的。 標(biāo)號過程開始，總先給vs標(biāo)上(0,+∞)，這時vs是標(biāo)號而未檢查的點，其余都是未標(biāo)號點，一般地，取一個標(biāo)號而未檢查的點vi，對一切未標(biāo)號點vj： (1) 在弧上 ， ，則給vj標(biāo)號 。這里 。這時點vj成為標(biāo)號而未檢查的點。 (2) 若在弧 上， ，給vj標(biāo)號 。這里 。這時點vj成為標(biāo)號而未檢查的點。 于是 成為標(biāo)號而已檢查過的點，重復(fù)上述步驟，一旦 被標(biāo)上號，表明得到一條從 到 的增廣鏈 ，轉(zhuǎn)入調(diào)整過程。 若所有標(biāo)號都是已檢查過，而標(biāo)號過程進行不下去時，則算法結(jié)束

48、，這時的可行流就是最大流。 2） 2 調(diào)整過程 首先按 及其它點的第一個標(biāo)號，利用“反向追蹤”的辦法，找出增廣鏈μ。例如設(shè)vt的第一個標(biāo)號為 （或 ），則弧 （或相應(yīng)地 ）是μ上的弧。接下來檢查 的第一個標(biāo)號，若為 （或 ），則找出 （或相應(yīng)地 ）。再檢查 的第一個標(biāo)號，依此下去，直到 為止。這時被找出的弧就構(gòu)成了增廣鏈 。令調(diào)整量θ是 ，即 的第二個標(biāo)號。 令 去掉所有的標(biāo)號，對新的可行流 ，重新進入標(biāo)號過程。 下面，以例題說明此算法求解過程。 例3 用標(biāo)號法求圖7-20所示網(wǎng)絡(luò)最大流?；∨缘臄?shù)是 解 :對圖7-20中各頂點進行標(biāo)號。 首先給 標(biāo)(0,+∞

49、)，即 檢查 ： 在弧 上，因為 ，又有 ,所以給 標(biāo) ； 在弧上 ，因為 ，又有 ,所以給 標(biāo) 。 檢查 ： 在弧上 ，因為 ，又有 ,所以給 標(biāo) ； 在弧上 ，因為 ，又有 ,所以給 標(biāo) ； 在弧 上，因為 ，又有 ,所以給V3標(biāo) 。 因為前面已給v3標(biāo)過號 ，這里又給 標(biāo) ，它們分別表示兩條不同的路線，這里不存在修改標(biāo)號的問題（與最短路不同）。因為我們的目標(biāo)是盡快找出一條從vs到vt的增廣鏈，即盡快使終點vt獲得標(biāo)號，所以不必在中途過多停留。也就是說在對已標(biāo)號點vi進行檢查時，每次只檢查一個相鄰點vj（不論前向弧或后向弧均可），再給標(biāo)號即可，而不必檢查所有與v

50、i相鄰的點。事實上，其余的相鄰點也不會漏掉，因為以后還要通過檢查這些點來找出新的增廣鏈。以下我們就按這種思路進行。 檢查： 在弧 上，因為 ，又有 .所以給 標(biāo) . 至此，終點 已獲得標(biāo)號，于是找出一條 從到 的增廣鏈。再由標(biāo)號的第一部分用反向追蹤法找出路線，即 （見圖7-21）。 進行調(diào)查： 這時的調(diào)整量 .再按公式（7.20）調(diào)整。由于 上各弧均為前向弧，故得 ， ，

51、 . （見圖7-21）.其余的 不變. 對這個新的可行流再進入標(biāo)號過程，尋找新增廣鏈。開始給 標(biāo) ，檢查 ，給 標(biāo) ，檢查 ： 在弧 上，因為 （見圖7-21），故該弧已飽和，標(biāo)號無法進行下去。 在弧 上，因為 ，又有 所以給 標(biāo) ， 檢查 ： 在弧 上，因為 ，又有 所以給 標(biāo) ， 檢查 ： 在弧 上，因為 ，又有 ，所以給 標(biāo) . 于是又得到一條增廣鏈 (見圖7-22) 進行調(diào)整： 這時 。調(diào)整結(jié)果如圖9.28所示。再重新標(biāo)號求新的增廣鏈. 開始給 標(biāo) ，檢查 ，給 標(biāo) 。檢查 ，給 標(biāo) ，檢查 ，給 標(biāo) ，檢查 ，因

52、 已是飽和弧（見圖7-22）。標(biāo)號無法進行。 但在弧 上， .又有 ，所以給 標(biāo) . 于是又得到一條增廣鏈： . 再進行調(diào)整（見圖7-23）. 再重新進行標(biāo)號求新的增廣鏈： 開始給 標(biāo)（0，+ ），檢查 ，給 標(biāo) . 檢查 ： 這時弧 均已飽和。而在弧 上，因 ，又有 所以給 標(biāo) ，表明弧 為后向弧. 檢查 ，給 標(biāo) 。檢查 ，給 標(biāo) 。于是又得到一條增廣鏈： . 再進行調(diào)整（見圖7-24）。 再重新進行標(biāo)號求新的增廣鏈： 開始給 標(biāo)(0,+∞)，檢查 ，給 標(biāo) 。檢查 ，這時 和 均為前向弧，都已

53、飽和，弧 為后向弧，且為零流弧 。故標(biāo)號無法進行。但在弧 上因為 。又有 .所以給 標(biāo) . 檢查 ,給 標(biāo) 。檢查 ，因為 已飽和（見圖7-24）。而在弧 上，因為 ，又有 .所以給 標(biāo) ，再檢查 ，給 標(biāo) 。于是又得到一條增廣鏈： . 再進行調(diào)整（見圖7-25）。 再重新進行標(biāo)號求新的增廣鏈。 開始給 標(biāo)(0,+∞)，檢查 ，給 標(biāo) 。檢查 ，因為 已飽和，而為弧 上標(biāo)號還可以繼續(xù)進行，給 標(biāo) 。檢查 。給 標(biāo) 。于是又得到一條增廣鏈

54、 再進行調(diào)整（見圖7-26）。 再重新進行標(biāo)號： 開始給 標(biāo)(0,+∞)，檢查 ：這時弧 已飽和。標(biāo)號無法進行。而 還可以標(biāo)號 。 再檢查 ，如前所述，標(biāo)號也無法進行。 至此已求得最大流。我們將最大流 表示在圖7-27中。最大流量為 與此同時，可找到最小截集 ，其中 為最后一輪已標(biāo)號點的集合， 為未標(biāo)號點的集合，即 最小截量為 所以 。 圖7-27 由上述可見，用標(biāo)號法找增廣鏈以求最大流的結(jié)果，同時也得到一個最小截集。最小截集的容量的大小影

55、響總的運輸量的提高。因此，為提高總的運輸量，必須首先考慮增大最小截集中各弧的容量，提高它們的通過能力。反之，一旦最小截集中弧的通過能力降低，必然會使得運輸量減少。 前面討論都是對一個發(fā)點、一個收點的網(wǎng)絡(luò)最大流問題。對于多個發(fā)點和收點的情形，我們可以采取虛設(shè)一個總發(fā)點 和總收點 ，從總發(fā)點 到各發(fā)點 均以弧相聯(lián)，并且令這些弧的容量均為∞或某一具體值（根據(jù)情況而定）。同樣，從各個收點 到總收點 亦以弧相聯(lián)，也令這些弧的容量為∞或某一具體值。這樣，原來的發(fā)點 與收點 都變成了轉(zhuǎn)運點，原來的問題就轉(zhuǎn)變成一個發(fā)點一個收點的網(wǎng)絡(luò)圖。例如圖7-28所示是兩個發(fā)點兩個收點的網(wǎng)絡(luò)，可以轉(zhuǎn)換成一個發(fā)點一個收點的網(wǎng)絡(luò)，見圖7-29所示。 圖7-29