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

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

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

2、關(guān)系邊的集合E=｛e1,e2,…，em｝所組成，且E中元素ei是由V中的無(wú)序元素對(duì)[vi,vj]表示，即ei=[vi,vj]，記為G=（V，E），并稱這類圖為無(wú)向圖。 例如，圖7-1中，有８條邊，６個(gè)頂點(diǎn)，即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]. 定義２　 （１）頂點(diǎn)數(shù)和邊數(shù)：圖G(Ｖ,Ｅ)中，Ｖ中元素的個(gè)數(shù)稱為圖Ｇ的頂點(diǎn)數(shù)，記作p(G)或簡(jiǎn)記為p；Ｅ中元素的個(gè)數(shù)稱做圖Ｇ的邊數(shù)，記為q(G)，或簡(jiǎn)記q。 （２）端點(diǎn)和關(guān)聯(lián)邊：若ei=[vi,vj]∈Ｅ，則稱點(diǎn)vi,vj是邊ei的端點(diǎn)，邊ei是點(diǎn)vi和vj的關(guān)聯(lián)邊。 （３）相鄰點(diǎn)和相鄰邊：同一條邊的兩個(gè)端點(diǎn)稱為相鄰點(diǎn)，簡(jiǎn)稱鄰點(diǎn)；有公共端點(diǎn)的兩條邊稱為相鄰邊，簡(jiǎn)稱鄰邊。 （４）多重邊與環(huán)：具有相同端點(diǎn)的邊稱為多重邊或平行邊；兩個(gè)端點(diǎn)落在一個(gè)頂點(diǎn)的邊稱為環(huán)。 （５）多重圖和簡(jiǎn)單圖：含有多重邊的圖稱為多重圖；無(wú)環(huán)也無(wú)多重邊的圖稱為簡(jiǎn)單

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

5、。即 。 定理１是顯然的，因?yàn)樵谟?jì)算各點(diǎn)的次時(shí)，每條邊都計(jì)算兩次，于是圖Ｇ中全部頂點(diǎn)的次之和就是邊數(shù)的２倍。 定理２　任一圖Ｇ＝（Ｖ，Ｅ）種，奇點(diǎn)的個(gè)數(shù)為偶數(shù)。 證　設(shè)Ｖ１，Ｖ２分別是Ｇ中奇點(diǎn)和偶點(diǎn)的集合，由定理１可知 　　　　　　　　 （7.１） 因?yàn)?是偶數(shù)，而 也是偶數(shù)，故 也必是偶數(shù)，由于偶數(shù)個(gè)奇數(shù)才能導(dǎo)致偶數(shù)，所以有奇點(diǎn)的個(gè)數(shù)必須為偶數(shù)。 定義３ ?。ǎ保╂溤谝粋€(gè)圖Ｇ＝（Ｖ，Ｅ）中，一個(gè)由點(diǎn)與邊構(gòu)成的交錯(cuò)序列（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）,則稱點(diǎn)vi２,vi3,…, vik-1為鏈的中間點(diǎn)。 （２）閉鏈與開(kāi)鏈：若鏈μ中vi1＝vik 即始點(diǎn)與終點(diǎn)重合，則稱此鏈為閉鏈（圈）。否則稱之為開(kāi)鏈。 （３）簡(jiǎn)單鏈與初等鏈：若鏈μ中，若含的邊數(shù)均不相同，則稱之為簡(jiǎn)單鏈；若鏈μ中，頂點(diǎn)vi1,vi2,…，vik都不相同，則稱此鏈為初等鏈。除非特別交代，以后我們討論的均指初等鏈。 例如，圖7-1中，μ1= ( v2,e2, v3,e3, v4,e6, v5) 是一條鏈，由于鏈μ1里所含的邊和點(diǎn)均不相同，故是一條初等鏈；而μ2= ( v1,e

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

8、Ｅ2｝如果Ｖ1 V2，又Ｅ1 E2,則稱Ｇ1為G2的子圖。 （２）真子集：若V1 V2,E1 E2即G1中不包含G2中所有的頂點(diǎn)和邊，則稱G1是G2的真子圖。 （３）部分圖：若V1=V2,E1 E2,即Ｇ1中不包含G2中所有的邊，則稱G1是G2的一個(gè)部分圖。 （４）支撐子圖：若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)中，對(duì)任意一條邊e∈E,如果相應(yīng)都有一個(gè)權(quán)值w(e)，則稱G為賦權(quán)圖。w(e) 稱為邊e的權(quán)。 圖7-2是一個(gè)賦權(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 可見(jiàn)，賦權(quán)圖不僅指出各點(diǎn)之間的鄰接關(guān)系，而且也表示各點(diǎn)之間的數(shù)量關(guān)系。所以賦權(quán)圖在圖的理論及其應(yīng)用方面有著重要的地位。 在很多實(shí)際問(wèn)題中，事物之間的聯(lián)系是帶有方向性的。例如圖7-4所示。v1表示某一水系的發(fā)源地，v6表示這個(gè)水系的入海口，圖中的箭頭則表示各支流的水流方向，圖7-4是水系流向圖。 可見(jiàn)圖7-4中的邊是有方向的，稱這類圖為有向圖。 定義8 設(shè)V=｛v1,v2, …，vn｝是由n個(gè)頂點(diǎn)組成的非空集合，A=｛a1,a2,…，am｝是由m條邊組成的集合，且有A中元素ai是V中一個(gè)有序元素對(duì)(vi,vj)，則稱V和A構(gòu)成一個(gè)有向圖，記作G= (V

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

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

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

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

15、從圈中任意去掉一條邊，得到圖G的一個(gè)支撐子圖G1。如果G1不含圈，那么G1是G的一棵支撐樹（因?yàn)橐滓?jiàn)G1是連通的）；如果G1仍含圈，那么從G1中任取一個(gè)圈，從圈中再任意去掉一條邊，得到圖G的一個(gè)支撐子圖G2，如此重復(fù)，最終可以得到G的一個(gè)支撐子圖Gk，它不含圈，則Gk是圖G的一棵支撐樹。 由以上充分性的證明中，提供了一個(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)的一個(gè)支撐子圖，且為一棵樹（無(wú)圈），所以我們找到一棵支撐樹T1=｛V,E1｝，其中E1=｛e1,e4,e2,e8｝。 7-2（a） 不難發(fā)現(xiàn)，圖的支持樹不是唯一的，對(duì)于上例若這樣做： 取一圈｛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è)過(guò)程，直到不能進(jìn)行下去為止。這是，由所有取出的邊所構(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的最小支撐樹，簡(jiǎn)稱最小樹。即 (7.3) 式中對(duì)G的所有支撐樹T取最小。 求最小樹通常用以下兩種方法。 (1).破圈法：在給定連通圖G中，任取一圈，去掉一條最大權(quán)邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條邊），在余圖中（是圖G的支撐子圖）任取一圈，去掉一條最大權(quán)邊，重復(fù)下去，直到余圖中無(wú)圈為止，即可得到圖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、邊為止。已選邊與頂點(diǎn)構(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都會(huì)與已選取邊構(gòu)成圈，故停止。得到與圖7-9一樣的結(jié)果。 結(jié)果。 3 最短路問(wèn)題 最短路問(wèn)題是網(wǎng)絡(luò)分析中的一個(gè)基本問(wèn)題，它不僅可以直接應(yīng)用于于解決生產(chǎn)實(shí)際的許多問(wèn)題，若管道鋪設(shè)、線路安排、廠區(qū)布局等，而且經(jīng)常被作為一個(gè)基本工具，用于解決其它的優(yōu)化問(wèn)題. 定義 13 給定一個(gè)賦權(quán)有向圖D = (V,A)，記D中每一條弧 上的權(quán)為 。給定D中一個(gè)起點(diǎn) 和 終點(diǎn)，設(shè)P是D中從 到 的一條路.則定義路P的權(quán)是P中所有弧的權(quán)之和.記為 ，即

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

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

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

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

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

27、小的為()=5，于是令 ,=4. i=3: 這時(shí)為剛獲得P標(biāo)號(hào)的點(diǎn).考察與相鄰的點(diǎn)(見(jiàn)圖7-14). 因?yàn)?。故把的臨時(shí)標(biāo)號(hào)修改為 . 這時(shí)的臨時(shí)標(biāo)號(hào)不修改,故=3,同理得 在所有的臨時(shí)標(biāo)號(hào)中,最小的為, i=4: 這時(shí)為剛獲得P標(biāo)號(hào)的點(diǎn),考察與相鄰的點(diǎn)(見(jiàn)圖7-15): 因?yàn)楣拾训呐R時(shí)標(biāo)號(hào)修改為 . 這時(shí)，同理得 . 在所有的臨時(shí)標(biāo)號(hào)中，最小的為，于是令，。 i=5: 這時(shí)為剛獲得P標(biāo)號(hào)的點(diǎn)，考察與相鄰的點(diǎn)(見(jiàn)圖7-16)： 因?yàn)椋拾训呐R時(shí)標(biāo)號(hào)修改為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

49、)，即 檢查 ： 在弧 上，因?yàn)?，又有 ,所以給 標(biāo) ； 在弧上 ，因?yàn)?，又有 ,所以給 標(biāo) 。 檢查 ： 在弧上 ，因?yàn)?，又有 ,所以給 標(biāo) ； 在弧上 ，因?yàn)?，又有 ,所以給 標(biāo) ； 在弧 上，因?yàn)?，又有 ,所以給V3標(biāo) 。 因?yàn)榍懊嬉呀ov3標(biāo)過(guò)號(hào) ，這里又給 標(biāo) ，它們分別表示兩條不同的路線，這里不存在修改標(biāo)號(hào)的問(wèn)題（與最短路不同）。因?yàn)槲覀兊哪繕?biāo)是盡快找出一條從vs到vt的增廣鏈，即盡快使終點(diǎn)vt獲得標(biāo)號(hào)，所以不必在中途過(guò)多停留。也就是說(shuō)在對(duì)已標(biāo)號(hào)點(diǎn)vi進(jìn)行檢查時(shí)，每次只檢查一個(gè)相鄰點(diǎn)vj（不論前向弧或后向弧均可），再給標(biāo)號(hào)即可，而不必檢查所有與v

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

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

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

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

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

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