1、2022-6-51第七章網(wǎng) 絡(luò) 分 析2022-6-52第七章第七章 網(wǎng)絡(luò)分析網(wǎng)絡(luò)分析第一節(jié)第一節(jié) 圖的基本概念圖的基本概念第二節(jié)第二節(jié) 最小樹問題最小樹問題第三節(jié)第三節(jié) 最短路問題最短路問題第四節(jié)第四節(jié) 最大流問題最大流問題第五節(jié)第五節(jié) 中國郵遞員問題中國郵遞員問題第六節(jié)第六節(jié) 網(wǎng)絡(luò)計劃網(wǎng)絡(luò)計劃2022-6-53 歐拉在1736年發(fā)表圖論方面的第一篇論文，解決了著名的哥尼斯堡七橋問題。如圖7-1（a）所示。歐拉將此問題歸結(jié)為如圖7-1（b）所示圖形的一筆畫問題。歐拉證明了這是不可能的。 圖7-12022-6-54第一節(jié)第一節(jié) 圖的基本概念圖的基本概念 例例1 圖7-2是某省十個城鎮(zhèn)間的公路交

2、通圖，反映了這十個城鎮(zhèn)間的公路分布情況。這里用點代表城鎮(zhèn)，用點和點之間的聯(lián)線代表這兩個城鎮(zhèn)之間的公路線。諸如此類的還有電話線分布圖、煤氣管道圖、航空線圖等。v4v10v7v2v1 v9 v6v8v5 v3圖7-22022-6-55v1v3v4v5v2圖7-3 例例2 2 有甲、乙、丙、丁、戊五個球隊，它們之間比賽的情況，也可以用圖表示出來。已知甲隊和其它各隊都比賽過一次，乙隊和甲、丙隊比賽過，丙隊和乙、丁隊比賽過，丁隊和丙、戊隊比賽過，戊隊和甲、丁隊比賽過。為了反映這個情況，可以用點v1，v2，v3，v4，v5分別代表這五個隊，某兩個隊之間比賽過，就在這兩個隊所相應(yīng)的點之間聯(lián)一條線，這條線不過

3、其它的點，如圖7-3所示。1v2v3v4v5v2022-6-56 前面例子中涉及到的對象之間的“關(guān)系”具有“對稱性”，但在實際生活中，有許多關(guān)系不具有這種對稱性。如例2，如果人們關(guān)心的是五個球隊比賽的勝負(fù)情況，那么可以用一條帶箭頭的聯(lián)線表示。圖7-4反映了五個球隊比賽的勝負(fù)情況。 v1v2v3v4v5圖7-4 綜上所述，一個圖是由一些點及一些點之間的聯(lián)線（不帶箭頭或帶箭頭）所組成的。為了區(qū)別起見，把兩點之間的不帶箭頭的聯(lián)線稱為邊邊，帶箭頭的聯(lián)線稱為弧弧。 如果一個圖是由點及邊所構(gòu)成的，則稱之為無向圖無向圖（也簡稱為圖圖），記為=（，），式中，分別是的點集合和邊集合。一條聯(lián)結(jié)點vi，vj的邊記為

4、vi，vj（或vj，vi）。2022-6-57ivjvivjvjviv 如果一個圖是由點及弧所構(gòu)成的，則稱為有向圖有向圖，記為=（，）式中，分別表示的點集合和弧集合。一條方向是從vi指向vj的弧記為（ vi ， vj ）。 ivjvivjv圖7-5是一個無向圖。 V=v1,v2,v3,v4, E=e1,e2,e3,e4,e5,e6,e7其中e1=v1,v2, e2=v1,v2, e3=v2,v3, e4=v3,v4e5=v1,v4, e6=v1,v3, e7=v4,v4e5e3e7e2e6e1v4v3v2v1e4圖7-52022-6-58圖7-6是一個有向圖， V=v1,v2,v3,v4,v5

5、,v6,v7, A=a1,a2,a3,a4, ,a11其中 a1=(v1,v2), a2=(v1,v3), a3=(v3,v2), a4=(v3,v4), a5=(v2,v4), a6=(v4,v5), a7=(v4,v6), a8=(v5,v3), a9=(v5,v4), a10=(v5,v6), a11=(v6,v7), v1a3a11a7a10a6a9a1a5a4a8a2v5v3v2v7v6v4圖7-62022-6-59 圖或中的點數(shù)記為p(G)或p(D)，邊（?。?shù)記為q(G)(q(D)，也分別簡記為p，q。下面介紹常用的一些名詞和記號，先考慮無向圖=（，）。 若邊e=u,v E，則稱

6、，是的端點端點，也稱，是相鄰相鄰的，稱是點（及點）的關(guān)聯(lián)邊關(guān)聯(lián)邊。若圖中，某個邊的兩個端點相同，則稱是環(huán)環(huán)（如圖7-5中的e7）,若兩個點之間有多于一條的邊,稱這些邊為多重邊多重邊(如圖7-5中的12）。 一個無環(huán)、無多重邊的圖稱為簡單圖簡單圖，一個無環(huán)、但允許有多重邊的圖稱為多重圖多重圖。 以點為端點的邊的個數(shù)稱為的次次，記為dG(v)或d（v）。如圖7-5中，d(v1)=4, d(v2)=3, d(v3)=3, d(v4)=4，（環(huán)7在計算時算作兩次）。 稱次為1的點為懸掛點懸掛點，懸掛點的關(guān)聯(lián)邊稱為懸掛懸掛邊邊，次為零的點稱為孤立點孤立點。 2022-6-510 定理定理 圖=（，）中，

7、所有點的次之和是邊數(shù)的兩倍，即Vvqvd2)( 次為奇數(shù)的點，稱為奇點奇點，否則稱為偶點偶點。 給定一個圖=（，），一個點，邊的交錯序列(vi1,ei1,vi2,ei2, ,vik-1,eik-1,vik ），如果滿足eit=vit,vit+1(t=1,2, ,k-1) ，則稱為一條聯(lián)結(jié)vi1和vik的鏈鏈，記為(vi1,vi2, ,vik)，有時稱點vi1,vi2, ,vik為鏈的中間點中間點。 定理定理 任一個圖中，奇點的個數(shù)為偶數(shù)。 鏈(vi1,vi2, ,vik)中，若，則稱之為一個圈圈，記為（ vi1,vi2, ,vik ）。若鏈（ vi1,vi2, ,vik ）中，點vi1,vi2

8、, ,vik都是不同的，則稱之為初等鏈初等鏈；若圈（ vi1,vi2, ,vik-1,vik ）中， vi1,vi2, ,vik-1都是不同的，則稱之為初等圈初等圈；若鏈（圈）中含的邊均不相同，則稱之為簡單圈簡單圈。2022-6-511 圖中，若任何兩個點之間，至少有一條鏈，則稱是連通圖連通圖，否則稱為不連通圖不連通圖。若是不連通圖，它的每個連通的部分稱為的一個連通分圖連通分圖（也簡稱分圖分圖）。如圖7-7是一個不連通圖，則它有兩個連通分圖。e1 圖7-7v1e5e3e9e10v2v6v3v4v7v5v9v8e6e8e4e2e72022-6-512 設(shè)vV(G)，用G-v表示從圖G中去掉點v及

9、v的關(guān)聯(lián)邊后得到的一個圖。例如若G如圖7-8(a)所示，則如圖7-8(b)所示。圖7-8(c)是圖的一個支撐子圖 。 給了一個圖=（，），若圖=（，），使V=及，則稱是的一個支撐子圖支撐子圖。 圖7-8(a)(b)(c)v1v3v4v5v2v4v2v2v5v3v4v1v5v12022-6-513 現(xiàn)在討論有向圖的情形。設(shè)有一個有向圖，D=(,A)，從中去掉所有弧上的箭頭，就得到一個無向圖，稱之為的基礎(chǔ)圖基礎(chǔ)圖，記之為（）。給中的一條弧a=(u,v)，稱u為a的始點始點，v為a的終點終點，稱弧a是從u指向v的。 設(shè)（ vi1,ai1,vi2,ai2,vik-1,aik-1,vik ）是中的一個點

10、弧交錯序列，如果這個序列在基礎(chǔ)圖G(D)中所對應(yīng)的點邊序列是一條鏈，則稱這個點弧交錯序列是D的一條鏈。類似定義圈和初等鏈（圈）。 如果（vi1,ai1,vi2,ai2,vik-1,aik-1,vik ）是中的一條鏈，且對t=1,2, ,k-1 ，均有ait=(vit,vit+1)，稱之為從vi1到vik 的一條路路。若路的第一點和最后一點相同，則稱之為回路回路，類似定義初等路初等路（回路）。2022-6-514第二節(jié)第二節(jié) 最小樹問題最小樹問題 一、樹的基本概念 例例 已知有五個城市，要在它們之間架設(shè)電話線，要求任何兩個城市都可以互相通話（允許通過其它城市），并且電話線的根數(shù)最少。 解解 用五

11、個點v1，v2，v3，v4，v5代表五個城市，如果在某兩個城市之間架設(shè)電話線，則在相應(yīng)的兩個點之間聯(lián)一條邊，這樣一個電話線網(wǎng)就可以用一個圖來表示。 圖7-9代表了滿足要求的一個電話線網(wǎng)。 v1v2v3v4v5v4v3v2v5v1圖7-9圖7-102022-6-515 定義定義 一個無圈的連通圖稱為樹樹。 定理定理 設(shè)圖=（，）是一個樹，則中至少 有兩個懸掛點。 定理定理 圖=（，）是一個樹的充分必要條件是 不含圈，且恰有p-1條邊。 定理定理 圖=（，）是一個樹的充分必要條件是 是連通圖，并且 定理定理 圖是樹的充分必要條件是任意兩個頂點之間 恰有一條鏈。1)()(GpGq 樹的一些重要性質(zhì)由

12、定理4，很容易推出如下結(jié)論：1.從一個樹中去掉任意一條邊，則余下的圖是不連通的2.在樹中不相鄰的兩個點間添上一條邊，則恰好得到一個圈。進一步地說，如果再從這個圈上任意去掉一條邊，可以得到一個樹。 2022-6-516v1v5v3v2v4v6v3v4v2v6v1v5圖7-11(b)(a) 定義定義 設(shè)圖=（，）是圖=（，）的支撐子圖，如果圖=（，）是一個樹，則稱是的一個支撐樹支撐樹。二、圖的支撐樹二、圖的支撐樹例如圖7-11（b）是圖7-11（a）所示圖的一個支撐樹 2022-6-517 定理定理 圖有支撐樹的充分必要條件是圖是連通的。 定理中充分性的證明，提供了一個尋求連通圖的支撐樹的方法。這

13、就是任取一個圈，從圈中去掉一邊，對余下的圖重復(fù)這個步驟，直到不含圈時為止，即得到一個支撐樹，稱這種方法為“破圈法破圈法”。 例例 在圖7-12中，用破圈法求出圖的一個支撐樹。 1e1e2e1e2e3ekeee,21v1e4e3e6e8e1v4v5v3v2e5e2e7圖7-122022-6-518 也可以用另一種方法來尋求連通圖的支撐樹。在圖中任取一條邊e1，找一條與e1不構(gòu)成圈的邊e2，再找一條與e1,e2不構(gòu)成圈的邊e3。一般,設(shè)已有e1,e2,ek,找一條與e1,e2, ,ek中的任何一些邊不構(gòu)成圈的邊ek+1。重復(fù)這個過程，直到不能進行為止。這時，由所有取出的邊所構(gòu)成的圖是一個支撐樹，稱

14、這種方法為“避圈避圈法法”。 例例 在圖7-13中，用避圈法求出一個支撐樹。 v1e2e7v2e3e9e8e1e6e5e4v3v5v6v4圖7-132022-6-519 定義定義 給圖=（，），對中的每一條邊 vi，vj，相應(yīng)地有一個數(shù)wij，則稱這樣的圖為賦權(quán)賦權(quán)圖圖， wij稱為邊vi，vj上的權(quán)權(quán)。 這里所說的“權(quán)”，是指與邊有關(guān)的數(shù)量指標(biāo)。根據(jù)實際問題的需要，可以賦予它不同的含義，例如表示距離、時間、費用等。 定義定義 如果=（，）是的一個支撐樹，稱中所有邊的權(quán)之和為支撐樹的權(quán)，記為（）。 即TvvijjiwTw,)( 如果支撐樹*的權(quán)（*）是的所有支撐樹的權(quán)中最小者，則稱*是G的最小

15、支撐樹最小支撐樹（簡稱最小樹最小樹）。即)(min*)(TwTwT式中對的所有支撐樹取最小。 三、三、最小支撐樹問題2022-6-520 開始選一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈（每一步中，如果有兩條或兩條以上的邊都是權(quán)最小的邊，則從中任選一條）。 例例 某企業(yè)內(nèi)聯(lián)結(jié)六個車間的道路網(wǎng)如圖7-14（a）所示。已知每條道路的長，要求沿道路架設(shè)聯(lián)結(jié)六個車間的電話線網(wǎng)，使電話線的總長最小。解解 這個問題就是要求如圖7-14所示的賦權(quán)圖上的最小樹。 v16v5v3v2v4v651725434圖7-14求最小樹的兩種方法。避圈法2022-6-521

16、 任取一個圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條）。在余下的圖中，重復(fù)這個步驟，一直得到一個不含圈的圖為止，這時的圖便是最小樹。 例例 用破圈法求圖7-14所示賦權(quán)圖最小支撐樹。 v16v5v3v2v4v651725434圖7-14破圈法2022-6-522第三節(jié)第三節(jié) 最短路問題最短路問題 最短路問題在實際問題中有廣泛的應(yīng)用。例如管道的鋪設(shè)、線路安排、運輸路線的選擇、企業(yè)布局等問題。 狄克斯屈（E.W.Dijkstra）標(biāo)號算法，是由狄克斯屈于1959年提出，是目前公認(rèn)的求解最短路問題的較好算法。這種算法的基本思想可歸納如下： （1）由于從起

17、點到終點往往存在著許多不同的通路，可經(jīng)過各不同的中間點，情況比較復(fù)雜，該算法的計算過程中，把所有的計算局限在關(guān)聯(lián)邊，即直接連接相關(guān)兩點的邊。則就把一個復(fù)雜的問題轉(zhuǎn)化成一系列的簡單運算。二、二、最短路算法一、一、最短路問題2022-6-523 （）從起點出發(fā)，依次尋找到起點距離最短的點，并以這最短距離作為該點的標(biāo)號，每次尋找一個點。 （）若已經(jīng)計算出起點到若干點的最短距離，在找下一點時，要充分考慮到經(jīng)過集合中每一點的可能。也就是說要考慮集合中的每一點到其他點的距離，從中選取最短距離的點。 （）重復(fù)上述過程，直到終點的標(biāo)號被找到，則可終止計算，找出最短路。 如果要找起點到其他每一點的最短路，則必須

18、計算到所有點的標(biāo)號均找到為止。 例例 設(shè)有一批貨物要從運到，邊上的數(shù)字表示該段路的長，求最短的運輸路線。網(wǎng)絡(luò)圖見圖7-15。1v7v下面我們通過一個簡單的例子來說明這種算法。2022-6-524v4v1 v2 v5v3 v7v614247512236圖7-150 解解 給起點v1標(biāo)號，記為d(v1)=0，用以表示v1是起點，=v1。下面依次尋找到距離v1最短的點，這個過程可稱為迭代。 220),()(110),()(3111321112vvlvdkvvlvdk 第一步：找出與=v1中點直接相連的邊，并計算出它們的距離。關(guān)聯(lián)邊有（v1，v2），（v1，v3），相應(yīng)的距離記為：2022-6-525

19、 取上述值中最小的，mink12,k13=1,2=1，對應(yīng)的點為v2，說明v2是v1到其他所有點距離最短的，則進入，=v1，v2，v2的標(biāo)號d(v2)=1，在圖上標(biāo)出，并把邊（v1，v2）加粗，用以表示v1到v2的最短距離是經(jīng)過e（v1，v2）實現(xiàn)的，見圖7-16。v4v1 v2 v5v3 v7v614247512236圖7-16012022-6-526 第二步：找出與=v1，v2中點直接相連的邊，與v1相連邊有條（v1，v3），（v1，v2）已加粗，v2已進入集，不用再考慮，一般情況下考慮的邊必須是一端的點在集，另一端的點不在集。以下同）。與v2相連邊有4條（v2，v3），（v2，v4），（

20、v2，v5），（v2，v6），分別計算v1到相關(guān)各點的距離得：651),()(871),()(541),()(321),()(440),()(6222652225422243222331113vvlvdkvvlvdkvvlvdkvvlvdkvvlvdk 取上述值最小的，min=k13,k23,k24,k25,k26=3，對應(yīng)的點為v3，說明除了v2，v1到其他各點的距離中，到v3的距離最短，且為。則v3進入，=v1，v2，v3，v3的標(biāo)號d(v3)=3。由于k23=3，即知這最短路是經(jīng)過v2的，將邊（v2，v3）加粗。見圖7-17。2022-6-527v1 v2 v5v3 v7v6142475

21、12236圖7-1701v43 第三步：找出與=v1，v2，v3中點直接相連的邊，與v1相連的邊已沒有了，與v2相連的有（v2，v4），（v2，v5），（v2，v6），與v3相連的邊有（v3，v6），分別計算相關(guān)各點的距離：413),()(651),()(871),()(541),()(63336622265222542224vvlvdkvvlvdkvvlvdkvvlvdk2022-6-528 取上述值最小的，min=k24,k25,k26,k36=4，對應(yīng)的點是v6，說明除了集合中的點，v1到其他各點的距離中，最短的是v6，且為，則v6進入，=v1,v2，v3，v6，v6的標(biāo)號為。由k36=

22、4可知，由v1到v6的最短路是經(jīng)過v3的，將邊e（v3，v6）加粗，見圖7-18。v1 v2 v5v3 v7v614247512236圖7-18013v442022-6-529 第四步：同樣找出與集中各點相連的邊，并計算如下： 1064),()6(734),()6(871),()2(541),()2(7667566552254224vvldkvvldkvvldkvvldk 最小的是k24=5，則v4進入集，=v1，v2，v3，v6，v4，v4的標(biāo)號為，加粗邊（v2，v4），見圖7-19。v1 v2 v5v3 v7v614247512236圖7-190134v452022-6-530 第五步：與

23、集關(guān)聯(lián)的邊的參數(shù)計算如下： 1064),()(734),()(725),()(871),()(76667566655444552225vvlvdkvvlvdkvvlvdkvvlvdk 最小值是，且有k4 5=k6 5=7，則v5進入集， =v1，v2，v3，v6，v4，v5，v5的標(biāo)號為，同時加粗邊（v4，v5）和（v6，v5），見圖7-20。v1 v2 v5v3 v7v614247512236圖7-200134v4572022-6-531第六步：與集關(guān)聯(lián)的邊的參數(shù)計算如下： 1064),()6(927),()5(76677557vvldkvvldk75632175421vvvvvvvvvvv

24、最小值是，v7則進入集，v7的標(biāo)號為，加粗邊（v5，v7）。由于v7是終點，故已算得到的最短距離是。至于最短路，只要從點v1開始，沿加粗的邊，找到通往v7的路，即為最短路。在圖7-21中，容易找到到的最短通路，它們有兩條，分別是： v2 v5v3 v7v614247512236圖7-210134v45792022-6-532第四節(jié)第四節(jié) 最大流問題最大流問題 所謂最大流問題，就是在一定的條件下，要求流過網(wǎng)絡(luò)系統(tǒng)中某種流的流量為最大的問題。 如圖7-22是聯(lián)結(jié)某產(chǎn)品產(chǎn)地v1和銷地v6的交通網(wǎng)，每一?。╲i，vj）代表從vi到vj的運輸線，產(chǎn)品經(jīng)這條弧由vi輸送到vj,弧旁的數(shù)字表示這條運輸線的最

25、大通過能力。產(chǎn)品經(jīng)過交通網(wǎng)從v1輸送到v6?，F(xiàn)在要求制定一個運輸方案使從v1運到v6的產(chǎn)品數(shù)量最多。1v6vivjvivjvivjv1v6v1v6v v2 v458517113v1v634v3v56圖7-22 2022-6-533 圖7-23給出了一個運輸方案，每條弧旁的數(shù)字表示在這個方案中，每條運輸線上的運輸數(shù)量。這個方案使8個單位的產(chǎn)品從v1運到v6，在這個交通網(wǎng)上輸送量是否還可以增多，或者說這個運輸網(wǎng)絡(luò)中，從v1到v6的最大輸送量是多少呢？本節(jié)就是要研究類似這樣的問題。v1v6v3v5v2v4圖7-232022-6-534 定義定義 給一個有向圖=（，），在中指定了一點，稱為發(fā)點發(fā)點（記

26、為vs），和另一點，稱為收點收點（記為vt），其余的點叫中間點。對于每一個?。╲i，vj）,對應(yīng)有一個（vi，vj）（或簡寫為cij），稱為弧的容量容量。通常我們就把這樣的叫作一個網(wǎng)絡(luò)網(wǎng)絡(luò)，記作 =（，）。 所謂網(wǎng)絡(luò)上的流，是指定義在弧集合上的一個函數(shù)f =f(vi,vj)，并稱（vi，vj）為?。╲i，vj）上的流量流量。（有時也簡記作fij）。 例如圖7-22就是一個網(wǎng)絡(luò)，指定v1是發(fā)點，v6是收點，其它的點是中間點。弧旁的數(shù)字為cij。 圖7-23所示的運輸方案，就可看作是這個網(wǎng)絡(luò)上的一個流，每個弧上的運輸量就是該弧上的流量，即f12=5, f34=2, f13=3, f34=1等。 一

27、、基本概念網(wǎng)絡(luò)與流2022-6-535定義定義 滿足下述條件的流稱為可行流可行流： （）容量限制條件：對每一?。╲i，vj）ivjvijijcf0（）平衡條件： 對于中間點：流出量流入量，即對每個i(is,t)有AvvAvvjiijjiijff),(),(0 對于發(fā)點vs：有 svAvvAvvjssjjssjfvff),(),()( 對于收點vt：有 tvAvvAvvjttjjttjfvff),(),()( 式中（）稱為這個可行流的流量，即發(fā)點的凈輸出量（或收點的凈輸入量）?？尚辛髋c最大流2022-6-536 可行流總是存在的。比如令所有弧的流量fij=0，就得到一個可行流（稱為零流）。其流量

28、（）=0。 ijf 最大流問題就是求一個流fij，使其流量（）達(dá)到最大，并且滿足： ijfAvvcfjiijij),( 0(1)( )(),( 0)( )(tifvtsisifvffjiij(2) 最大流問題是一個特殊的線性規(guī)劃問題。即求一組fij，在滿足（）和（）條件下使（）達(dá)到極大。我們將會看到利用圖的特點，解決這個問題的方法較之線性規(guī)劃的一般方法要方便、直觀得多。 ijf2022-6-537 圖解法就是根據(jù)最大流問題的網(wǎng)絡(luò)圖來尋找從起點到終點所允許通過的最大流量。其具體步驟是：svtv（）先從網(wǎng)絡(luò)圖的最外層開始找出從vs到vt的通路。（）接著找出該通路中允許通過的最小流量，并從該通路中各

29、邊上減去最小流量值。（）將上述具有最小流量的邊刪去，余下的重新畫出網(wǎng)絡(luò)圖。（）重復(fù)上述步驟，直到從vs到vt已無通路時為止。（）將上述各通路的最小流量值相加，即為該網(wǎng)絡(luò)的最大流。 svtvsvtv 例例 圖7-24為一網(wǎng)絡(luò)最大流問題?，F(xiàn)用圖解法求解。二、求最大流的方法二、求最大流的方法圖解法2022-6-538vsv2vtv5v41394565104594v6v35 解解 (1)先從網(wǎng)絡(luò)圖的最外層找出從vs到vt的通路。結(jié)果有：tsvvvv955213tsvvvv106539(1)(2) （）式（）、（）兩條通路的最小允許流量c25、c36，其值均為。 圖7-242022-6-539 并從式（

30、）、（）兩條通路中減去，得tsvvvv45028tsvvvv56034（）刪除cij=的邊，重新畫出網(wǎng)絡(luò)圖如圖7-25所示。vsv2vtv5v48446554544v6v3圖7-252022-6-540（）重復(fù)步驟（）（）。根據(jù)圖7-25所示網(wǎng)絡(luò)，從最外層找出從vs到vt的通路，結(jié)果有：tsvvvvv4554628tsvvvvv5644534(3)(4) 式（）、（）兩條通路的最小允許流量c5t、c46其值均為。并從（）、（）中減去，得tsvvvvv0514224tsvvvvv1604130 刪除cij=的邊后，重新畫出網(wǎng)絡(luò)圖如圖7-26所示。 vsv2vtv5v44421141v6v3圖7-

31、262022-6-541 再重復(fù)步驟（）（），根據(jù)圖7-26可知，此時從vs到vt只有一條通路，即tsvvvv 44224(5) 上述最小允許流量為c24=2，并從式（）中減去，得tsvvvv 24022 刪除cij=的邊（v2，v4）后，重新畫出網(wǎng)絡(luò)圖如圖7-27所示。由圖可知，此時從vs到vt已無通路可找。 vsv2vtv5v441121v6v32圖7-272022-6-542 （）將上述式（）（）通路的最小允許流量值相加，得 =5+5+4+4+2=20 則=20即為該網(wǎng)絡(luò)的最大流量。 從上述用圖解法求網(wǎng)絡(luò)的最大流問題可知，其實就是找出流經(jīng)網(wǎng)絡(luò)的最小流的集合。這一原理一般稱做最大流最小割集

32、原理。 圖7-31所示即為最大流量網(wǎng)絡(luò)圖。由圖可知，其最大流量為20。即fs3+f32+f24+f25=9+0+6+5=20。此即所謂的最大流最小割網(wǎng)絡(luò)流量。 標(biāo)號法 標(biāo)號法是用來求解最大流問題的常用方法。這種方法就是根據(jù)最大流最小割集原理來進行求解的。2022-6-543vsv2vtv5v41394565104594v6v35圖7-31f +=20 fmax=20 (9)(4)(5)(0)(5)(11)(9)(7)(4)cij ( fij )(6)(4)(2)2022-6-544第五節(jié)第五節(jié) 中國郵遞員問題中國郵遞員問題 主要的結(jié)論是：（）一個連通圖中的頂點都是偶點，沒有奇點，則該圖可以一筆

33、畫出。（）一個連通圖中的頂點恰有兩個是奇點，其余均為偶點，則從任一奇點出發(fā)，可一筆畫出該圖，而終點則是另一個奇點。（）一個連通圖中的頂點有兩個以上是奇點，則該圖不能一筆畫出。一、一筆畫問題一、一筆畫問題 一筆畫問題是討論一個連通圖是否能一筆畫出。討論從圖中的某點出發(fā)，經(jīng)過每條邊一次且僅僅一次，再返回該點是否可能。早在1736年數(shù)學(xué)家歐拉解決哥尼斯堡七橋問題時已解決了這個問題（見圖7-32）。2022-6-545v1v2v3v4v5v6v7ABCDv1v2v3v4v5 v6v7(a)(c)(b) 在圖7-32（b）中，它即為哥尼斯堡七橋問題抽象出的圖，四個頂點的次數(shù)均為奇數(shù)，有四個奇點，故該圖不

34、能一筆畫出。也就是說，從陸地上的任一點出發(fā)，經(jīng)過每座橋一次且僅一次返回原地是不可能的。 在圖7-32（c）中，七個頂點中，是奇點，其他點均為偶點。故可從出發(fā)經(jīng)過各邊一次且僅一次，到達(dá)，一筆畫出該圖，當(dāng)然也可從出發(fā)，經(jīng)各邊一次且僅一次到達(dá)。圖7-32 在圖7-32（a）中，七個頂點均為偶點，故可一筆畫出。2022-6-546第六節(jié)第六節(jié) 網(wǎng)絡(luò)計劃網(wǎng)絡(luò)計劃 例例1111 某項研制新產(chǎn)品工程的各個工序與所需時間以及它們之間的相互關(guān)系如表7-1所示。要求編制該項工程的網(wǎng)絡(luò)計劃。 為編制網(wǎng)絡(luò)計劃，首先需繪制網(wǎng)絡(luò)圖。網(wǎng)絡(luò)圖是由結(jié)點（點）、弧及權(quán)所構(gòu)成的有向圖，即有向的賦權(quán)圖。 根據(jù)表7-1的已知條件和數(shù)據(jù)

35、，繪制的網(wǎng)絡(luò)圖如圖7-35所示。一、網(wǎng)絡(luò)圖一、網(wǎng)絡(luò)圖2022-6-547表7-1 工序工序代號所需時間（天）緊后工序產(chǎn)品設(shè)計與工藝設(shè)計a60b,c,d,e外購配套件b45l下料、鍛件c10f工裝制造d20g,h木模、鑄件e40h機械加工f18l工裝制造g30k機械加工h15l機械加工k25l裝配調(diào)試l352022-6-54852467138adgklehbcf 60 203025351810451540圖7-352022-6-549二、二、網(wǎng)絡(luò)圖的繪制原則方向、時序和結(jié)點編號緊前工序與緊后工序虛工序相鄰的兩個結(jié)點之間只能有一條弧網(wǎng)絡(luò)圖中不能有缺口和回路平行作業(yè)交叉作業(yè)始點和終點網(wǎng)絡(luò)圖的分解與綜

36、合10. 網(wǎng)絡(luò)圖的布局2022-6-5501323142圖7-36圖7-371432dabc圖7-38aabbcc2022-6-551 在網(wǎng)絡(luò)圖中，從始點開始，按照各個工序的順序，連續(xù)不斷地到達(dá)終點的一條通路稱為路線。如在圖7-35中，共有五條路線。 為了編制網(wǎng)絡(luò)計劃和找出關(guān)鍵路線，要計算網(wǎng)絡(luò)圖中各個事項及各個工序的有關(guān)時間，稱這些有關(guān)時間為網(wǎng)絡(luò)時間。三、網(wǎng)絡(luò)時間與關(guān)鍵路線三、網(wǎng)絡(luò)時間與關(guān)鍵路線路線與關(guān)鍵路線網(wǎng)絡(luò)時間的計算 在各條路線上，完成各個工序的時間之和是不完全相等的。其中，完成各個工序需要時間最長的路線稱為關(guān)鍵路線，或稱主要矛盾線，在圖中用粗線表示。在圖7-35 中，第三條路線就是條關(guān)鍵路線，組成關(guān)鍵路線的工序稱為關(guān)鍵工序。2022-6-552 為完成某一工序所需要的時間稱為該工序的作業(yè)時間，用Tij表示。確定作業(yè)時間有兩種方法。 ijT 一點時間估計法 三點時間估計法64bmaT 估計的三種時間是： 樂 觀 時間： 常用符號a表示； 最可能時間： 常用符號表示； 悲 觀 時間： 常用符號表示。一般情況下，可按下列公式計算作業(yè)時間： （）作業(yè)時間2022-6-553 若事項為某一工序或若干工序的箭尾事項時