第5章圖與網(wǎng)絡(luò)

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

圖論的基本概念

最小支撐樹

最短路問題

最大流問題

網(wǎng)絡(luò)計(jì)劃2一、引言

圖論是由瑞士數(shù)學(xué)家歐拉（Euler）于1736年創(chuàng)始的，當(dāng)時(shí)有一個(gè)世界難題，叫“哥尼斯堡七橋問題”。哥尼斯堡城中有一條河，叫普雷格爾河，河中有兩個(gè)島，河上有七座橋，如圖所示。當(dāng)時(shí)那里的居民熱衷于這樣的問題：一個(gè)散步者能否走過七座橋，但每座橋只走過一次，最后回到出發(fā)點(diǎn)。5.1圖論的基本概念A(yù)BCD3歐拉用A、B、C、D四點(diǎn)表示河的兩岸和小島，用兩點(diǎn)間的聯(lián)線表示橋，如右下圖所示，該問題可歸結(jié)為：能否從某一點(diǎn)出發(fā)，一筆畫出這個(gè)圖形，最后回到出發(fā)點(diǎn)而不重復(fù)？即一筆畫問題。

ACBDBCDA歐拉在1786年發(fā)表了題為“依據(jù)幾何位置的解題方法”的論文，解決了著名的哥尼斯堡七橋問題．歐拉證明了上述圖形一筆劃是不可能的，因?yàn)閳D中每一個(gè)點(diǎn)都只和奇數(shù)條線相關(guān)聯(lián)．

他的結(jié)論是：圖形能一筆畫的充要條件是圖形的奇頂點(diǎn)（連接奇數(shù)條線的頂點(diǎn)）的個(gè)數(shù)為零4二、圖的定義

在自然界和人類的實(shí)際生活中，常用點(diǎn)和點(diǎn)與點(diǎn)之間的聯(lián)線所構(gòu)成的圖，來反映某些研究對(duì)象和對(duì)象之間的某種特定的關(guān)系。如：為了反映城市之間有沒有航班，我們可用右圖表示。甲城與乙城，乙城與丙城有飛機(jī)到達(dá)，而甲、丙兩城沒有直飛航班。對(duì)于工作分配問題，我們可能用點(diǎn)表示工人與需要完成的工作，點(diǎn)間連線表示每個(gè)工人可以勝任哪些工作如右圖所示。

甲乙丙甲乙丙工人ABC工作Ｄ5圖的定義：所謂圖，就是頂點(diǎn)（簡(jiǎn)稱點(diǎn)）和一些點(diǎn)之間的連線（不帶箭頭或者帶箭頭）所組成的集合。為區(qū)別起見，不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的，則稱之為無向圖（也簡(jiǎn)稱為圖），記作，其中V表示圖G的非空的頂點(diǎn)集合，E表示G的邊的集合。連接頂點(diǎn)和的邊記為；如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，則稱之為有向圖，記作，其中V仍表示有向圖D的非空的頂點(diǎn)集合，A表示D的弧集合。一條方向從指向的弧記為。6

如無向圖：Ｖ1Ｖ4Ｖ3Ｖ2e1e5e6e4e3e2e77如有向圖：Ｖ1Ｖ3Ｖ2Ｖ4Ｖ5Ｖ6Ｖ7a1a2a3a4a6a5a7a8a9a10a118三、基本概念點(diǎn)和邊的相關(guān)概念：（1）頂點(diǎn)數(shù)和邊數(shù)：給定圖，集合V的元素的個(gè)數(shù)，稱為圖G的頂點(diǎn)數(shù)，記作；集合E的元素的個(gè)數(shù)，稱為圖G的邊數(shù)，記作。（2）端點(diǎn)和關(guān)聯(lián)邊：若，則稱頂點(diǎn)是的端點(diǎn)，是的關(guān)聯(lián)邊。（3）相鄰點(diǎn)和相鄰邊：若頂點(diǎn)和與同一條邊相關(guān)聯(lián)，則稱點(diǎn)和為相鄰點(diǎn)；若邊和有一個(gè)共同的端點(diǎn)，則稱其為相鄰邊。（4）環(huán)和多重邊：若邊的兩個(gè)端點(diǎn)屬同一頂點(diǎn)，則稱該邊為環(huán)；若兩個(gè)端點(diǎn)之間多于一條邊，則稱這些邊為多重邊。（5）多重圖和簡(jiǎn)單圖：含多重邊的圖稱為多重圖，無環(huán)也無多重邊的圖稱為簡(jiǎn)單圖。9（6）次和孤立點(diǎn)：與點(diǎn)關(guān)聯(lián)的邊的條數(shù)，稱為點(diǎn)的次，記作；次數(shù)為零的點(diǎn)為孤立點(diǎn)。（7）懸掛點(diǎn)和懸掛邊：次為1的點(diǎn)稱為懸掛點(diǎn)；懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸掛邊。（8）奇點(diǎn)和偶點(diǎn)：次為奇數(shù)的點(diǎn)稱為奇點(diǎn)；次為偶數(shù)的點(diǎn)為偶點(diǎn)。定理1圖中，所有頂點(diǎn)的次之和等于所有邊數(shù)的2倍，即鏈的概念：（1）給定一個(gè)圖，一個(gè)點(diǎn)、邊的交錯(cuò)序列，如果滿足。這樣的序列稱為一條聯(lián)結(jié)和的鏈，記作。10（2）開鏈和閉鏈：如果，則該鏈稱為開鏈；如果，則該鏈稱為閉鏈（或稱為圈）。（3）簡(jiǎn)單鏈和初等鏈：如鏈內(nèi)所含的邊均不相同，稱之為簡(jiǎn)單鏈；如鏈內(nèi)所含的點(diǎn)均不相同，稱之為初等鏈。如：是簡(jiǎn)單鏈，是初等鏈，是初等圈，是簡(jiǎn)單圈，Ｖ1Ｖ2Ｖ4Ｖ3Ｖ5Ｖ6Ｖ7e1e2e3e8e4e7e6e5e911（4）基礎(chǔ)圖和路：若把一個(gè)有向圖D的方向去掉，即每一弧都用相應(yīng)得無向邊代替，所得到的一個(gè)無向圖，稱為該有向圖D的基礎(chǔ)圖，記為G（D）；基礎(chǔ)圖G（D）中的鏈（或圈）恢復(fù)無向邊的方向后，稱為有向圖D的鏈（或圈）。若交替序列是有向圖G的一條鏈，且滿足，即鏈中每一條弧的箭頭方向都和鏈的方向一致，那么該鏈稱為有向圖D的一條從到的路，簡(jiǎn)記。又若，則稱μ為圖D中的回路。對(duì)無向圖G來說，鏈和路（閉鏈和回路）這兩個(gè)概念是一致的。但有向圖D中的鏈不一定是路，因?yàn)橛邢驁D的鏈可能存在和鏈的方向不一致的反向弧，但按定義，它們?nèi)允怯邢驁D中的鏈。12連通圖和網(wǎng)絡(luò)圖的概念：（1）連通圖：在一個(gè)圖G中，若任意兩點(diǎn)之間至少存在一條鏈，則稱該圖G為連通圖，否則稱之為不連通圖。如：Ｖ3Ｖ6Ｖ5Ｖ2Ｖ4Ｖ1a2a3a1a4a5左圖為不連通圖。因?yàn)樵陧旤c(diǎn)Ｖ1，V2，V3，V4和V5，V6之間不存在任何一條鏈將它們相連接。Ｖ1Ｖ2Ｖ3Ｖ4Ｖ5右圖為有向連通圖13（2）連通分圖：若G是不連通圖，那么它的每一個(gè)連通部分稱為圖G的連通分圖。（3）子圖和支撐子圖：設(shè)圖，若有，使，則稱是的子圖；若，則稱是的支撐子圖。如，以下右圖是左圖的支撐子圖。v1v3v5v4e5v3v5v4v2e2e1e3e4e5e6e7e8v2e1e3e4v1e614（4）賦權(quán)圖：設(shè)圖，若對(duì)其邊集E定義了一個(gè)實(shí)值函數(shù)，則稱該圖為一個(gè)賦權(quán)圖。記作。稱為邊的權(quán)。如某工廠內(nèi)連接六個(gè)車間的道路網(wǎng)如入所示，已知每條路長，要求沿道路架設(shè)連接六個(gè)車間的電話線路，使電話總長最短。Ｖ1Ｖ2Ｖ3Ｖ4Ｖ5Ｖ6652715344左圖為一賦權(quán)圖最優(yōu)解：如紅線所示，電話總長15個(gè)單位。紅線所示為圖Ｇ的最小支撐樹15（5）網(wǎng)絡(luò)圖，若為一賦權(quán)圖，并在其頂點(diǎn)集合V中指定了起點(diǎn)（或稱發(fā)點(diǎn)）和終點(diǎn)（或稱收點(diǎn)），其余的點(diǎn)為中間點(diǎn)，這樣的賦權(quán)圖稱為網(wǎng)絡(luò)圖（簡(jiǎn)稱網(wǎng)絡(luò)）。記作。網(wǎng)絡(luò)一般是連通的賦權(quán)圖。

若一個(gè)網(wǎng)絡(luò)圖中的每條邊都是有向的弧，則稱之為有向網(wǎng)絡(luò)，記作

16四、圖的矩陣表示距離矩陣：設(shè)圖，為邊上的權(quán)，表示點(diǎn)到之間的距離，則可構(gòu)造距離矩陣，其中如：以下無向賦權(quán)圖中的權(quán)表示點(diǎn)與點(diǎn)之間距離其他Ｖ1247635489Ｖ2Ｖ3Ｖ4Ｖ5或

對(duì)有向賦權(quán)圖，則定義時(shí)將改為。17鄰接矩陣：

設(shè)圖，則鄰接矩陣的元素可定義如下其他對(duì)有向賦權(quán)圖，則定義時(shí)將改為如Ｖ1Ｖ2Ｖ3Ｖ4Ｖ518一、樹及其性質(zhì)樹的定義：設(shè)，若G連通，并且沒有圈，則稱G為樹，記作。比如有六個(gè)頂點(diǎn)的樹有6種，5.2最小支撐樹··19定理2

以下關(guān)于樹T的六種描述是等價(jià)的，（1）無圈連通圖；（2）無圈，(即圖有條邊，是圖中的頂點(diǎn)數(shù))；（3）連通，；（4）無圈，但增加一條邊可得唯一一個(gè)圈；（5）連通，但舍棄一條邊則不連通；（6）每一對(duì)頂點(diǎn)之間有一條且僅有一條鏈。上述六個(gè)等價(jià)命題可以使用循環(huán)證明法，即由命題（1）推得命題（2），再由命題（2）推得命題（3），……，依次類推，最后由命題（6）回推到命題（1），完成以上推導(dǎo)過程即證明了六個(gè)命題是等價(jià)的。20二、圖的支撐樹支撐樹的定義：假設(shè)圖是圖的支撐子圖，如果圖是一個(gè)樹，則稱T是G的支撐樹。如下圖中，（b）圖是(a)圖的支撐樹定理3

圖G有支撐樹的充分必要條件是圖G是連通的V1V2V3V4V5V6V2V3V4V5V6（a）（b）21三、最小支撐樹定義設(shè)賦權(quán)圖，它的每條邊有非負(fù)權(quán)，是G的一個(gè)支撐樹，中所有邊的權(quán)之和如果，則稱是G的最小支撐樹。定理4

設(shè)賦權(quán)圖，若把E分割成兩個(gè)不相交的非空子集和，那么連接這兩個(gè)子集的最小邊一定包含在G的最小支撐樹內(nèi)。由定理4可以引出求最小支撐樹的方法22求最小支撐樹的方法。（1）避圈法。步驟如下：①從賦權(quán)圖G中任選一點(diǎn)，令，；②從連接和的邊中選擇權(quán)最小的邊，不妨假設(shè)為，由定理4，它必包含在最小支撐樹內(nèi)；③令，；④若，則停止計(jì)算，已選出的各條邊已構(gòu)成最小支撐樹，否則回到②。例1

某工廠聯(lián)結(jié)六個(gè)車間的道路網(wǎng)如下圖所示，已知每條道路長，要求沿道路架設(shè)聯(lián)結(jié)六個(gè)車間的電話網(wǎng)，使電話線的總長最短。V1V2V4V3V5V661557234423至此，停止計(jì)算，

V1V2V4V3V5V6615572344解：這是求最小支撐樹的問題，由避圈法的步驟，在圖G的六個(gè)頂點(diǎn)中任選其中一點(diǎn)作為S，比如選，則，聯(lián)結(jié)和一共有3條邊，取最短邊，并令，依次類推…

，最短電話線路的總長為15個(gè)單位。24（2）破圈法。步驟是：在圖中任取一個(gè)圈，從圈中除去權(quán)最大的一條邊（圈中存在兩條以上最大權(quán)的邊，可任選其中一條），在余下的支撐子圖中重復(fù)這個(gè)步驟，一直得到一個(gè)不含圈的支撐子圖為止，這時(shí)的圖就是原賦權(quán)圖的最小支撐樹。例2，用破圈法求例1中的賦權(quán)圖的最小支撐樹。V1V3V5V6615572344

，最短電話線路的總長為15個(gè)單位。25最短路問題表述：給定一個(gè)賦權(quán)圖，對(duì)每一邊相應(yīng)地有權(quán)，又有兩點(diǎn)，設(shè)Ｐ是Ｇ中從到的一條路，路Ｐ的權(quán)是Ｐ中所有邊的權(quán)之和，記為。最短路問題就是求從到的路中一條權(quán)最小的路Ｐ0，使上述定義中，若是有向賦權(quán)圖，則任一邊改為任一弧，其他相同。此時(shí)從到的路應(yīng)是沿弧的箭頭方向首尾相接的路。5.3最短路問題26一、Dijkstra算法

狄克斯拉算法是由Dijkstra于1959年提出來，用于求解指定兩點(diǎn)，cc之間的最短路，或從指定點(diǎn)到其余各點(diǎn)的最短路，目前被認(rèn)為是求情形下最短路問題的最好方法?；舅悸坊谝韵略恚喝簦惺菑牡降淖疃搪?，是Ｐ中的一個(gè)點(diǎn)，那么從到的最短路就是從沿Ｐ到的那條路。采用標(biāo)號(hào)法：Ｔ標(biāo)號(hào)與Ｐ標(biāo)號(hào)。Ｔ標(biāo)號(hào)為試探性標(biāo)號(hào)，Ｐ為永久性標(biāo)號(hào)。給點(diǎn)一個(gè)Ｐ標(biāo)號(hào)時(shí)，該標(biāo)號(hào)表示從到點(diǎn)的最短路權(quán)，點(diǎn)的標(biāo)號(hào)不再改變。給點(diǎn)一個(gè)Ｔ標(biāo)號(hào)時(shí)，Ｔ標(biāo)號(hào)表示從到點(diǎn)的最短路權(quán)的上界，是一種臨時(shí)標(biāo)號(hào)。凡沒有得到Ｐ標(biāo)號(hào)的點(diǎn)都有Ｔ標(biāo)號(hào)。算法每一步都把某一點(diǎn)的Ｔ標(biāo)號(hào)改為Ｐ標(biāo)號(hào)，當(dāng)終點(diǎn)得到Ｐ標(biāo)號(hào)時(shí)，全部計(jì)算結(jié)束。27Dijkstra算法基本步驟：⑴給以Ｐ標(biāo)號(hào)，其余各點(diǎn)均給Ｔ標(biāo)號(hào)，。⑵若點(diǎn)為得到Ｐ標(biāo)號(hào)的點(diǎn)，考慮且為Ｔ標(biāo)號(hào)。對(duì)的Ｔ標(biāo)號(hào)進(jìn)行如下的更改：⑶比較所有具有Ｔ標(biāo)號(hào)的點(diǎn)，若則把最小值對(duì)應(yīng)的點(diǎn)改為Ｐ標(biāo)號(hào)，即當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為Ｐ標(biāo)號(hào)。若全部點(diǎn)均為Ｐ標(biāo)號(hào)則停止。否則轉(zhuǎn)回⑵。步驟(3)，當(dāng)給頂點(diǎn)Ｐ標(biāo)號(hào)時(shí)，可以在圖的對(duì)應(yīng)頂點(diǎn)旁標(biāo)上一個(gè)記號(hào)（，），其中為從到的最短路上與鄰接的頂點(diǎn)，為從到的最短路長。的記號(hào)取（，０）28例2

用Dijkstra算法求圖中從的最短路12235535775１1４２３５６７解：⑴首先給以P標(biāo)號(hào)給其余所有點(diǎn)Ｔ標(biāo)號(hào)

(2)考察，由于且是Ｔ標(biāo)號(hào)點(diǎn)，所以修改Ｔ標(biāo)號(hào)為：(v1,0)在所有Ｔ標(biāo)號(hào)中，，于是給Ｐ標(biāo)號(hào)令，并標(biāo)上（，２）。(v1,2)2912235535775１1４２３５６７(v1,0)在所有Ｔ標(biāo)號(hào)中，最小，于是給Ｐ標(biāo)號(hào)令，并標(biāo)上（，3）。(3)考察，因且是Ｔ標(biāo)號(hào)，故修改對(duì)應(yīng)的Ｔ標(biāo)號(hào)：(v1,3)(v1,2)30(4)考察，因且是Ｔ標(biāo)號(hào)，故修改對(duì)應(yīng)的Ｔ標(biāo)號(hào)為：在所有Ｔ標(biāo)號(hào)中，最小，于是給Ｐ標(biāo)號(hào)令

，并標(biāo)上（，4）。12235535775１1４２３５６７(v1,0)(v1,3)(v2,4)(v1,2)31在所有Ｔ標(biāo)號(hào)中，最小，于是給Ｐ標(biāo)號(hào)令

，標(biāo)上（，7）。(5)考察，因且是Ｔ標(biāo)號(hào)，故修改對(duì)應(yīng)的Ｔ標(biāo)號(hào)為：12235535775１1４２３５６７(v1,0)(v1,3)(v2,4)(v3,7)(v1,2)32在所有Ｔ標(biāo)號(hào)中，最小，于是給Ｐ標(biāo)號(hào)令，標(biāo)上（，8）。12235535775１1４２３５６７(6)考察，因且是Ｔ標(biāo)號(hào)，故修改對(duì)應(yīng)的Ｔ標(biāo)號(hào)為：(v1,0)(v1,3)(v2,4)(v3,7)(v5,8)(v1,2)33(7)考察，因且是Ｔ標(biāo)號(hào)，故修改對(duì)應(yīng)的Ｔ標(biāo)號(hào)為：由于只剩最后一個(gè)Ｔ標(biāo)號(hào)，所以給Ｐ標(biāo)號(hào)。令，標(biāo)上（，13）。由于所有頂點(diǎn)都標(biāo)上了Ｔ標(biāo)號(hào)所以計(jì)算結(jié)束。(v６,13)從到的最短路：最短路長13.12235535775１1４２３５６７(v1,0)(v1,3)(v2,4)(v3,7)(v5,8)(v1,2)34例3

設(shè)備更新問題。某企業(yè)使用一臺(tái)設(shè)備，在每年年初，都要決定是否更新。若購置新設(shè)備，要付購買費(fèi)；若繼續(xù)使用舊設(shè)備，則支付維修費(fèi)用。試制定一個(gè)5年更新計(jì)劃，使總支出最少。若已知設(shè)備在各年的購買費(fèi)及不同機(jī)器役齡時(shí)的殘值和維修費(fèi)，如下表所示：第1年第2年第3年第4年第5年購買費(fèi)1112131414機(jī)器役齡0-11-22-33-44-5維修費(fèi)5681118殘值4321035解：把這個(gè)問題化為最短路問題用表示第i年初購進(jìn)一臺(tái)新設(shè)備，虛設(shè)一個(gè)點(diǎn)表示第5年底；用弧表示第i年初購的設(shè)備一直使用到第j年年初（第j-1年年低）；弧旁的數(shù)字表示第i年初購進(jìn)設(shè)備，一直使用到第j年初所需支付的購買、維修的全部費(fèi)用。這樣設(shè)備更新問題就變?yōu)椋呵髲牡降淖疃搪?第1年第2年第3年第4年第5年購買費(fèi)1112131414機(jī)器役齡0-11-22-33-44-5維修費(fèi)5681118殘值4321036第1年第2年第3年第4年第5年購買費(fèi)1112131414機(jī)器役齡0-11-22-33-44-5維修費(fèi)5681118殘值43210194059121314152130152841292220123456購買維修殘值費(fèi)用１→２１１５４１２１→３１１１１３１９１→４１１１９２２８１→５１１３０１４０１→６１１４８０５９２→３１２５４１３２→４１２１１３２０２→５１２１９２２９２→６１２３０１４１３→４１３５４１４３→５１３１１３２１３→６１３１９２３０４→５１４５４１５４→６１４１１３２２５→６１４５４１５37

計(jì)算結(jié)果表明為最短路，路長為49。即在第1年、第3年初各購買一臺(tái)新設(shè)備為最優(yōu)決策，這時(shí)5年的總費(fèi)用為49。194059121314152130152841292220123456(v1,0)(v1,12)(v1,19)(v1,28)(v3,40)(v3,49)ＴＴＴＴＴＴV1０V2∞12V3∞1919V4∞282828V5∞40404040V6∞5953494949相鄰點(diǎn)V1V1V1

V1V3V3Ｐ標(biāo)號(hào)38右圖是輸油管道網(wǎng)，為起點(diǎn)，是終點(diǎn)，為中轉(zhuǎn)站，邊上的數(shù)表示該管道的最大輸油能力，問：（1）應(yīng)如何安排各管道輸油量，才能使從到的總輸油量最大？

最大流問題是網(wǎng)絡(luò)分析中一類應(yīng)用極為廣泛的問題。在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車流、貨物流；供水網(wǎng)絡(luò)中有水流；金融系統(tǒng)中有現(xiàn)金流；通訊系統(tǒng)中有信息流；等等。20世紀(jì)50年代Ford，F(xiàn)ulkerson建立的“網(wǎng)絡(luò)流理論”是網(wǎng)絡(luò)應(yīng)用的重要組成部分。5.4最大流問題254311２１４３Ｓt352（2）如果要增加管道網(wǎng)的最大輸油量，應(yīng)該優(yōu)先增加哪個(gè)管道的輸油能力?39一、基本概念網(wǎng)絡(luò)與流：我們已經(jīng)給出了網(wǎng)絡(luò)圖的概念，網(wǎng)絡(luò)圖是一種無向或有向賦權(quán)圖，在其頂點(diǎn)集合中指定了起點(diǎn)和終點(diǎn)，其余的點(diǎn)為中間點(diǎn)。在最大流問題中，我們所討論的網(wǎng)絡(luò)都是有向連通賦權(quán)圖，記作，稱V中的起點(diǎn)為發(fā)點(diǎn)，終點(diǎn)為收點(diǎn)，其余的點(diǎn)仍為中間點(diǎn)。對(duì)于每一個(gè)弧，對(duì)應(yīng)有一個(gè)權(quán)，稱為弧的容量，簡(jiǎn)記。所謂網(wǎng)絡(luò)上的流，是指定義在弧集合A上的一個(gè)函數(shù)，并稱為弧上的流量，簡(jiǎn)記作。40可行流：滿足下列條件的流成為可行流：①容量限制條件：每一弧②平衡條件：對(duì)于中間點(diǎn)，有對(duì)于發(fā)點(diǎn)，收點(diǎn)，有并稱為這個(gè)可行流的流量?？尚辛骺偸谴嬖诘模缌懔?，。

（2，1）（5，3）（4，3）（3，0）（1，1）（1，1）２１４３Ｓt（3，3）（5，1）（2，2）41最大流：所謂最大流問題，就是求一個(gè)流，使其流量達(dá)到最大，并且滿足以上容量限制條件和平衡條件。最大流問題是一個(gè)特殊的線性規(guī)劃問題．（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（3，3）（5，2）（2，2）42增廣鏈：若是網(wǎng)絡(luò)中聯(lián)結(jié)發(fā)點(diǎn)和收點(diǎn)的一條鏈，且鏈的方向是從到，則與鏈的方向一致的弧叫前向弧，表示前向弧的集合；與鏈的方向相反的弧叫后向弧，表示后向弧的集合。定義1

設(shè)是一個(gè)可行流，是從到的一條鏈，若滿足下列條件，則是可行流的一條增廣鏈：①

前向弧上，，即中每一弧是非飽和弧，②

后向弧上，，即中每一弧是非零流弧。定理5

可行流是最大流，當(dāng)且僅當(dāng)不存在關(guān)于的增廣鏈。43（2，1）（5，3）（4，3）（3，0）（1，1）（1，1）２１４３Ｓt（3，3）（5，1）（2，2）44二、Ford-Fulkerson算法福特－富克遜算法又稱尋求最大流的標(biāo)號(hào)法。前提是已有一個(gè)可行流，標(biāo)號(hào)算法分2步。第1步：給頂點(diǎn)的標(biāo)號(hào)過程。通過頂點(diǎn)的標(biāo)號(hào)來尋找增廣鏈；第2步是調(diào)整過程，沿增廣鏈調(diào)整ｆ以增加流量。⑴標(biāo)號(hào)過程每個(gè)頂點(diǎn)的標(biāo)號(hào)包含兩部分：第1部分表明它的標(biāo)號(hào)是從哪一個(gè)頂點(diǎn)得到，以便找出增廣鏈；第2部分是為確定增廣鏈的調(diào)整量用的。①給發(fā)點(diǎn)以標(biāo)號(hào)；②選擇一個(gè)已標(biāo)號(hào)的點(diǎn)，對(duì)于的所有未標(biāo)號(hào)的鄰接點(diǎn)，如果，且，令，并給以標(biāo)號(hào)；如果，且，令，并給以標(biāo)號(hào)。45重復(fù)上述步驟②，直到被標(biāo)上號(hào)或不再有頂點(diǎn)可標(biāo)號(hào)為止。如果得到標(biāo)號(hào)，說明存在增廣鏈，轉(zhuǎn)入調(diào)整過程；如果未獲得標(biāo)號(hào)，標(biāo)號(hào)過程已無法進(jìn)行時(shí)，說明ｆ已是最大流。⑵調(diào)整過程令其中調(diào)整量．調(diào)整后去掉所有標(biāo)號(hào)，對(duì)新的可行流重新進(jìn)行標(biāo)號(hào)過程。調(diào)整過程為：在增廣鏈的前向弧上加上調(diào)整量θ，后向弧上減去調(diào)整量θ，其他弧的流量不變．這樣可使總流量增加θ，即46找可行流ｆ給ＶS標(biāo)號(hào)(ＶS，＋∞)Ｖt是否已

標(biāo)號(hào)

是否存在已標(biāo)號(hào)但未檢查的點(diǎn)

倒向追蹤找出增廣鏈μ

令調(diào)整量求改進(jìn)的可行流不存在關(guān)于ｆ的增廣鏈ｆ即為最大流Ｖi已

標(biāo)號(hào),但未檢查．

對(duì)Ｖi

進(jìn)行檢查，并對(duì)Ｖj標(biāo)號(hào):

若，且，對(duì)Ｖj標(biāo)號(hào):

，若，且，對(duì)Ｖj標(biāo)號(hào):

，是否47例4

用標(biāo)號(hào)法求所示網(wǎng)絡(luò)圖的最大流?；∨缘臄?shù)是?；〔粷M足標(biāo)號(hào)條件．（2，2）（2，1）（5，3）（4，3）（3，3）（5，1）（3，0）（1，1）（1，1）解：經(jīng)檢查，網(wǎng)絡(luò)中的流是可行流，下面分析是否可以增加流量。（１）標(biāo)號(hào)過程：①先給標(biāo)號(hào)；②檢查，在弧上，所以

則的標(biāo)號(hào)２１４3Ｓt（ＶＳ,+∞)（ＶＳ,4)．弧不滿足標(biāo)號(hào)條件．③檢查，在弧上，所以則的標(biāo)號(hào)（－Ｖ１,１）48（Ｖ4,１）（2，2）（2，1）（5，3）（4，3）（3，3）（5，1）（3，0）（1，1）（1，1）④檢查，在弧上，

給標(biāo)號(hào)

２１４３Ｓt（ＶＳ,+∞)（ＶＳ,4)

在弧上．給標(biāo)號(hào)⑤檢查，在弧上，所以

,

給標(biāo)號(hào)．因已經(jīng)標(biāo)號(hào)，故進(jìn)入調(diào)整過程．（－Ｖ１,１）（Ｖ２,１）（－Ｖ2,１）49（5，1）（Ｖ4,１）（2，2）（2，1）（5，3）（4，3）（3，3）（3，0）（1，1）（1，1）２１４３Ｓt（ＶＳ,4)（－Ｖ１,１）（Ｖ２,１）（－Ｖ2,１）（ＶＳ,+∞)（2）調(diào)整過程：取定增廣鏈．前向弧上流量增加１，后向弧上流量減去１，其他不變，得可行流在進(jìn)入新的循環(huán)：①給標(biāo)號(hào)檢查給標(biāo)號(hào)檢查，標(biāo)號(hào)過程無法進(jìn)行下去．所以為最大流，（2，2）（3，3）（5，2）（ＶＳ,+∞)（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（ＶＳ,3)問題（1）：應(yīng)如何安排各管道輸油量，才能使從到的總輸油量最大？答：fs1=2、fs2=3、f13=2、f24=4、f32=1、f4t=4、f3t=1.（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（3，3）（5，2）（2，2）51截集與截量：設(shè)，我們把始點(diǎn)在Ｓ，終點(diǎn)在Ｔ中的所有弧構(gòu)成的集合，記為。定義１：設(shè)網(wǎng)絡(luò)，若點(diǎn)集Ｖ被剖分為兩個(gè)非空集合和，使，則把弧集稱為分離，的截集。截集是從到的必徑之道。定義2

給定一截集，把截集中所有弧的容量之和稱為這個(gè)截集的容量（或稱截量），記作任何一個(gè)可行流的流量都不會(huì)超過任一截量的容量，即若對(duì)于一個(gè)可行流，網(wǎng)絡(luò)中有一個(gè)截集，使則必是最大流，而必定是網(wǎng)絡(luò)的所有截集中容量最小的一個(gè)，稱為最小截量。52

最大流量最小截量定理：任一個(gè)網(wǎng)絡(luò)中，從到的最大流的流量等于分離，的最小截集的容量。

53由上述可見，用標(biāo)號(hào)法找增廣鏈找到最大流的同時(shí)，得到一個(gè)最小截集。最小截集的容量大小影響網(wǎng)絡(luò)最大流量。因此為提高總的輸送量，必須首先考慮改善最小截集中各弧的輸送能力。另一方面，一旦最小截集中弧的通過能力被降低，就會(huì)使總的輸送量減少。（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（ＶＳ,3)（ＶＳ,+∞)（3，3）（5，2）（2，2）問題（2）：如果要增加管道網(wǎng)的最大輸油量，應(yīng)該優(yōu)先增加哪個(gè)管道的輸油能力?答：cs2、c21、c13.（2，1）（5，4）（4，４）（3，0）（1，1）（1，0）２１４３Ｓt（3，3）（5，2）（2，2）練習(xí)用Dijkstra標(biāo)號(hào)法求網(wǎng)絡(luò)圖起點(diǎn)VS到終點(diǎn)Vt的最短路徑，結(jié)果如下圖示：由結(jié)果之間的關(guān)系，可以知A=

，B=

，C=

，D=

。起點(diǎn)VS到終點(diǎn)Vt的最短路程為

，最短路徑為：

。起點(diǎn)VS到點(diǎn)V5的最短路程為

，最短路徑為：

。練習(xí)如下圖所示的網(wǎng)絡(luò)圖，弧上數(shù)為（）。為了使f為可行流，則f23=

；f31=

；f14=

；f4t=

。找一條增廣鏈：

；為使可行流流量增加，如何改進(jìn)行可行流：

。（5，1）（3，3）（1，1）（2，f31）（4，f14）（2，f23）（2，1）（5，f4t）（3，0）s1324t575.5網(wǎng)絡(luò)計(jì)劃

20世紀(jì)50年代以來，國外陸續(xù)出現(xiàn)一些計(jì)劃管理的新方法，如關(guān)鍵路線法（CriticalPathMethod，縮寫為CPM），計(jì)劃評(píng)審方法（ProgramEvaluationReviewTechnique，縮寫為PETR）等。這些方法都是建立在網(wǎng)絡(luò)模型基礎(chǔ)之上，稱為網(wǎng)絡(luò)計(jì)劃技術(shù)。網(wǎng)絡(luò)計(jì)劃技術(shù)被地廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、國防、科研等計(jì)劃管理中，對(duì)縮短工期，節(jié)約人力、物力和財(cái)力，提高經(jīng)濟(jì)效益發(fā)揮了重要作用。我國數(shù)學(xué)家華羅庚先生將這些方法總結(jié)概括為統(tǒng)籌方法，引入中國并推廣應(yīng)用。統(tǒng)籌方法的基本原理是：從任務(wù)的總進(jìn)度著眼，以任務(wù)中各工作所需要的工時(shí)為時(shí)間因素；按照工作的先后順序和相互關(guān)系作出網(wǎng)絡(luò)圖，以反映任務(wù)全貌，實(shí)現(xiàn)管理過程的模型化。然后進(jìn)行時(shí)間參數(shù)計(jì)算，找出計(jì)劃中的關(guān)鍵工作和關(guān)鍵路線，對(duì)任務(wù)的各項(xiàng)工作所需的人、財(cái)、物通過改善網(wǎng)絡(luò)計(jì)劃作出合理安排，得到最優(yōu)方案并付諸實(shí)施。通過對(duì)各種評(píng)價(jià)指標(biāo)進(jìn)行定量化分析，在計(jì)劃的實(shí)施過程中，進(jìn)行有效的監(jiān)督與控制，以保證任務(wù)高質(zhì)量地完成。58例5

某項(xiàng)新產(chǎn)品投產(chǎn)前全部準(zhǔn)備工作如下表，表中列示了各工序所需時(shí)間以及它們之間的相互關(guān)系。工序工序內(nèi)容緊前工序工時(shí)（周）A市場(chǎng)調(diào)整/4B資金籌措/10C需求分析A3D產(chǎn)品設(shè)計(jì)A6E產(chǎn)品研制D8F制定成本計(jì)劃C，E2G制定生產(chǎn)計(jì)劃F3H籌備設(shè)備B，G2I原材料準(zhǔn)備B，G8J安裝設(shè)備H5K人員準(zhǔn)備G2L準(zhǔn)備開工投產(chǎn)I，J，K1問：（1）該新產(chǎn)品投產(chǎn)前全部準(zhǔn)備工作的最短工期需要多長時(shí)間？（2）如果要提早完成工期，優(yōu)先考慮壓縮哪些工序的工作時(shí)間？60一、網(wǎng)絡(luò)圖的繪制什么是網(wǎng)絡(luò)圖：網(wǎng)絡(luò)圖是由節(jié)點(diǎn)、弧及權(quán)所構(gòu)成的有向賦權(quán)圖。(1)用一個(gè)箭頭（?。┍硎疽粋€(gè)工序．多道工序就有多個(gè)箭頭。(2)把各個(gè)箭頭按工序間的相互制約關(guān)系，依流程方向從左向右聯(lián)系起來。(3)相鄰工序交接處畫上圓圈（節(jié)點(diǎn)），每個(gè)節(jié)點(diǎn)編上循序號(hào)，表示工序的事項(xiàng)。節(jié)點(diǎn)在箭尾表示工序的開始，節(jié)點(diǎn)在箭頭表示工序的完成。(4)把每道工序所需要的時(shí)間（權(quán)）標(biāo)在對(duì)應(yīng)的箭頭旁．２４３１６５７８４３２５５６３５５２61網(wǎng)絡(luò)圖的組成：（1）工序：指一項(xiàng)有具體內(nèi)容，需要一定人力，物力，經(jīng)過一定時(shí)間才能完成的生產(chǎn)過程或活動(dòng)過程．虛工序：不消耗資源，不需要時(shí)間，僅用以表示一個(gè)工序和另一工序之間相互依存的制約關(guān)系，是虛設(shè)的工序，用虛箭頭表示。工序代號(hào)緊前工序ＡＢＣＤ－－Ａ，ＢＢＡＢＣＤ（2）事項(xiàng)：指工序的開始（即開工事件）和工序的結(jié)束（完工事件）一個(gè)事項(xiàng)對(duì)它的前工序是完工事件，對(duì)它的后工序是開工事件。

②是工序Ａ的完工事件，是Ｂ的開工事件只有一個(gè)總的開工事件，一個(gè)總的完工事件。ＡＢ１２３62（3）路線：指網(wǎng)絡(luò)圖中從起點(diǎn)開始順箭頭所指方向，連續(xù)不斷到達(dá)終點(diǎn)為止的一條路。關(guān)鍵路線：指完成各個(gè)工序需要時(shí)間最長的路線，也稱主要矛盾線．繪制網(wǎng)絡(luò)圖的規(guī)則：(１)每個(gè)工序只出現(xiàn)一次。(２)只能有一個(gè)總起始頂點(diǎn)，一個(gè)總終止頂點(diǎn)。(３)不能有回路。(４)兩個(gè)頂點(diǎn)之間只能有一條弧。(５)正確表示工序之間的前行、后繼關(guān)系。(６)每一工序起始頂點(diǎn)編號(hào)小于終止頂點(diǎn)編號(hào)，所有編號(hào)從１連續(xù)編號(hào)。２４３１６５７８４３２５５６３５５２63例5

某項(xiàng)新產(chǎn)品投產(chǎn)前全部準(zhǔn)備工作如下表，表中列示了各工序所需時(shí)間以及它們之間的相互關(guān)系。要求編制該項(xiàng)工程的網(wǎng)絡(luò)計(jì)劃。工序工序內(nèi)容緊前工序工時(shí)（周）A市場(chǎng)調(diào)整/4B資金籌措/10C需求分析A3D產(chǎn)品設(shè)計(jì)A6E產(chǎn)品研制D8F制定成本計(jì)劃C，E2G制定生產(chǎn)計(jì)劃F3H籌備設(shè)備B，G2I原材料準(zhǔn)備B，G8J安裝設(shè)備H5K人員準(zhǔn)備G2L準(zhǔn)備開工投產(chǎn)I，J，K164工序緊前工序工時(shí)（周）工序緊前工序工時(shí)（周）A/4GF3B/10HB，G2CA3IB，G8DA6JH5ED8KG2FC，E2LI，J，K1AＢＣＤＥＦＧＨＩＫＪＬ４11３６８２３２８２５１１２３４５６７８９1065二、時(shí)間參數(shù)和關(guān)鍵路線計(jì)算

計(jì)算網(wǎng)絡(luò)圖中有關(guān)的時(shí)間參數(shù)，主要目的是找出關(guān)鍵路線，為網(wǎng)絡(luò)計(jì)劃的優(yōu)化、調(diào)整和執(zhí)行提供明確的時(shí)間概念。通常把網(wǎng)絡(luò)圖中需時(shí)最長的路線叫做關(guān)鍵路線，如右圖所示網(wǎng)絡(luò)中雙箭線表示的為關(guān)鍵路線，關(guān)鍵路線上的工序稱為關(guān)鍵工序。要想使任務(wù)按期完或提前完工，就要在關(guān)鍵路線的關(guān)鍵工序上想辦法。

網(wǎng)絡(luò)圖的時(shí)間參數(shù)包括工序所需時(shí)間、事項(xiàng)最早、最遲時(shí)間，工序的最早、最遲時(shí)間及時(shí)差等，下面分別敘述。1234564537223466工序時(shí)間的確定工序的所需時(shí)間可記為，有以下兩種情況：⑴完成每道工序所需時(shí)間確定，在具備勞動(dòng)定額資料，或者具有類似工序作業(yè)時(shí)間消耗的統(tǒng)計(jì)資料時(shí)，用對(duì)比分析來確定作業(yè)時(shí)間。⑵影響工序因素較多，作業(yè)時(shí)間難以確定，可以采用三點(diǎn)時(shí)間估計(jì)法來確定作業(yè)時(shí)間：a——最快可能完成時(shí)間b——最可能完成時(shí)間c——最慢可能完成時(shí)間一般情況下，可按下列公式近似計(jì)算作業(yè)時(shí)間。67

事項(xiàng)時(shí)間參數(shù)⑴事項(xiàng)最早時(shí)間事項(xiàng)ｊ的最早時(shí)間用表示，它表示以ｊ為始點(diǎn)的各工序最早可能開工的時(shí)間，也表示以ｊ為終點(diǎn)的各工序的最早可能完工時(shí)間。它等于從始點(diǎn)事項(xiàng)到本事項(xiàng)最長路線的時(shí)間長度。事項(xiàng)最早時(shí)間可用下列遞推公式，按照事項(xiàng)編號(hào)從小到大（自左向右）順序逐個(gè)計(jì)算。其中，為與事項(xiàng)ｊ相鄰的各緊前事項(xiàng)的最早時(shí)間。是工序的工時(shí)，Ａ為網(wǎng)絡(luò)圖?。üば颍┑娜w，為邊界條件．68例5中的事項(xiàng)最早時(shí)間：1０AＢＣＤＥＦＧＨＩＫＪＬ４３６８２３２８２５１１２３４５６７８９10８

０４182０23313223251０問（1）該新產(chǎn)品投產(chǎn)前全部準(zhǔn)備工作的最短工期需要多長時(shí)間？答：最短工期需要32周。70⑵事項(xiàng)的最遲時(shí)間事項(xiàng)ｉ的最遲時(shí)間用表示，它表明在不影響總工期條件下，以它為終點(diǎn)的各工作的最遲必須完工時(shí)間，或以它為始點(diǎn)的工序的最遲必須開工時(shí)間。在一般情況下，把任務(wù)的最早完工時(shí)間作為任務(wù)的總工期，所示事項(xiàng)