《第七章圖與網(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和表示事物之間關(guān)系邊的集合E=e1,e2,，em所組成，且E中元素e

2、i是由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 = 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的

3、關(guān)聯(lián)邊。（）相鄰點和相鄰邊：同一條邊的兩個端點稱為相鄰點，簡稱鄰點；有公共端點的兩條邊稱為相鄰邊，簡稱鄰邊。（）多重邊與環(huán)：具有相同端點的邊稱為多重邊或平行邊；兩個端點落在一個頂點的邊稱為環(huán)。（）多重圖和簡單圖：含有多重邊的圖稱為多重圖；無環(huán)也無多重邊的圖稱為簡單圖。（）次：以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)

4、聯(lián)邊；v2與v5是鄰點，e3與e2是鄰邊；e7與e8是多重邊，e4是一個環(huán)；圖.是一個多重圖；v1是懸掛點，e是懸掛邊；v是孤立點；v是奇點，v是偶點。定理圖（，）中，所有點的次之和是邊數(shù)的兩倍。即。定理是顯然的，因為在計算各點的次時，每條邊都計算兩次，于是圖中全部頂點的次之和就是邊數(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,v

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

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

7、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=(V , E)中，對任意一條邊eE,如果相應(yīng)都有一個權(quán)值w(e)，則稱G為賦權(quán)圖。w(e) 稱為邊e的權(quán)。圖7-2是一個賦權(quán)圖。 e

8、1 = 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 , w(e8) = 3可見，賦權(quán)圖不僅指出各點之間的鄰接關(guān)系，而且也表示各點之間的數(shù)量關(guān)系。所以賦權(quán)圖在圖的理論及其應(yīng)用方面有著重要的地位。在很多實際問題中，事物之間的聯(lián)系是帶有方向性的。例如圖7-4所示。

9、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 , A),ai=(vi,vj)表明vi和vj分別為ai邊的起點和終點，稱有方向的邊ai為弧（在圖中用帶有箭頭的線表示）。例如，圖7-4中，(v1,v2),(v1,v3),(v2,v5)都是A中的元素，A是弧的集合。在有向圖的討論中，類似無向圖，

10、可以對多重邊、環(huán)、簡單圖、鏈等概念進行定義，只是在無向圖中，鏈與路、閉鏈與回路概念是一致的，而在有向圖中，這兩個概念不能混為一談。概括地說，一條路必定是一條鏈。然而在有向圖中，一條鏈未必是一條路，只有在每相鄰的兩弧的公共結(jié)點是其中一條弧的終點，同時又是另一條弧的始點時，這條鏈才能叫做一條路。例如，圖7-4中，v1,(v1,v2),v2,(v2,v5),v5,(v5,v6),v6是一條鏈，也是一條路。而v1,(v1,v2),v2,(v2,v5),v5,(v3,v5),v3是一條鏈但不是一條路。我們還會碰到這樣一類有向圖（見圖7-5），這是某地區(qū)的交通運輸分布、走向及相應(yīng)費用示意圖。箭頭表示走向，

11、箭頭旁邊的數(shù)字表示費用，稱這類圖為賦權(quán)有向圖。定義9 設(shè)在有向圖G= ( V，A )中對任意一條弧aijA，如果相應(yīng)都有一個權(quán)值w(aij)則稱G為賦權(quán)有向圖。W(aij)稱為弧aij的權(quán)。簡記為wij（權(quán)可以表示距離、費用和時間等）。 在實際工作中，有很多問題的可行解方案都可以通過一個賦權(quán)有向圖表示，例如：物流渠道的設(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 樹及最小樹問題樹是圖論中一個重要概念，由于樹的模型簡單實

12、用，它在企業(yè)管理、線路設(shè)計等方面都有很重要的應(yīng)用。2.1 樹與樹的性質(zhì)例1 例1 某企業(yè)的組織機構(gòu)如下所示如果用圖表示，見圖7-6是一個呈樹枝形狀的圖，“樹”的名稱由此而來。圖7-6定義10 一個無回路（圈）的連通無向圖稱為樹。 樹的性質(zhì)（1）必連通，但無回路（圈）；（2）n個頂點的樹必有n-1條邊；（3）樹中任意兩點間，恰有一條初等鏈；（4）樹連通，但去掉任意一條邊，必變?yōu)椴贿B通；（5）樹無回路（圈），但不相鄰頂點連一條邊，恰得一回路（圈）。2.2 支撐樹與最小樹定義11 設(shè)圖 是圖 的支撐子圖，如果是一棵樹 ，記 。則稱 是 的一棵支撐樹。 定理3 圖G有支撐樹的充分必要條件是圖G是連通的

13、。證 必要性是顯然的。充分性：設(shè)G是連通圖。（i）如果G不含圈，由定義10可知，G本身就是一棵樹，從而G是它自身的支撐樹。（ii）如果G含圈，任取一圈，從圈中任意去掉一條邊，得到圖G的一個支撐子圖G1。如果G1不含圈，那么G1是G的一棵支撐樹（因為易見G1是連通的）；如果G1仍含圈，那么從G1中任取一個圈，從圈中再任意去掉一條邊，得到圖G的一個支撐子圖G2，如此重復(fù)，最終可以得到G的一個支撐子圖Gk，它不含圈，則Gk是圖G的一棵支撐樹。由以上充分性的證明中，提供了一個尋求連通圖的支撐樹的方法。稱這種方法為“破圈法”。例2 在圖7-2（a）中，用破圈法求出圖的一棵支撐樹。解: 取一圈v1 e1

14、v2 e3 v3 e2 v1去掉e3；取一圈v1 e1 v2 e4 v4 e5 v3 e2 v1去掉e5；取一圈v2 e4 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；取一圈jv1 e1 v2 e4 v5 e5 v3 e2 v1去掉e4；取一圈v1 e1 v2 e6 v5 e

15、8 v3 e2 v1去掉e6；取一圈v4 e7 v5 e8 v3 e5 v4去掉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

16、(T)。即 (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的最小樹。例3 用破圈法求解圖7-3的最小樹。解: 取一圈v1 e1 v2 e3 v3 e2 v1去掉e2；取一圈v2 e6 v5 e8 v3 e3 v2去掉e6；取一圈v2 e4 v4

17、 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)成圈的邊為止。已選邊與頂點構(gòu)成的圖T就是所求最小樹。算法的具體步驟如下：第1步：令i=1，E0=（空集）。第2步：選一條邊eiEEi，且ei是使圖Gi=(V , Ei-1e)中不含圈的所有邊中權(quán)最小的邊e(eEEi

18、)。如果這樣的邊不存在，則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,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ū)布局等，而

19、且經(jīng)常被作為一個基本工具，用于解決其它的優(yōu)化問題.定義 13 給定一個賦權(quán)有向圖D = (V,A)，記D中每一條弧 上的權(quán)為 。給定D中一個起點 和 終點，設(shè)P是D中從 到 的一條路.則定義路P的權(quán)是P中所有弧的權(quán)之和.記為 ，即 (7.4)又若P*是D圖中 到 的一條路，且滿足 (7.5)式中對D的所有從 到 的路P取最小，則稱P*為從 到 的最短路， 為 從 到的最短距離.在一個圖D=（V，A）中，求從 到 的最短路和最短距離的問題就稱為最短路問題. 3.1 Dijkstra標號法下面介紹在一個賦權(quán)有向圖中尋求最短路的方法，這種方法實際上求出了從給定到任一個頂點的最短路.如下事實是經(jīng)常要利

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

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

22、止，這時對每一個 有 ；而對每一個 ，有 . 例1 如圖7-10所示是某地區(qū)交通運輸?shù)氖疽鈭D.試問：從 出發(fā)，經(jīng)哪條路線到達 才能使總行程最短？用Dijkstra算法求解.解 開始時 ， ，令 （j=2,3,，8），k=1.即給起點 標（0，0），給其余的點表（1， ）.這時 為獲得P標號的點，其余均為T標號點.考察與相鄰的點(見圖7-11)：因,故把的臨時標號修改為 ，這時。同理，得，.（見圖7-11）.其余點的T標號不變.在所有的T標號中，最小的為, 于是令.i=1:這時為剛獲得P標號的點，考察與相鄰的點(見圖7-12)：因，故把的臨時標號修改為 。這時，同理得在所有的T標號中，最小的為，

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

24、.i=6:這時為剛獲得P標號的點，考察與相鄰的點(見圖7-17)：因為.故把的臨時標號修改為 .這時的臨時標號不修改，故. 最后只剩下一個臨時標號，故令 。至此已找到從起點到終點的最短距離為12.再根據(jù)第一個標號反向追蹤求出最短路徑為： 事實上，按照這個算法，也找出了起點到各個中間點的最短路徑和最短距離.例如 就是從到最短路徑，距離為8.為了簡化計算，還可以采用每次只記錄從起點到各點的最短距離或上界的方法.為此我們引入記號 表示在第i次標號中各點的距離和上界.例如上例中，我們也可以接如下方式進行:有“*”號的點表示P標號點.最后按后面的軌跡記錄反向追蹤可求得從起點到終點的最短路,且最后一輪標號

25、中所表示的就是從起點到各點的最短距離.另外，本算法在給某個點標號時，也可以通過找該點的各個來源點的方法來實現(xiàn)，具體作法如下：開始時，給起點標（0，0），即一般地，在給起點標號時，要找出所有與有弧相聯(lián)且箭頭指向的各點（稱為的來源點）,不妨設(shè)是的來源點，其標號為為弧的權(quán)值 ，則給點標以(,l(),其中 根據(jù)別爾曼優(yōu)化原理，由始點到的最短路徑必是由到某個的最短路徑再加上弧(,)的權(quán)值。是到最短路徑的點，且是的來源點，顯然，是到最段路徑的長度,所以給每個頂點以標號即可獲得最短路徑和長度的信息.下面，以圖7-10為例，說明標號法的具體過程.首先給始點標號，第一個標號表示的是來源點，第二個標號表示.由于是

26、始點,故令始點的第一個標號為0，令，于是得到始點的標號(0,0).點的來源是，且可由(7.8）計算即 得到的標號（,3）.點的來源點有，計算 ,得到的標號（,4）.的來源點有,計算 于是得到的標號(,5).的來源有，,但還未標號，而的來源點,都已經(jīng)獲得標號，故可計算 。因而得到的標號(,6).計算 故的標號為（,8）.的來源點是, ,計算 ，得到的標號(,7).最后終點的來源點是,計算 ，所以在終點處標上(,12)，標號過程結(jié)束，見圖7-18所示.我們沿著第一個標號，由終點反向跟蹤，很容易求得該網(wǎng)絡(luò)最短路徑，而終點的第二個標號就是此最短路長度.上述標號過程中，不僅可以求得到的最短路，而且從到(

27、=2,3,4,5,6,7)的最短路都可求得.例如，到的最短路是，最短路長度為8.歸納上述例子，可以總結(jié)標號法一般步驟如下：(1) (1) 始點 標以（0.0）；(2) (2) 考慮需要標號的頂點 ，設(shè) 的來源點 均已獲得標號，則 處應(yīng)標以 ，其中 按（7.8）式確定.(3) (3) 重復(fù)第（2）步，直至終點 也獲得標號為止， 就是最短路徑的長度.(4) (4) 確定最短路徑，從網(wǎng)絡(luò)終點的第一個標號反向跟蹤，即得到網(wǎng)絡(luò)的最短路徑.以上例1是非負權(quán)（即 ）網(wǎng)絡(luò)最短路徑的求解，對于含有負權(quán)（即網(wǎng)絡(luò)的情形，此標號法也是適用的，請看下面例題. 例 2 求圖7-19所示從始點 到各點的最短路徑.解 首先在

28、始點 標以（0,0），然后在處標以（ ,-2）,由于所以在和處依次標以（,-5）和(,-7)，然后在處標以（,-1）.由于 所以在和處分別標以(,-4)和（，-5）最后由于 所以在終點處應(yīng)標以(,3).所有點都獲得標號，標號結(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)地 和銷地

29、 的交通圖?；?表示從 到 的運輸線，弧旁的數(shù)字表示這條運輸線的最大通過能力 ，括號內(nèi)的數(shù)字表示該弧上的實際流 ?，F(xiàn)要求制定一個運輸方案，使從 運到 的產(chǎn)品數(shù)量最多?？尚辛髋c最大流在運輸網(wǎng)絡(luò)的實際問題中，我們可以看出，對于流有兩個基本要求： 一是每條弧上的流量必須是非負的且不能超過該弧的最大通過能力（即該弧的容量）；二是起點發(fā)出的流的總和（稱為流量），必須等于終點接收的流的總和，且各中間點流入的流量之和必須等于從該點流出的流量之和，即流入的流量之和與流出的流量之和的差為零，也就是說各中間點只起轉(zhuǎn)運作用，它既不產(chǎn)出新的物資，也不得截留過境的物資。因此有下面所謂的可行流的定義。定義14 對于給定的

30、網(wǎng)絡(luò)D=（V,A,C）和給定的流 ，若 滿足下列條件：（1） （1） 容量限制條件：對每一條弧 ，有 (7.9)（2）平衡條件：對于中間點：流出量=流入量，即對于每一個i (is,t)，有 (7.10)對于出發(fā)帶點 ，有 (7.11)對于收點 ，有 (7.12)則稱 為一個可行流， 稱為這個可行流的流量。注意，我們這里所說的出發(fā)點 是指只有從 發(fā)出去的弧，而沒有指向 的弧；收點 是指只有弧指向 ，而沒有從它的發(fā)出去的弧。可行流總是存在的。例如令所有弧上的流 ，就得到一個可行流，（稱為零流），其流量 。如圖7-20中，每條弧上括號內(nèi)的數(shù)字給出的就是一個可行流 ，它顯然滿足定義中的條件（1）和（2

31、）。其流量 。所謂網(wǎng)絡(luò)最大流問題就是求一個流 ，使得總流量 達到最大，并且滿足定義15中的條件（1）和（2），即max (7.13)網(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)結(jié)發(fā)點 和收點 的一條鏈，我定

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

33、.截集與截量定義16 給定網(wǎng)絡(luò)D=(V,A,C)，若點集V被分割成兩個非空集合V1和V2，使得V=V1+V2,V1V2=(空集)，且vsV1,vtV2，則把始點在V1,終點在V2的弧的集合稱為分離vs和vt的一個截集，記為(V1,V2)。如圖9.26中，設(shè)V1=vs,v2,v5，V2=v3,v4,v6,vt則截集為 ,而弧(v3,v2)和(v4,v5)不是該集中的弧。因為這兩條弧的起點在V2中，與定義17不符。顯然，一個網(wǎng)絡(luò)的截集是很多的（但只有有限個），例如在圖7-20中，還可以取 , ，則截集為 另外，若把網(wǎng)絡(luò)D=(V,A,C)中某截集的弧從網(wǎng)絡(luò)D中去掉，則從vs到vt便不存在路，所以直觀

34、上說，截集是從vs到vt的必經(jīng)之路。定義17 在網(wǎng)絡(luò)D=(V,A,C)中，給定一個截集(V1,V2)，則把該截集中所有弧的容量之和，稱為這個截集的容量，簡稱為截量，記為c(V1,V2)，即 C(V1,V2)= (7.16)例如在上面我們所舉的兩個截集中，有 而 顯然，截集不同，其截量也不同。由于截集的個數(shù)是有限的，故其中必有一個截集的容量是最小的，稱為最小截集，也就是通常所說的“瓶頸”。不難證明，網(wǎng)絡(luò)D=(V,A,C)中，任何一個可行流f=fij的流量V(f)，都不會超過任一截集的容量，即 v( f ) c(V1,V2) (7.17)如果存在一個可行流f*=f*ij，網(wǎng)絡(luò)D=(V,A,C)中有

35、一個截集 ，使得 (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)由增廣鏈的定義可知0，令 (7.20)不難驗證 是一個可行流，且有 這與f*是最大流的假定矛盾。再證充分性：即證明設(shè)D中不存在關(guān)于f*的增廣鏈，f*是最大流。用下面的方法定義：令 若 ，且有 ，則令 ；若 ，且有 ，則令 。因為不存在著關(guān)于 的增廣鏈，故 記 ，于是得到一個截集(V*, )。顯然有

36、所以V(f*)=c ，于是f*必是最大流。定理得證。由上述證明中可見，若 是最大流，則網(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的增廣鏈。在實際計算時

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

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

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

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

41、進行。檢查： 在弧 上，因為 ，又有.所以給 標 .至此，終點 已獲得標號，于是找出一條 從到 的增廣鏈。再由標號的第一部分用反向追蹤法找出路線，即 （見圖7-21）。進行調(diào)查：這時的調(diào)整量 .再按公式（7.20）調(diào)整。由于 上各弧均為前向弧，故得 ， ， .（見圖7-21）.其余的 不變.對這個新的可行流再進入標號過程，尋找新增廣鏈。開始給 標 ，檢查 ，給 標 ，檢查 ：在弧 上，因為 （見圖7-21），故該弧已飽和，標號無法進行下去。在弧 上，因為 ，又有所以給 標 ，檢查 ： 在弧 上，因為 ，又有 所以給 標 ，檢查 ：在弧 上，因為 ，又有，所以給 標 .于是又得到一條增廣鏈 (見

42、圖7-22) 進行調(diào)整： 這時 。調(diào)整結(jié)果如圖9.28所示。再重新標號求新的增廣鏈. 開始給 標 ，檢查 ，給 標 。檢查 ，給 標 ，檢查 ，給 標 ，檢查 ，因 已是飽和?。ㄒ妶D7-22）。標號無法進行。但在弧 上， .又有，所以給 標 .于是又得到一條增廣鏈：.再進行調(diào)整（見圖7-23）. 再重新進行標號求新的增廣鏈： 開始給 標（0，+ ），檢查 ，給 標 .檢查 ：這時弧 均已飽和。而在弧 上，因 ，又有所以給 標 ，表明弧 為后向弧.檢查 ，給 標 。檢查 ，給 標 。于是又得到一條增廣鏈： .再進行調(diào)整（見圖7-24）。 再重新進行標號求新的增廣鏈： 開始給 標(0,+)，檢查

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

44、 。再檢查 ，如前所述，標號也無法進行。至此已求得最大流。我們將最大流 表示在圖7-27中。最大流量為 與此同時，可找到最小截集 ，其中 為最后一輪已標號點的集合， 為未標號點的集合，即最小截量為 所以 。圖7-27由上述可見，用標號法找增廣鏈以求最大流的結(jié)果，同時也得到一個最小截集。最小截集的容量的大小影響總的運輸量的提高。因此，為提高總的運輸量，必須首先考慮增大最小截集中各弧的容量，提高它們的通過能力。反之，一旦最小截集中弧的通過能力降低，必然會使得運輸量減少。 前面討論都是對一個發(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