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

第七章 圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析（Graph Theory and Network Analysis），是近幾十年來運(yùn)籌學(xué)領(lǐng)域中發(fā)展迅速、而且十分靈活的一個(gè)分支。由于它對(duì)實(shí)際問題的描述，具有直觀性，故廣泛應(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ǎng)絡(luò)流問題等領(lǐng)域中應(yīng)用。重點(diǎn)講明方法的物理概念、基本概念及計(jì)算步驟。1 圖與網(wǎng)絡(luò)的基本概念 定義1 圖是由表示具體事物的點(diǎn)（頂點(diǎn)）的集合V=v1,v2,，vn和表示事物之間關(guān)系邊的集合E=e1,e2,，em所組成，且E中元素ei是由V中的無序元素對(duì)vi,vj表示，即ei=vi,vj，記為G=（V，E），并稱這類圖為無向圖。例如，圖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 = v4, v5 = v5 , v4.定義（）頂點(diǎn)數(shù)和邊數(shù)：圖G(,)中，中元素的個(gè)數(shù)稱為圖的頂點(diǎn)數(shù)，記作p(G)或簡記為p；中元素的個(gè)數(shù)稱做圖的邊數(shù)，記為q(G)，或簡記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)，簡稱鄰點(diǎn)；有公共端點(diǎn)的兩條邊稱為相鄰邊，簡稱鄰邊。（）多重邊與環(huán)：具有相同端點(diǎn)的邊稱為多重邊或平行邊；兩個(gè)端點(diǎn)落在一個(gè)頂點(diǎn)的邊稱為環(huán)。（）多重圖和簡單圖：含有多重邊的圖稱為多重圖；無環(huán)也無多重邊的圖稱為簡單圖。（）次：以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ù)的兩倍。即。定理是顯然的，因?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-1), 則稱此序列為一條聯(lián)結(jié)vil, eik,的鏈，記為=（vi1,vi2,，vik）,則稱點(diǎn)vi,vi3, vik-1為鏈的中間點(diǎn)。（）閉鏈與開鏈：若鏈中vi1vik 即始點(diǎn)與終點(diǎn)重合，則稱此鏈為閉鏈（圈）。否則稱之為開鏈。（）簡單鏈與初等鏈：若鏈中，若含的邊數(shù)均不相同，則稱之為簡單鏈；若鏈中，頂點(diǎn)vi1,vi2,，vik都不相同，則稱此鏈為初等鏈。除非特別交代，以后我們討論的均指初等鏈。例如，圖7-1中，1= ( v2,e2, v3,e3, v4,e6, v5) 是一條鏈，由于鏈1里所含的邊和點(diǎn)均不相同，故是一條初等鏈；而2= ( v1,e1, v2,e2, v3,e3, v4,e5,v2,e1,v1) 是一條閉鏈。定義（）回路：一條閉的鏈稱為回路。（）通路：一條開的初等鏈稱為通路。（）簡單鏈回路和初等回路；若回路中的邊都不相同，則稱為簡單回路；若回路中的邊和頂點(diǎn)都互不相同，則稱為初等回路或圈。定義一個(gè)圖的任意兩頂點(diǎn)之間，如果至少有一條通路將它們連接起來，則這個(gè)圖就稱為連通圖，否則稱為不連通圖。例如，圖7-1中，v1與v6沒有一條通路把它們連接起來，故此圖是不連通圖。本章以后討論的圖，除特別聲明外，都是指連通圖。 定義（）子圖：設(shè)11，122，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=(V , E)中，對(duì)任意一條邊eE,如果相應(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 , w(e8) = 3可見，賦權(quán)圖不僅指出各點(diǎn)之間的鄰接關(guān)系，而且也表示各點(diǎn)之間的數(shù)量關(guān)系。所以賦權(quán)圖在圖的理論及其應(yīng)用方面有著重要的地位。在很多實(shí)際問題中，事物之間的聯(lián)系是帶有方向性的。例如圖7-4所示。v1表示某一水系的發(fā)源地，v6表示這個(gè)水系的入?？?，圖中的箭頭則表示各支流的水流方向，圖7-4是水系流向圖?？梢妶D7-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 , A),ai=(vi,vj)表明vi和vj分別為ai邊的起點(diǎn)和終點(diǎn)，稱有方向的邊ai為?。ㄔ趫D中用帶有箭頭的線表示）。例如，圖7-4中，(v1,v2),(v1,v3),(v2,v5)都是A中的元素，A是弧的集合。在有向圖的討論中，類似無向圖，可以對(duì)多重邊、環(huán)、簡單圖、鏈等概念進(jìn)行定義，只是在無向圖中，鏈與路、閉鏈與回路概念是一致的，而在有向圖中，這兩個(gè)概念不能混為一談。概括地說，一條路必定是一條鏈。然而在有向圖中，一條鏈未必是一條路，只有在每相鄰的兩弧的公共結(jié)點(diǎn)是其中一條弧的終點(diǎn)，同時(shí)又是另一條弧的始點(diǎn)時(shí)，這條鏈才能叫做一條路。例如，圖7-4中，v1,(v1,v2),v2,(v2,v5),v5,(v5,v6),v6是一條鏈，也是一條路。而v1,(v1,v2),v2,(v2,v5),v5,(v3,v5),v3是一條鏈但不是一條路。我們還會(huì)碰到這樣一類有向圖（見圖7-5），這是某地區(qū)的交通運(yùn)輸分布、走向及相應(yīng)費(fèi)用示意圖。箭頭表示走向，箭頭旁邊的數(shù)字表示費(fèi)用，稱這類圖為賦權(quán)有向圖。定義9 設(shè)在有向圖G= ( V，A )中對(duì)任意一條弧aijA，如果相應(yīng)都有一個(gè)權(quán)值w(aij)則稱G為賦權(quán)有向圖。W(aij)稱為弧aij的權(quán)。簡記為wij（權(quán)可以表示距離、費(fèi)用和時(shí)間等）。 在實(shí)際工作中，有很多問題的可行解方案都可以通過一個(gè)賦權(quán)有向圖表示，例如：物流渠道的設(shè)計(jì)、物資運(yùn)輸路線的安排、裝卸設(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 樹及最小樹問題樹是圖論中一個(gè)重要概念，由于樹的模型簡單實(shí)用，它在企業(yè)管理、線路設(shè)計(jì)等方面都有很重要的應(yīng)用。2.1 樹與樹的性質(zhì)例1 例1 某企業(yè)的組織機(jī)構(gòu)如下所示如果用圖表示，見圖7-6是一個(gè)呈樹枝形狀的圖，“樹”的名稱由此而來。圖7-6定義10 一個(gè)無回路（圈）的連通無向圖稱為樹。 樹的性質(zhì)（1）必連通，但無回路（圈）；（2）n個(gè)頂點(diǎn)的樹必有n-1條邊；（3）樹中任意兩點(diǎn)間，恰有一條初等鏈；（4）樹連通，但去掉任意一條邊，必變?yōu)椴贿B通；（5）樹無回路（圈），但不相鄰頂點(diǎn)連一條邊，恰得一回路（圈）。2.2 支撐樹與最小樹定義11 設(shè)圖 是圖 的支撐子圖，如果是一棵樹 ，記 。則稱 是 的一棵支撐樹。 定理3 圖G有支撐樹的充分必要條件是圖G是連通的。證 必要性是顯然的。充分性：設(shè)G是連通圖。（i）如果G不含圈，由定義10可知，G本身就是一棵樹，從而G是它自身的支撐樹。（ii）如果G含圈，任取一圈，從圈中任意去掉一條邊，得到圖G的一個(gè)支撐子圖G1。如果G1不含圈，那么G1是G的一棵支撐樹（因?yàn)橐滓奊1是連通的）；如果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 v4 e7 v5 e6 v2去掉e7；取一圈v1 e1 v2 e6 v5 e8 v3 e2 v1去掉e6；如圖7-7所示，此圖是圖7-2(a)的一個(gè)支撐子圖，且為一棵樹（無圈），所以我們找到一棵支撐樹T1=V,E1，其中E1=e1,e4,e2,e8。7-2（a）不難發(fā)現(xiàn)，圖的支持樹不是唯一的，對(duì)于上例若這樣做：取一圈v1 e1 v2 e3 v3 e2 v1去掉e3；取一圈jv1 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去掉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è)過程，直到不能進(jìn)行下去為止。這是，由所有取出的邊所構(gòu)成的圖是圖G的一棵支撐樹。定義12 設(shè)T=(V,)是賦權(quán)圖G=(V,E)的一棵支撐樹，稱中全部邊上的權(quán)數(shù)之和為支撐樹T的權(quán)，記為w(T)。即 (7.2)如果支撐樹T*的權(quán)W(T*)是G的所有支撐樹的權(quán)中最小者，則稱T*是G的最小支撐樹，簡稱最小樹。即 (7.3)式中對(duì)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 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)成圈的邊為止。已選邊與頂點(diǎn)構(gòu)成的圖T就是所求最小樹。算法的具體步驟如下：第1步：令i=1，E0=（空集）。第2步：選一條邊eiEEi，且ei是使圖Gi=(V , Ei-1e)中不含圈的所有邊中權(quán)最小的邊e(eEEi)。如果這樣的邊不存在，則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都會(huì)與已選取邊構(gòu)成圈，故停止。得到與圖7-9一樣的結(jié)果。結(jié)果。3 最短路問題最短路問題是網(wǎng)絡(luò)分析中的一個(gè)基本問題，它不僅可以直接應(yīng)用于于解決生產(chǎn)實(shí)際的許多問題，若管道鋪設(shè)、線路安排、廠區(qū)布局等，而且經(jīng)常被作為一個(gè)基本工具，用于解決其它的優(yōu)化問題.定義 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)之和.記為 ，即 (7.4)又若P*是D圖中 到 的一條路，且滿足 (7.5)式中對(duì)D的所有從 到 的路P取最小，則稱P*為從 到 的最短路， 為 從 到的最短距離.在一個(gè)圖D=（V，A）中，求從 到 的最短路和最短距離的問題就稱為最短路問題. 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é)論不成立，設(shè)Q是從到的最短路，令P/是從沿Q到達(dá)，再從沿P到達(dá)的路，那么P/的權(quán)就比P的權(quán)小，這與P是從到的最短路矛盾.Dijkstra算法是沒有前公認(rèn)最好的方法，它適合所有的的情形.Dijkstra算法是一種標(biāo)記法，它的基本思路是從起點(diǎn) 出發(fā)，逐步向外探尋最短路，執(zhí)行過程中，給每一個(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)，并且把某一個(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)過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）開始時(shí)，令 （1）如果 ，算法終止.這時(shí)，對(duì)每個(gè) ；否則轉(zhuǎn)下一步。（2） 設(shè) 是剛獲得P標(biāo)號(hào)的點(diǎn).考察每個(gè)使 修改為即 （7.6）如果 則把T(vj)修改為 ，把 修改為 ；否則不修改.（3）令. （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.試問：從 出發(fā)，經(jīng)哪條路線到達(dá) 才能使總行程最短？用Dijkstra算法求解.解 開始時(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)(見圖7-11)：因,故把的臨時(shí)標(biāo)號(hào)修改為 ，這時(shí)。同理，得，.（見圖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)(見圖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)（見圖7-13）.因，故把的臨時(shí)標(biāo)號(hào)修改為同理得.在所有的T標(biāo)號(hào)中，最小的為()=5，于是令,=4.i=3:這時(shí)為剛獲得P標(biāo)號(hào)的點(diǎn).考察與相鄰的點(diǎ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)(見圖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)(見圖7-16)：因?yàn)?，故把的臨時(shí)標(biāo)號(hào)修改為 。這時(shí).這所有的臨時(shí)標(biāo)號(hào)中，最小的為，于是令,.i=6:這時(shí)為剛獲得P標(biāo)號(hào)的點(diǎn)，考察與相鄰的點(diǎ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)的最短路徑和最短距離.例如 就是從到最短路徑，距離為8.為了簡化計(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í)，也可以通過找該點(diǎn)的各個(gè)來源點(diǎn)的方法來實(shí)現(xiàn)，具體作法如下：開始時(shí)，給起點(diǎn)標(biāo)（0，0），即一般地，在給起點(diǎn)標(biāo)號(hào)時(shí)，要找出所有與有弧相聯(lián)且箭頭指向的各點(diǎn)（稱為的來源點(diǎn)）,不妨設(shè)是的來源點(diǎn)，其標(biāo)號(hào)為為弧的權(quán)值 ，則給點(diǎn)標(biāo)以(,l(),其中 根據(jù)別爾曼優(yōu)化原理，由始點(diǎn)到的最短路徑必是由到某個(gè)的最短路徑再加上弧(,)的權(quán)值。是到最短路徑的點(diǎn)，且是的來源點(diǎn)，顯然，是到最段路徑的長度,所以給每個(gè)頂點(diǎn)以標(biāo)號(hào)即可獲得最短路徑和長度的信息.下面，以圖7-10為例，說明標(biāo)號(hào)法的具體過程.首先給始點(diǎn)標(biāo)號(hào)，第一個(gè)標(biāo)號(hào)表示的是來源點(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)的來源是，且可由(7.8）計(jì)算即 得到的標(biāo)號(hào)（,3）.點(diǎn)的來源點(diǎn)有，計(jì)算 ,得到的標(biāo)號(hào)（,4）.的來源點(diǎn)有,計(jì)算 于是得到的標(biāo)號(hào)(,5).的來源有，,但還未標(biāo)號(hào)，而的來源點(diǎn),都已經(jīng)獲得標(biāo)號(hào)，故可計(jì)算 。因而得到的標(biāo)號(hào)(,6).計(jì)算 故的標(biāo)號(hào)為（,8）.的來源點(diǎn)是, ,計(jì)算 ，得到的標(biāo)號(hào)(,7).最后終點(diǎn)的來源點(diǎn)是,計(jì)算 ，所以在終點(diǎn)處標(biāo)上(,12)，標(biāo)號(hào)過程結(jié)束，見圖7-18所示.我們沿著第一個(gè)標(biāo)號(hào)，由終點(diǎn)反向跟蹤，很容易求得該網(wǎng)絡(luò)最短路徑，而終點(diǎn)的第二個(gè)標(biāo)號(hào)就是此最短路長度.上述標(biāo)號(hào)過程中，不僅可以求得到的最短路，而且從到(=2,3,4,5,6,7)的最短路都可求得.例如，到的最短路是，最短路長度為8.歸納上述例子，可以總結(jié)標(biāo)號(hào)法一般步驟如下：(1) (1) 始點(diǎn) 標(biāo)以（0.0）；(2) (2) 考慮需要標(biāo)號(hào)的頂點(diǎn) ，設(shè) 的來源點(diǎn) 均已獲得標(biāo)號(hào)，則 處應(yīng)標(biāo)以 ，其中 按（7.8）式確定.(3) (3) 重復(fù)第（2）步，直至終點(diǎn) 也獲得標(biāo)號(hào)為止， 就是最短路徑的長度.(4) (4) 確定最短路徑，從網(wǎng)絡(luò)終點(diǎn)的第一個(gè)標(biāo)號(hào)反向跟蹤，即得到網(wǎng)絡(luò)的最短路徑.以上例1是非負(fù)權(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)，標(biāo)號(hào)結(jié)果見圖7-20，反追蹤得到 至 的最短路為 .長度為3.4 網(wǎng)絡(luò)最大流問題網(wǎng)絡(luò)最大流問題是網(wǎng)絡(luò)的另一個(gè)基本問題。許多系統(tǒng)包含了流量問題。例如交通系統(tǒng)有車流量，金融系統(tǒng)有現(xiàn)金流，控制系統(tǒng)有信息流等。許多流問題主要是確定這類系統(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)輸線的最大通過能力 ，括號(hào)內(nèi)的數(shù)字表示該弧上的實(shí)際流 。現(xiàn)要求制定一個(gè)運(yùn)輸方案，使從 運(yùn)到 的產(chǎn)品數(shù)量最多?？尚辛髋c最大流在運(yùn)輸網(wǎng)絡(luò)的實(shí)際問題中，我們可以看出，對(duì)于流有兩個(gè)基本要求： 一是每條弧上的流量必須是非負(fù)的且不能超過該弧的最大通過能力（即該弧的容量）；二是起點(diǎn)發(fā)出的流的總和（稱為流量），必須等于終點(diǎn)接收的流的總和，且各中間點(diǎn)流入的流量之和必須等于從該點(diǎn)流出的流量之和，即流入的流量之和與流出的流量之和的差為零，也就是說各中間點(diǎn)只起轉(zhuǎn)運(yùn)作用，它既不產(chǎn)出新的物資，也不得截留過境的物資。因此有下面所謂的可行流的定義。定義14 對(duì)于給定的網(wǎng)絡(luò)D=（V,A,C）和給定的流 ，若 滿足下列條件：（1） （1） 容量限制條件：對(duì)每一條弧 ，有 (7.9)（2）平衡條件：對(duì)于中間點(diǎn)：流出量=流入量，即對(duì)于每一個(gè)i (is,t)，有 (7.10)對(duì)于出發(fā)帶點(diǎn) ，有 (7.11)對(duì)于收點(diǎn) ，有 (7.12)則稱 為一個(gè)可行流， 稱為這個(gè)可行流的流量。注意，我們這里所說的出發(fā)點(diǎn) 是指只有從 發(fā)出去的弧，而沒有指向 的??；收點(diǎn) 是指只有弧指向 ，而沒有從它的發(fā)出去的弧?？尚辛骺偸谴嬖诘?。例如令所有弧上的流 ，就得到一個(gè)可行流，（稱為零流），其流量 。如圖7-20中，每條弧上括號(hào)內(nèi)的數(shù)字給出的就是一個(gè)可行流 ，它顯然滿足定義中的條件（1）和（2）。其流量 。所謂網(wǎng)絡(luò)最大流問題就是求一個(gè)流 ，使得總流量 達(dá)到最大，并且滿足定義15中的條件（1）和（2），即max (7.13)網(wǎng)絡(luò)最大流問題是一個(gè)特殊的線性規(guī)劃問題。我們將會(huì)看到利用圖的特點(diǎn)，解決這個(gè)問題的方法較直線性規(guī)劃的一般方法要簡便和直觀的多。例2 寫出圖7-20所表示的網(wǎng)絡(luò)最大流問題的線性規(guī)劃模型。解 設(shè) ，則其線性規(guī)劃模型為 max 3. 增廣鏈 在網(wǎng)絡(luò)D=(V,A,C)中，若給定一個(gè)可行流 ，我們把網(wǎng)絡(luò)中使 的弧稱為飽和弧，使 的弧稱為非飽和弧。把 的弧稱為零流弧，把 的稱為非零流弧。如圖7-20中的弧都是非飽和弧，而弧 為零流弧。若 是網(wǎng)絡(luò)中聯(lián)結(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)于 的一條增廣鏈。如前面所說的鏈就是一條增廣鏈。因?yàn)槠渲?上的弧均非飽和，如(vs,v2) +,fs2=5<cs2=13；而-上的弧為非零流弧，如(v3,v2) -,f32=1>0，。顯然這樣的增廣鏈不止一條。4.截集與截量定義16 給定網(wǎng)絡(luò)D=(V,A,C)，若點(diǎn)集V被分割成兩個(gè)非空集合V1和V2，使得V=V1+V2,V1V2=(空集)，且vsV1,vtV2，則把始點(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)和(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便不存在路，所以直觀上說，截集是從vs到vt的必經(jīng)之路。定義17 在網(wǎng)絡(luò)D=(V,A,C)中，給定一個(gè)截集(V1,V2)，則把該截集中所有弧的容量之和，稱為這個(gè)截集的容量，簡稱為截量，記為c(V1,V2)，即 C(V1,V2)= (7.16)例如在上面我們所舉的兩個(gè)截集中，有 而 顯然，截集不同，其截量也不同。由于截集的個(gè)數(shù)是有限的，故其中必有一個(gè)截集的容量是最小的，稱為最小截集，也就是通常所說的“瓶頸”。不難證明，網(wǎng)絡(luò)D=(V,A,C)中，任何一個(gè)可行流f=fij的流量V(f)，都不會(huì)超過任一截集的容量，即 v( f ) c(V1,V2) (7.17)如果存在一個(gè)可行流f*=f*ij，網(wǎng)絡(luò)D=(V,A,C)中有一個(gè)截集 ，使得 (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)不難驗(yàn)證 是一個(gè)可行流，且有 這與f*是最大流的假定矛盾。再證充分性：即證明設(shè)D中不存在關(guān)于f*的增廣鏈，f*是最大流。用下面的方法定義：令 若 ，且有 ，則令 ；若 ，且有 ，則令 。因?yàn)椴淮嬖谥P(guān)于 的增廣鏈，故 記 ，于是得到一個(gè)截集(V*, )。顯然有 所以V(f*)=c ，于是f*必是最大流。定理得證。由上述證明中可見，若 是最大流，則網(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有無關(guān)于 的增廣鏈。如果有增廣鏈，則可以按定理4前半部分證明中的辦法，由公式(7.19)求出調(diào)整量Q，再按式（7.20）的方法求出新的可行流。如果流有增廣鏈，則得到最大流。而根據(jù)定理4后半部分證明中定義 的辦法，可以根據(jù)vt是否屬于 來判斷D中有無關(guān)于f的增廣鏈。在實(shí)際計(jì)算時(shí)，我們是用給頂點(diǎn)標(biāo)號(hào)的方法來定義 的，在標(biāo)號(hào)過程中，有標(biāo)號(hào)的頂點(diǎn)表示是 中的點(diǎn)，沒有標(biāo)號(hào)的點(diǎn)表示不是 中的點(diǎn)。一旦有了標(biāo)號(hào)，就表明找到一條從vs到vt的增廣鏈；如果標(biāo)號(hào)過程無法進(jìn)行下去，而vt尚未標(biāo)號(hào)，則說明不存在從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ò)中沒有給定 ，則可以設(shè) 是零流），經(jīng)過標(biāo)號(hào)過程與調(diào)整過程。1） 1） 標(biāo)號(hào)過程在這個(gè)過程中，網(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)表明它的標(biāo)號(hào)是從哪一點(diǎn)得到的，以便找出增廣鏈；第二個(gè)標(biāo)號(hào)是為確定增廣鏈的調(diào)整量用的。標(biāo)號(hào)過程開始，總先給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)而已檢查過的點(diǎn)，重復(fù)上述步驟，一旦 被標(biāo)上號(hào)，表明得到一條從 到 的增廣鏈 ，轉(zhuǎn)入調(diào)整過程。若所有標(biāo)號(hào)都是已檢查過，而標(biāo)號(hào)過程進(jìn)行不下去時(shí)，則算法結(jié)束，這時(shí)的可行流就是最大流。2） 2 調(diào)整過程首先按 及其它點(diǎn)的第一個(gè)標(biāo)號(hào)，利用“反向追蹤”的辦法，找出增廣鏈。例如設(shè)vt的第一個(gè)標(biāo)號(hào)為 （或 ），則弧 （或相應(yīng)地 ）是上的弧。接下來檢查 的第一個(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)過程。下面，以例題說明此算法求解過程。例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,+)，即 檢查 ：在弧 上，因?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)過號(hào) ，這里又給 標(biāo) ，它們分別表示兩條不同的路線，這里不存在修改標(biāo)號(hào)的問題（與最短路不同）。因?yàn)槲覀兊哪繕?biāo)是盡快找出一條從vs到vt的增廣鏈，即盡快使終點(diǎn)vt獲得標(biāo)號(hào)，所以不必在中途過多停留。也就是說在對(duì)已標(biāo)號(hào)點(diǎn)vi進(jìn)行檢查時(shí)，每次只檢查一個(gè)相鄰點(diǎn)vj（不論前向弧或后向弧均可），再給標(biāo)號(hào)即可，而不必檢查所有與vi相鄰的點(diǎn)。事實(shí)上，其余的相鄰點(diǎn)也不會(huì)漏掉，因?yàn)橐院筮€要通過檢查這些點(diǎn)來找出新的增廣鏈。以下我們就按這種思路進(jìn)行。檢查： 在弧 上，因?yàn)?，又有.所以給 標(biāo) .至此，終點(diǎn) 已獲得標(biāo)號(hào)，于是找出一條 從到 的增廣鏈。再由標(biāo)號(hào)的第一部分用反向追蹤法找出路線，即 （見圖7-21）。進(jìn)行調(diào)查：這時(shí)的調(diào)整量 .再按公式（7.20）調(diào)整。由于 上各弧均為前向弧，故得 ， ， .（見圖7-21）.其余的 不變.對(duì)這個(gè)新的可行流再進(jìn)入標(biāo)號(hào)過程，尋找新增廣鏈。開始給 標(biāo) ，檢查 ，給 標(biāo) ，檢查 ：在弧 上，因?yàn)?（見圖7-21），故該弧已飽和，標(biāo)號(hào)無法進(jìn)行下去。在弧 上，因?yàn)?，又有所以給 標(biāo) ，檢查 ： <!endif>在弧 上，因?yàn)?，又有 所以給 標(biāo) ，檢查 ：在弧 上，因?yàn)?，又有，所以給 標(biāo) .于是又得到一條增廣鏈 (見圖7-22) 進(jìn)行調(diào)整： 這時(shí) 。調(diào)整結(jié)果如圖9.28所示。再重新標(biāo)號(hào)求新的增廣鏈. 開始給 標(biāo) ，檢查 ，給 標(biāo) 。檢查 ，給 標(biāo) ，檢查 ，給 標(biāo) ，檢查 ，因 已是飽和?。ㄒ妶D7-22）。標(biāo)號(hào)無法進(jìn)行。但在弧 上， .又有，所以給 標(biāo) .于是又得到一條增廣鏈：.再進(jìn)行調(diào)整（見圖7-23）. 再重新進(jìn)行標(biāo)號(hào)求新的增廣鏈： 開始給 標(biāo)（0，+ ），檢查 ，給 標(biāo) .檢查 ：這時(shí)弧 均已飽和。而在弧 上，因 ，又有所以給 標(biāo) ，表明弧 為后向弧.檢查 ，給 標(biāo) 。檢查 ，給 標(biāo) 。于是又得到一條增廣鏈： .再進(jìn)行調(diào)整（見圖7-24）。 再重新進(jìn)行標(biāo)號(hào)求新的增廣鏈： 開始給 標(biāo)(0,+)，檢查 ，給 標(biāo) 。檢查 ，這時(shí) 和 均為前向弧，都已飽和，弧 為后向弧，且為零流弧 。故標(biāo)號(hào)無法進(jìn)行。但在弧 上因?yàn)?。又有.所以給 標(biāo) .檢查 ,給 標(biāo) 。檢查 ，因?yàn)?已飽和（見圖7-24）。而在弧 上，因?yàn)?，又有 .所以給 標(biāo) ，再檢查 ，給 標(biāo) 。于是又得到一條增廣鏈： .再進(jìn)行調(diào)整（見圖7-25）。再重新進(jìn)行標(biāo)號(hào)求新的增廣鏈。 開始給 標(biāo)(0,+)，檢查 ，給 標(biāo) 。檢查 ，因?yàn)?已飽和，而為弧 上標(biāo)號(hào)還可以繼續(xù)進(jìn)行，給 <!endif> 標(biāo) 。檢查 。給 標(biāo) 。于是又得到一條增廣鏈 再進(jìn)行調(diào)整（見圖7-26）。 再重新進(jìn)行標(biāo)號(hào)： 開始給 標(biāo)(0,+)，檢查 ：這時(shí)弧 已飽和。標(biāo)號(hào)無法進(jìn)行。而 還可以標(biāo)號(hào) 。再檢查 ，如前所述，標(biāo)號(hào)也無法進(jìn)行。至此已求得最大流。我們將最大流 表示在圖7-27中。最大流量為 與此同時(shí)，可找到最小截集 ，其中 為最后一輪已標(biāo)號(hào)點(diǎn)的集合， 為未標(biāo)號(hào)點(diǎn)的集合，即最小截量為 所以 。圖7-27由上述可見，用標(biāo)號(hào)法找增廣鏈以求最大流的結(jié)果，同時(shí)也得到一個(gè)最小截集。最小截集的容量的大小影響總的運(yùn)輸量的提高。因此，為提高總的運(yùn)輸量，必須首先考慮增大最小截集中各弧的容量，提高它們的通過能力。反之，一旦最小截集中弧的通過能力降低，必然會(huì)使得運(yùn)輸量減少。 前面討論都是對(duì)一個(gè)發(fā)點(diǎn)、一個(gè)收點(diǎn)的網(wǎng)絡(luò)最大流問題。對(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)，也令這些弧的容量為或某一具體值。這樣，原來的發(fā)點(diǎn) 與收點(diǎn) 都變成了轉(zhuǎn)運(yùn)點(diǎ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ò)，見圖7-29所示。 圖7-29