圖與網(wǎng)絡(luò)分析(4課時(shí))起訖點(diǎn)不同最短路最大流問題

1、運(yùn)運(yùn) 籌籌 學(xué)學(xué)( Operations Research )圖的基本概念與模型圖的基本概念與模型樹與圖的最小樹樹與圖的最小樹最短路問題最短路問題網(wǎng)絡(luò)的最大流網(wǎng)絡(luò)的最大流Page 3近代圖論的歷史可追溯到近代圖論的歷史可追溯到18世紀(jì)的七橋問題世紀(jì)的七橋問題穿過(guò)穿過(guò)Knigsberg城的七座橋，要求每座橋通過(guò)一次且僅通過(guò)一次。城的七座橋，要求每座橋通過(guò)一次且僅通過(guò)一次。 這就是著名的這就是著名的“哥尼斯堡哥尼斯堡 7 橋橋”難題。難題。Euler1736年證明了不年證明了不可能存在這樣的路線?？赡艽嬖谶@樣的路線。Page 4圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。圖論中圖是由點(diǎn)和邊

2、構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的。曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的。若用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象之間的聯(lián)系，若用點(diǎn)表示研究的對(duì)象，用邊表示這些對(duì)象之間的聯(lián)系，則圖則圖G可以定義為點(diǎn)和邊的集合，記作：可以定義為點(diǎn)和邊的集合，記作：,EVG 其中其中: V點(diǎn)集點(diǎn)集 E邊集邊集 圖圖G區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以及哪些點(diǎn)之間有連線。及哪些點(diǎn)之間有連線。Page 5(v1)趙趙

3、(v2)錢錢孫孫(v3) 李李(v4)周周(v5)吳吳(v6)陳陳(v7)e2e1e3e4e5(v1)趙趙(v2)錢錢(v3)孫孫(v4)李李(v5)周周(v6)吳吳(v7)陳陳e2e1e3e4e5可見圖論中的圖與幾何圖、工程圖是不一樣的?？梢妶D論中的圖與幾何圖、工程圖是不一樣的。例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來(lái)例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來(lái)表示。表示。Page 6定義定義: 圖中的點(diǎn)用圖中的點(diǎn)用v表示，邊用表示，邊用e表示。對(duì)每條邊可用它所連表示。對(duì)每條邊可用它所連接的點(diǎn)表示，記作：接的點(diǎn)表示，記作：e1=v1,v1; e2=v1,v2; v3e7e

4、4e8e5e6e1e2e3v1v2v4v5 端點(diǎn)端點(diǎn),關(guān)聯(lián)邊關(guān)聯(lián)邊,相鄰相鄰若有邊若有邊e可表示為可表示為e=vi,vj，稱，稱vi和和vj是邊是邊e的的端點(diǎn)端點(diǎn)，反之稱邊，反之稱邊e為點(diǎn)為點(diǎn)vi或或vj的的關(guān)聯(lián)邊關(guān)聯(lián)邊。若點(diǎn)。若點(diǎn)vi、vj與同一條邊關(guān)與同一條邊關(guān)聯(lián)，稱點(diǎn)聯(lián)，稱點(diǎn)vi和和vj相鄰；若邊相鄰；若邊ei和和ej具具有公共的端點(diǎn)，稱邊有公共的端點(diǎn)，稱邊ei和和ej相鄰相鄰。Page 7 環(huán)環(huán), 多重邊多重邊, 簡(jiǎn)單圖簡(jiǎn)單圖如果邊如果邊e的兩個(gè)端點(diǎn)相重，稱該邊為的兩個(gè)端點(diǎn)相重，稱該邊為環(huán)環(huán)。如右圖中邊。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)為環(huán)。如果兩個(gè)點(diǎn)之間多于一條，稱為之間多于一條，稱為

5、多重邊多重邊，如右圖，如右圖中的中的e4和和e5，對(duì)無(wú)環(huán)、無(wú)多重邊的圖，對(duì)無(wú)環(huán)、無(wú)多重邊的圖稱作稱作簡(jiǎn)單圖簡(jiǎn)單圖。v3e7e4e8e5e6e1e2e3v1v2v4v5Page 8 次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)與某一個(gè)點(diǎn)與某一個(gè)點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為相關(guān)聯(lián)的邊的數(shù)目稱為點(diǎn)點(diǎn)vi的的次次（也叫做度），記作（也叫做度），記作d(vi)。右圖中右圖中d(v1),d(v3)=5,d(v5)=1。次。次為奇數(shù)的點(diǎn)稱作為奇數(shù)的點(diǎn)稱作奇點(diǎn)奇點(diǎn)，次為偶數(shù)的，次為偶數(shù)的點(diǎn)稱作點(diǎn)稱作偶點(diǎn)偶點(diǎn)，次為，次為1的點(diǎn)稱為的點(diǎn)稱為懸掛點(diǎn)懸掛點(diǎn)，次為次為0的點(diǎn)稱作的點(diǎn)稱作孤立點(diǎn)孤立點(diǎn)。v3e7e4e8e5e

6、6e1e2e3v1v2v4v5圖的次圖的次: 一個(gè)圖的次等于各點(diǎn)的次之和。一個(gè)圖的次等于各點(diǎn)的次之和。Page 9 鏈，圈，連通圖鏈，圈，連通圖圖中某些點(diǎn)和邊的交替序列，若其圖中某些點(diǎn)和邊的交替序列，若其中各邊互不相同，且對(duì)任意中各邊互不相同，且對(duì)任意vi,t-1和和vit均相鄰稱為均相鄰稱為鏈鏈。用。用 表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5,110kkvevev 起點(diǎn)與終點(diǎn)重合的鏈稱作起點(diǎn)與終點(diǎn)重合的鏈稱作圈圈。如。如果每一對(duì)頂點(diǎn)之間至少存在一條果每一對(duì)頂點(diǎn)之間至少存在一條鏈，稱這樣的圖為鏈，稱這樣的圖為連通圖連通圖，否則，否則稱圖不連通。稱圖不連通。Page 1

7、0 子圖，部分圖子圖，部分圖(支撐子圖支撐子圖)圖圖G1=V1、E1和圖和圖G2=V2，E2如果有如果有 稱稱G1是是G2的一個(gè)的一個(gè)子圖子圖。若有若有 ，則稱，則稱G1是是G2的一的一個(gè)個(gè)部分圖部分圖(支撐子圖支撐子圖)。2121EEVV 和和2121EEVV ，v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G圖）圖）Page 11 網(wǎng)絡(luò)（賦權(quán)圖）網(wǎng)絡(luò)（賦權(quán)圖）設(shè)圖設(shè)圖G（V，E），對(duì)），對(duì)G的每一條邊的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊稱為邊(vi,vj)

8、的的權(quán)權(quán),賦予權(quán)的圖賦予權(quán)的圖G稱為網(wǎng)絡(luò)稱為網(wǎng)絡(luò)(或或賦權(quán)圖）賦權(quán)圖）。權(quán)可以代表距離、費(fèi)用、通過(guò)能力權(quán)可以代表距離、費(fèi)用、通過(guò)能力(容量容量)等等。等等。端點(diǎn)無(wú)序的賦權(quán)圖稱為端點(diǎn)無(wú)序的賦權(quán)圖稱為無(wú)向網(wǎng)絡(luò)無(wú)向網(wǎng)絡(luò)，端點(diǎn)有序的賦權(quán)圖稱為，端點(diǎn)有序的賦權(quán)圖稱為有有向網(wǎng)絡(luò)。向網(wǎng)絡(luò)。910201571419256Page 12 出次與入次出次與入次 有向圖中，以有向圖中，以vi為始點(diǎn)的邊數(shù)稱為點(diǎn)為始點(diǎn)的邊數(shù)稱為點(diǎn)vi的的出次出次，用，用d+(vi)表表示；以示；以vi為終點(diǎn)的邊數(shù)稱為點(diǎn)為終點(diǎn)的邊數(shù)稱為點(diǎn)vi 的的入次入次，用表示，用表示d-(vi) ；vi 點(diǎn)點(diǎn)的出次和入次之和就是該點(diǎn)的次。的出次和入

9、次之和就是該點(diǎn)的次。 有向圖中，所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之有向圖中，所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。和。Page 13例例6.1 有甲有甲,乙乙,丙丙,丁丁,戊戊,己己6名運(yùn)動(dòng)員報(bào)名參加名運(yùn)動(dòng)員報(bào)名參加A,B,C,D,E,F 6個(gè)項(xiàng)目的比賽。下表中打個(gè)項(xiàng)目的比賽。下表中打的是各運(yùn)動(dòng)員報(bào)告參加的比賽項(xiàng)的是各運(yùn)動(dòng)員報(bào)告參加的比賽項(xiàng)目。問目。問6個(gè)項(xiàng)目的比賽順序應(yīng)如何安排，做到每名運(yùn)動(dòng)員都個(gè)項(xiàng)目的比賽順序應(yīng)如何安排，做到每名運(yùn)動(dòng)員都不連續(xù)地參加兩項(xiàng)比賽。不連續(xù)地參加兩項(xiàng)比賽。ABCDEF甲甲乙乙丙丙丁丁戊戊己己Page 14解：用圖來(lái)建模。把比賽項(xiàng)目作為研究對(duì)象，用點(diǎn)表示。如解

10、：用圖來(lái)建模。把比賽項(xiàng)目作為研究對(duì)象，用點(diǎn)表示。如果果2個(gè)項(xiàng)目有同一名運(yùn)動(dòng)員參加，在代表這兩個(gè)項(xiàng)目的點(diǎn)之個(gè)項(xiàng)目有同一名運(yùn)動(dòng)員參加，在代表這兩個(gè)項(xiàng)目的點(diǎn)之間連一條線，可得下圖。間連一條線，可得下圖。ABCDEF在圖中找到一個(gè)點(diǎn)序在圖中找到一個(gè)點(diǎn)序列，使得依次排列的列，使得依次排列的兩點(diǎn)不相鄰，即能滿兩點(diǎn)不相鄰，即能滿足要求。如：足要求。如：1) A,C,B,F,E,D2) D,E,F,B,C,APage 15一個(gè)班級(jí)的學(xué)生共計(jì)選修一個(gè)班級(jí)的學(xué)生共計(jì)選修A、B、C、D、E、F六門六門課程，其中一部分人同時(shí)選修課程，其中一部分人同時(shí)選修D(zhuǎn)、C、A，一部分人同時(shí)，一部分人同時(shí)選修選修B、C、F，一部分

11、人同時(shí)選修，一部分人同時(shí)選修B、E，還有一部分人，還有一部分人同時(shí)選修同時(shí)選修A、B，期終考試要求每天考一門課，六天內(nèi)考，期終考試要求每天考一門課，六天內(nèi)考完，為了減輕學(xué)生負(fù)擔(dān)，要求每人都不會(huì)連續(xù)參加考試，完，為了減輕學(xué)生負(fù)擔(dān)，要求每人都不會(huì)連續(xù)參加考試，試設(shè)計(jì)一個(gè)考試日程表。試設(shè)計(jì)一個(gè)考試日程表。Page 16以每門課程為一個(gè)頂點(diǎn)，共同被選修的課程之間用邊相以每門課程為一個(gè)頂點(diǎn)，共同被選修的課程之間用邊相連，得圖，按題意，相鄰頂點(diǎn)對(duì)應(yīng)課程不能連續(xù)考試，不相連，得圖，按題意，相鄰頂點(diǎn)對(duì)應(yīng)課程不能連續(xù)考試，不相鄰頂點(diǎn)對(duì)應(yīng)課程允許連續(xù)考試，因此，作圖的補(bǔ)圖，問題是鄰頂點(diǎn)對(duì)應(yīng)課程允許連續(xù)考試，因此，

12、作圖的補(bǔ)圖，問題是在圖中尋找一條哈密頓道路，如在圖中尋找一條哈密頓道路，如，就，就是一個(gè)符合要求的考試課程表。是一個(gè)符合要求的考試課程表。Page 17Page 18Page 19定理定理1 任何圖中，頂點(diǎn)次數(shù)之和等于所有邊數(shù)的任何圖中，頂點(diǎn)次數(shù)之和等于所有邊數(shù)的2倍。倍。定理定理2 任何圖中，次為奇數(shù)的頂點(diǎn)必為偶數(shù)個(gè)。任何圖中，次為奇數(shù)的頂點(diǎn)必為偶數(shù)個(gè)。證明：由于每條邊必與兩個(gè)頂點(diǎn)關(guān)聯(lián)，在計(jì)算點(diǎn)的次時(shí)，每條邊證明：由于每條邊必與兩個(gè)頂點(diǎn)關(guān)聯(lián)，在計(jì)算點(diǎn)的次時(shí)，每條邊均被計(jì)算了兩次，所以頂點(diǎn)次數(shù)的總和等于邊數(shù)的均被計(jì)算了兩次，所以頂點(diǎn)次數(shù)的總和等于邊數(shù)的2倍。倍。證明：設(shè)證明：設(shè)V1和和V2分別

13、為圖分別為圖G中奇點(diǎn)與偶點(diǎn)的集合。由定理中奇點(diǎn)與偶點(diǎn)的集合。由定理1可得：可得：mvdvdvdVvVvVv2)()()(21 2m為偶數(shù)，且偶點(diǎn)的次之和為偶數(shù)，且偶點(diǎn)的次之和 也為偶數(shù)，所以也為偶數(shù)，所以 必為偶必為偶數(shù)，即奇數(shù)點(diǎn)的個(gè)數(shù)必為偶數(shù)。數(shù)，即奇數(shù)點(diǎn)的個(gè)數(shù)必為偶數(shù)。 2)(Vvvd 1)(VvvdPage 20圖的矩陣描述：圖的矩陣描述：如何在計(jì)算機(jī)中存儲(chǔ)一個(gè)圖呢？現(xiàn)在已有很多存儲(chǔ)的方法，如何在計(jì)算機(jī)中存儲(chǔ)一個(gè)圖呢？現(xiàn)在已有很多存儲(chǔ)的方法，但最基本的方法就是采用矩陣來(lái)表示一個(gè)圖，圖的矩陣表示但最基本的方法就是采用矩陣來(lái)表示一個(gè)圖，圖的矩陣表示也根據(jù)所關(guān)心的問題不同而有：也根據(jù)所關(guān)心的問

14、題不同而有：鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。1. 鄰接矩陣鄰接矩陣對(duì)于圖對(duì)于圖G=（V，E），），| V |=n， | E |=m，有，有n n階方階方矩陣矩陣A=(aij) n n，其中其中 其它其它之間有關(guān)聯(lián)邊時(shí)之間有關(guān)聯(lián)邊時(shí)與與當(dāng)且僅檔當(dāng)且僅檔0vv1jiijaPage 21v5v1v2v3v4v64332256437 010101101001010111101010001101111010 65432166654321 vvvvvvAvvvvvv例例6.2 下圖所表示的圖可以構(gòu)造鄰接矩陣下圖所表示的圖可以構(gòu)造鄰接矩陣A如下如下Page 22對(duì)于賦權(quán)圖對(duì)于賦權(quán)

15、圖G=(V,E), 其中邊其中邊 有權(quán)有權(quán) , 構(gòu)造矩陣構(gòu)造矩陣B=(bij) n n 其中：其中：對(duì)于圖對(duì)于圖G=(V,E), | V |=n, | E |=m, 有有m n階階矩陣矩陣M=(mij) m n，其中其中: 其他其他的一個(gè)端點(diǎn)的一個(gè)端點(diǎn)是邊是邊當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)?shù)膬蓚€(gè)端點(diǎn)的兩個(gè)端點(diǎn)是邊是邊當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)0ev1ev2jijiijm),(jivvjiw EvvEvvwbjijijiji),(0),(Page 231 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0

16、1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0v1v2v3v4v5v6v7v8e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例例6.3 下圖所表示的圖可以構(gòu)造鄰接矩陣下圖所表示的圖可以構(gòu)造鄰接矩陣M如下如下:M=（mij）=Page 24654321654321 030303302004020576305020007204346

17、040vvvvvvvvvvvvB v5v1v2v3v4v64332256437例例6.4 下圖所表示的圖可以構(gòu)造權(quán)矩陣下圖所表示的圖可以構(gòu)造權(quán)矩陣B如下如下:Page 25樹是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)領(lǐng)樹是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)領(lǐng)域應(yīng)用極為廣泛。域應(yīng)用極為廣泛。例例6.2 乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如乒乓求單打比賽抽簽后，可用圖來(lái)表示相遇情況，如下圖所示。下圖所示。AB CDEF GH運(yùn)動(dòng)員運(yùn)動(dòng)員Page 26例例6.3 某企業(yè)的組織機(jī)構(gòu)圖也可用樹圖表示。某企業(yè)的組織機(jī)構(gòu)圖也可用樹圖表示。廠長(zhǎng)廠長(zhǎng)人事科人事科財(cái)務(wù)科財(cái)務(wù)科總工總工程

18、師程師生產(chǎn)副生產(chǎn)副廠長(zhǎng)廠長(zhǎng)經(jīng)營(yíng)副經(jīng)營(yíng)副廠長(zhǎng)廠長(zhǎng)開發(fā)科開發(fā)科技術(shù)科技術(shù)科生產(chǎn)科生產(chǎn)科設(shè)備科設(shè)備科供應(yīng)科供應(yīng)科銷售科銷售科檢驗(yàn)科檢驗(yàn)科動(dòng)力科動(dòng)力科Page 27 樹：無(wú)圈的連通圖即為樹樹：無(wú)圈的連通圖即為樹性質(zhì)性質(zhì)1：任何樹中必存在次為：任何樹中必存在次為1的點(diǎn)。的點(diǎn)。性質(zhì)性質(zhì)2：n 個(gè)頂點(diǎn)的樹必有個(gè)頂點(diǎn)的樹必有n-1 條邊。條邊。性質(zhì)性質(zhì)3：樹中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。：樹中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。性質(zhì)性質(zhì)4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。性質(zhì)性質(zhì)5：樹無(wú)回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，?。簶錈o(wú)回圈，但不相鄰的兩個(gè)點(diǎn)之間

19、加一條邊，恰得到一個(gè)圈。得到一個(gè)圈。v1v2v3v4v5v6Page 28 圖的最小部分樹圖的最小部分樹(支撐樹支撐樹)如果如果G2是是G1的部分圖，又是樹圖，則稱的部分圖，又是樹圖，則稱G2是是G1的部分樹的部分樹（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖G1含有多含有多個(gè)部分樹，其中樹枝總長(zhǎng)最小的部分樹，稱為該圖的最小個(gè)部分樹，其中樹枝總長(zhǎng)最小的部分樹，稱為該圖的最小部分樹（或最小支撐樹）。部分樹（或最小支撐樹）。v1v2v3v4v5v1v2v3v4v5G1G2Page 29Page 30Page 31Page 32Page 33Page 34Pa

20、ge 35部分樹部分樹Page 36v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5Page 37破圈法破圈法：任取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈。：任取一圈，去掉圈中最長(zhǎng)邊，直到無(wú)圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521邊數(shù)邊數(shù)n-1=5Page 38v1v2v3v4v5v643521得到最小樹：得到最小樹：Min C(T)=15Page 39避圈法避圈法:去掉去掉G中所有邊，得到中所有邊，得到n個(gè)孤立點(diǎn)；然后加邊。個(gè)孤立點(diǎn)；然后加邊。加邊的原則為：從最短邊開始添加，加邊的過(guò)程中不能形成加邊的原

21、則為：從最短邊開始添加，加邊的過(guò)程中不能形成圈，直到點(diǎn)點(diǎn)連通圈，直到點(diǎn)點(diǎn)連通(即即:n-1條邊條邊)。5v1v2v3v4v5v6843752618Page 40v1v2v3v4v5v6435215v1v2v3v4v5v6843752618Min C(T)=15Page 41Page 42Page 43Page 44Page 45Page 46Page 47Page 48Page 49Page 50Page 51Page 52Page 53Page 54Page 55Page 56Page 57Page 58Page 59Page 60Page 613749346321Min C(T)=12Mi

22、n C(T)=15254173314475答案：答案：Page 6234122323242Min C(T)=12213638534567454321Min C(T)=18Page 63如何用最短的線路將三部電話連起來(lái)？如何用最短的線路將三部電話連起來(lái)？此問題可抽象為設(shè)此問題可抽象為設(shè)ABC為等邊三角形，連接三頂點(diǎn)的為等邊三角形，連接三頂點(diǎn)的路線（稱為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個(gè)，其中最短路線者顯路線（稱為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個(gè)，其中最短路線者顯然是二邊之和（如然是二邊之和（如ABAC）。）。ABCPage 64ABCP但若增加一個(gè)周轉(zhuǎn)站（新點(diǎn)但若增加一個(gè)周轉(zhuǎn)站（新點(diǎn)P），連接），連接4點(diǎn)的新網(wǎng)絡(luò)

23、的最短路點(diǎn)的新網(wǎng)絡(luò)的最短路線為線為PAPBPC。最短新路徑之長(zhǎng)。最短新路徑之長(zhǎng)N比原來(lái)只連三點(diǎn)的最比原來(lái)只連三點(diǎn)的最短路徑短路徑O要短。這樣得到的網(wǎng)絡(luò)不僅比原來(lái)節(jié)省材料，而且要短。這樣得到的網(wǎng)絡(luò)不僅比原來(lái)節(jié)省材料，而且穩(wěn)定性也更好。穩(wěn)定性也更好。Page 65問題描述：?jiǎn)栴}描述：就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路距離最短的一條路 .有些問題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投有些問題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問題，也可以

24、歸結(jié)為求最短路的問題。因此這類問題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。路的問題。因此這類問題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。Page 66求最短路有兩種算法求最短路有兩種算法: 狄克斯屈拉狄克斯屈拉(Dijkstra)標(biāo)號(hào)算法標(biāo)號(hào)算法 逐次逼近算法逐次逼近算法Page 67若序列若序列 vs,v1.vn-1,vn 是從是從vs到到vt間的最短路，則序列間的最短路，則序列 vs,v1.vn-1 必為從必為從vs 到到vn-1的最短路。的最短路。假定假定v1v2 v3 v4是是v1 v4的最短路，則的最短路，則v1 v2 v3一定是一定是v1 v3的最短路，的最短路，v2 v3 v4也一定是也一定是v2 v4的最

25、短路。的最短路。v1v2v3v4v5Page 68求網(wǎng)絡(luò)圖的最短路，設(shè)圖的起點(diǎn)是求網(wǎng)絡(luò)圖的最短路，設(shè)圖的起點(diǎn)是vs,終點(diǎn)是終點(diǎn)是vt ,以以vi為起點(diǎn)為起點(diǎn)vj為終點(diǎn)的弧記為為終點(diǎn)的弧記為 (i, j) 距離為距離為dij：b(j) 起點(diǎn)起點(diǎn)vs到點(diǎn)到點(diǎn)vj的最短路長(zhǎng)；的最短路長(zhǎng)；： k(i,j)=b(i)+dij，步驟：步驟： 1. 令起點(diǎn)的標(biāo)號(hào)；令起點(diǎn)的標(biāo)號(hào)；b(s)0。 2. 找出所有找出所有vi已標(biāo)號(hào)已標(biāo)號(hào)vj未標(biāo)號(hào)的弧集合未標(biāo)號(hào)的弧集合 B=(i, j) 如果這樣的如果這樣的弧不存在或弧不存在或vt已標(biāo)號(hào)則計(jì)算結(jié)束；已標(biāo)號(hào)則計(jì)算結(jié)束；3. 計(jì)算集合計(jì)算集合B中弧中弧k(i，j)=b(

26、i)+dij的標(biāo)號(hào)的標(biāo)號(hào)4. 選一個(gè)點(diǎn)標(biāo)號(hào)選一個(gè)點(diǎn)標(biāo)號(hào) 在終點(diǎn)在終點(diǎn)vl處標(biāo)處標(biāo)號(hào)號(hào)b(l), 返回到第返回到第2步。步。 ,),( | ),(min)(Bjijiklbj Page 69例例6.5 求下圖求下圖v1到到v7的最短路長(zhǎng)及最短路線的最短路長(zhǎng)及最短路線86252353421057086225441114751071211v7已標(biāo)號(hào)，計(jì)算結(jié)束。從已標(biāo)號(hào)，計(jì)算結(jié)束。從v1到到v7的最短路長(zhǎng)是的最短路長(zhǎng)是 11,最短路線：最短路線： v1 v4 v6 v7P標(biāo)號(hào)標(biāo)號(hào)T標(biāo)號(hào)標(biāo)號(hào)Page 70從上例知，只要某點(diǎn)已標(biāo)號(hào)，說(shuō)明已找到起點(diǎn)從上例知，只要某點(diǎn)已標(biāo)號(hào)，說(shuō)明已找到起點(diǎn)vs到到該點(diǎn)的最短路

27、線及最短距離，因此可以將每個(gè)點(diǎn)標(biāo)該點(diǎn)的最短路線及最短距離，因此可以將每個(gè)點(diǎn)標(biāo)號(hào)，求出號(hào)，求出vs到任意點(diǎn)的最短路線，如果某個(gè)點(diǎn)到任意點(diǎn)的最短路線，如果某個(gè)點(diǎn)vj不能不能標(biāo)號(hào)，說(shuō)明標(biāo)號(hào)，說(shuō)明vs不可達(dá)不可達(dá)vj 。注：無(wú)向圖最短路的求法只將上述步驟注：無(wú)向圖最短路的求法只將上述步驟2將弧改成邊即可。將弧改成邊即可。Page 71例例6.6 求下圖求下圖v1到各點(diǎn)的最短距離及最短路線。到各點(diǎn)的最短距離及最短路線。4526178393261216180452231039612641166188122482418所有點(diǎn)都已標(biāo)號(hào)，點(diǎn)上的標(biāo)號(hào)就是所有點(diǎn)都已標(biāo)號(hào)，點(diǎn)上的標(biāo)號(hào)就是v1到該點(diǎn)的最短距離，最短到該

28、點(diǎn)的最短距離，最短路線就是紅色的鏈。路線就是紅色的鏈。Page 72課堂練習(xí)：課堂練習(xí)：1. 用用Dijkstra算法求下圖從算法求下圖從v1到到v6的最短距離及路線。的最短距離及路線。v3v54v1v2v4v635222421v1到到v6的最短路為：的最短路為：6521vvvvPage 732. 求從求從v1到到v8的最短路徑的最短路徑237184566134105275934682Page 74237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路徑為的最短路徑為v1v4v7v5v8，最短距離為，最短距離為10

29、Page 753. 求下圖中求下圖中v1點(diǎn)到另外任意一點(diǎn)的最短路徑點(diǎn)到另外任意一點(diǎn)的最短路徑v1v2v3v4v6v5322762133Page 76v1V2V3V4 V6V5322762133024714Page 77v1V2V3V4 V6V5322762133024714Page 78算法適用條件：算法適用條件：Dijkstra算法只適用于全部權(quán)為非負(fù)情況，如果某算法只適用于全部權(quán)為非負(fù)情況，如果某邊上權(quán)為負(fù)的，算法失效。此時(shí)可采用逐次逼近邊上權(quán)為負(fù)的，算法失效。此時(shí)可采用逐次逼近算法。算法。例例6.7 如右圖所示中按如右圖所示中按dijkstra算算法可得法可得P(v1)=5為從為從vsv

30、1的最短的最短路長(zhǎng)顯然是錯(cuò)誤的，從路長(zhǎng)顯然是錯(cuò)誤的，從vsv2v1路長(zhǎng)只有路長(zhǎng)只有3。v2vsv15-58Page 79最短路問題的應(yīng)用：最短路問題的應(yīng)用：例例6.7 電信公司準(zhǔn)備準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，電信公司準(zhǔn)備準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長(zhǎng)度（單位：公里）。通圖。權(quán)數(shù)表示兩地間公路的長(zhǎng)度（單位：公里）。 v1 （甲地）（甲地）1517624431065v2v7 (乙地乙地)v3v4v5v6Page 80例例6.8 設(shè)備更新問題。某公司使用一

31、臺(tái)設(shè)備，在每年年初，設(shè)備更新問題。某公司使用一臺(tái)設(shè)備，在每年年初，公司就要決定是購(gòu)買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購(gòu)公司就要決定是購(gòu)買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購(gòu)置新設(shè)備，就要支付一定的購(gòu)置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用置新設(shè)備，就要支付一定的購(gòu)置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購(gòu)置費(fèi)，但維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購(gòu)置費(fèi)，但維修費(fèi)用就高了。請(qǐng)?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年就高了。請(qǐng)?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年內(nèi)購(gòu)置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。已知：內(nèi)購(gòu)置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小。已知：設(shè)備每年年初的價(jià)格表設(shè)備每年年

32、初的價(jià)格表年份年份12345年初價(jià)格年初價(jià)格1111121213Page 81設(shè)備維修費(fèi)如下表設(shè)備維修費(fèi)如下表使用年數(shù)使用年數(shù)0-11-22-33-44-5每年維修費(fèi)用每年維修費(fèi)用5681118解：解：將問題轉(zhuǎn)化為最短路問題，如下圖：用將問題轉(zhuǎn)化為最短路問題，如下圖：用vi表示表示“第第i年年年年初購(gòu)進(jìn)一臺(tái)新設(shè)備初購(gòu)進(jìn)一臺(tái)新設(shè)備”,弧（?。╲i,vj）表示第）表示第i年年初購(gòu)進(jìn)的設(shè)備一年年初購(gòu)進(jìn)的設(shè)備一直使用到第直使用到第j年年初。年年初。v1v2v3v4v5v6Page 82把所有弧的權(quán)數(shù)計(jì)算如下表，把所有弧的權(quán)數(shù)計(jì)算如下表，把權(quán)數(shù)賦到圖中，再用把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短

33、路。算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v6162230415916223041312317181723Page 83 最終得到下圖，可知，最終得到下圖，可知，v1到到v6的距離是的距離是53，最短路徑有兩條：，最短路徑有兩條： v1v3v6和和 v1v4v6 V1（0,s）v3v4(41,1) v5v62230415916(22,1)3041312317181723 V2（16,1）16(30,1)(53,3)(53,4)Page 84如何制定一個(gè)運(yùn)輸計(jì)劃使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。如何制定一個(gè)運(yùn)輸計(jì)劃使

34、生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個(gè)網(wǎng)絡(luò)最大流問題。這就是一個(gè)網(wǎng)絡(luò)最大流問題。Page 85基本概念：基本概念：對(duì)網(wǎng)絡(luò)上的每條弧對(duì)網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個(gè)最大的通都給出一個(gè)最大的通過(guò)能力，稱為該弧的過(guò)能力，稱為該弧的，簡(jiǎn)記為，簡(jiǎn)記為cij。容量網(wǎng)絡(luò)中通常規(guī)定。容量網(wǎng)絡(luò)中通常規(guī)定一個(gè)一個(gè)(也稱源點(diǎn)，記為也稱源點(diǎn)，記為s)和一個(gè)和一個(gè)(也稱匯點(diǎn)，記為也稱匯點(diǎn)，記為t)，網(wǎng)絡(luò)中其他點(diǎn)稱為網(wǎng)絡(luò)中其他點(diǎn)稱為。st4844122679Page 862. 網(wǎng)絡(luò)的最大流網(wǎng)絡(luò)的最大流是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過(guò)的最大流量。是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過(guò)的最大流量。3. 流與可行流流

35、與可行流 流流是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對(duì)加在弧是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對(duì)加在弧(vi,vj)上上的負(fù)載量記為的負(fù)載量記為fij。若。若fij=0，稱為零流。，稱為零流。滿足以下條件的一組流稱為滿足以下條件的一組流稱為可行流可行流。 容量限制條件。容量網(wǎng)絡(luò)上所有的弧滿足：容量限制條件。容量網(wǎng)絡(luò)上所有的弧滿足：0fijcij 中間點(diǎn)平衡條件。中間點(diǎn)平衡條件。),(0),(),(tsivvfvvfijji 若以若以v(f)表示網(wǎng)絡(luò)中從表示網(wǎng)絡(luò)中從st的流量，則有：的流量，則有： 0),(),()(tjjsvvfvvffvPage 87結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。（零流即是結(jié)論：任

36、何網(wǎng)絡(luò)上一定存在可行流。（零流即是可行流）可行流）網(wǎng)絡(luò)最大流問題：網(wǎng)絡(luò)最大流問題：指滿足容量限制條件和中間點(diǎn)平衡的條件下，使指滿足容量限制條件和中間點(diǎn)平衡的條件下，使v(f)值達(dá)到最大。值達(dá)到最大。Page 88 割與割集割與割集割是指容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開，并使割是指容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開，并使st的流中斷的流中斷的一組的一組弧的集合弧的集合。割容量是組成割集合中的各條弧的容量之。割容量是組成割集合中的各條弧的容量之和，用和，用 表示。表示。),(VVc ),(),(),(),(VVjijivvcVVc如下圖中，如下圖中，AA將網(wǎng)絡(luò)上的點(diǎn)分割成將網(wǎng)絡(luò)上的點(diǎn)分割成 兩個(gè)集合。并兩個(gè)

37、集合。并有有 ，稱弧的集合，稱弧的集合(v1,v3),(v2,v4)是一個(gè)割，且是一個(gè)割，且 的流量為的流量為18。 VV ,VtVs ,VV Page 89v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AABBPage 90 設(shè)網(wǎng)絡(luò)設(shè)網(wǎng)絡(luò)N中一個(gè)從中一個(gè)從 s 到到 t 的流的流 f 的流量為的流量為v(f )， (V, V )為任意一個(gè)割集，則為任意一個(gè)割集，則 v(f ) = f(V, V ) f(V , V) 對(duì)網(wǎng)絡(luò)對(duì)網(wǎng)絡(luò) N中任意流量中任意流量v(f )和割集和割集 (V, V )，有，有v(f ) c(V, V )證明證明 w= f(V,

38、 V ) f(V , V) f(V, V ) c(V, V ) 最大流量最大流量v (f )不大于最小割集的容量，即：不大于最小割集的容量，即：v (f ) minc(V, V ) 在網(wǎng)絡(luò)中在網(wǎng)絡(luò)中st的最大流量等于它的最小割集的容量，的最大流量等于它的最小割集的容量，即：即： v (f ) = c (V, V ) Page 91在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈，在該鏈上所有在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈，在該鏈上所有指向?yàn)橹赶驗(yàn)閟t的弧，稱為前向弧，記作的弧，稱為前向弧，記作+,存在存在f0，則稱這樣的鏈為，則稱這樣的鏈為增廣鏈。增廣鏈。例如下圖中，例如下圖中，sv2v1v3v4t。

39、網(wǎng)絡(luò)網(wǎng)絡(luò)N中的流中的流 f 是最大流當(dāng)且僅當(dāng)是最大流當(dāng)且僅當(dāng)N中不包含任何增廣中不包含任何增廣鏈鏈Page 92v1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)Page 93求網(wǎng)絡(luò)最大流的標(biāo)號(hào)算法：求網(wǎng)絡(luò)最大流的標(biāo)號(hào)算法：由一個(gè)流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，由一個(gè)流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個(gè)增流過(guò)程，直至不存在增廣鏈。繼續(xù)這個(gè)增流過(guò)程，直至不存在增廣鏈。(1)找出第一個(gè)可行流，（例如所有弧的流量找出第一個(gè)可行流，（例如所有弧的流量fij =0。）。）(2)用標(biāo)號(hào)的方法找一條增廣鏈用標(biāo)號(hào)的方法找一條增廣鏈 首先給發(fā)點(diǎn)

40、首先給發(fā)點(diǎn)s標(biāo)號(hào)標(biāo)號(hào)(),標(biāo)號(hào)中的數(shù)字表示允許的最大調(diào)整量。標(biāo)號(hào)中的數(shù)字表示允許的最大調(diào)整量。 選擇一個(gè)點(diǎn)選擇一個(gè)點(diǎn) vi 已標(biāo)號(hào)并且另一端未標(biāo)號(hào)的弧沿著某條鏈已標(biāo)號(hào)并且另一端未標(biāo)號(hào)的弧沿著某條鏈向收點(diǎn)檢查：向收點(diǎn)檢查：Page 94 如果弧的起點(diǎn)為如果弧的起點(diǎn)為vi，并且有，并且有fij0，則，則vj標(biāo)號(hào)標(biāo)號(hào)(fji)(3) 重復(fù)第重復(fù)第(2)步，可能出現(xiàn)兩種結(jié)局：步，可能出現(xiàn)兩種結(jié)局： 標(biāo)號(hào)過(guò)程中斷，標(biāo)號(hào)過(guò)程中斷，t無(wú)法標(biāo)號(hào)，說(shuō)明網(wǎng)絡(luò)中不存在增廣鏈，無(wú)法標(biāo)號(hào)，說(shuō)明網(wǎng)絡(luò)中不存在增廣鏈，目前流量為最大流。同時(shí)可以確定最小割集，目前流量為最大流。同時(shí)可以確定最小割集，記已標(biāo)號(hào)的點(diǎn)記已標(biāo)號(hào)的點(diǎn)集為

41、集為V,未標(biāo)號(hào)的點(diǎn)集合為未標(biāo)號(hào)的點(diǎn)集合為V,(V,V)為網(wǎng)絡(luò)的最小割。為網(wǎng)絡(luò)的最小割。 t得到標(biāo)號(hào)，反向追蹤在網(wǎng)絡(luò)中找到一條從得到標(biāo)號(hào)，反向追蹤在網(wǎng)絡(luò)中找到一條從s到到t得由標(biāo)號(hào)得由標(biāo)號(hào)點(diǎn)及相應(yīng)的弧連接而成的增廣鏈。繼續(xù)第點(diǎn)及相應(yīng)的弧連接而成的增廣鏈。繼續(xù)第(4)步步Page 95 所所有有非非增增廣廣鏈鏈上上的的弧弧對(duì)對(duì)增增廣廣鏈鏈上上所所有有后后向向弧弧對(duì)對(duì)增增廣廣鏈鏈上上所所有有前前向向弧弧ftftff)()(4) 修改流量。設(shè)原圖可行流為修改流量。設(shè)原圖可行流為f，令，令得到網(wǎng)絡(luò)上一個(gè)新的可行流得到網(wǎng)絡(luò)上一個(gè)新的可行流f。(5) 擦除圖上所有標(biāo)號(hào)，重復(fù)擦除圖上所有標(biāo)號(hào)，重復(fù)(1)-(4

42、)步，直到圖中找不到任何步，直到圖中找不到任何增廣鏈，計(jì)算結(jié)束。增廣鏈，計(jì)算結(jié)束。Page 96例例6.10 用標(biāo)號(hào)算法求下圖中用標(biāo)號(hào)算法求下圖中st的最大流量，并找出最小割。的最大流量，并找出最小割。v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)Page 97解：解：(1) 先給先給s標(biāo)號(hào)標(biāo)號(hào)()v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()Page 98v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(2) 檢查與檢查與s點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因點(diǎn)相鄰的未

43、標(biāo)號(hào)的點(diǎn)，因fs1cs1，故對(duì)，故對(duì)v1標(biāo)號(hào)標(biāo)號(hào)=min, cs1-fs1=1,)1( (1)Page 99v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(6)()(1)(2) 檢查與檢查與v1點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因f13c13，故對(duì)，故對(duì)v3標(biāo)號(hào)標(biāo)號(hào)=min1, c13-f13= min1, 6= 1)3( (1)Page 100v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(1)(1)(3) 檢查與檢查與v3點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)，因f3tc3t，故對(duì)，故對(duì)vt標(biāo)號(hào)

44、標(biāo)號(hào)=min1, c3t-f3t= min1, 1= 1)(t (1)找到一條增廣鏈找到一條增廣鏈sv1v3tPage 101(4) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流?？尚辛鳌1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)()(1)(1)(1)11 sf113 f13 tfPage 102(5) 擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過(guò)程，尋找另外的增廣鏈。擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過(guò)程，尋找另外的增廣鏈。v1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7

45、(5)()(1)(1)(1)Page 103(5) 擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過(guò)程，尋找另外的增廣鏈。擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過(guò)程，尋找另外的增廣鏈。v1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)()(2)(2)=min,2=2(2)(1)=min2,3=2(3)=min2,5=2(2)(1)(4)=min2,1=1(1)(t)=min1,2=1Page 104(6) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流?？尚辛鳌1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)

46、9(9)5(3)7(5)()(2)(2)(2)(1)(1)12 sf121 f113 f134 f14 tfPage 105v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(2)(2)(2)(1)(1)(7) 擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過(guò)程，尋找另外的增廣鏈。擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過(guò)程，尋找另外的增廣鏈。Page 106v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(1)(1)(1)(7) 擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過(guò)程，尋找另外的增廣鏈。擦除所有標(biāo)號(hào)，重復(fù)上述標(biāo)號(hào)過(guò)程，尋找另外的增廣鏈。(2)=

47、min,1=1(1)=min1,2=1(3)=min1,4=1,4321VVtvVvvvsV 最小割為最小割為Page 107例例6.9 求下圖求下圖st的最大流，并找出最小割的最大流，并找出最小割stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)Page 108stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)解解: (1) 在已知可行流的基礎(chǔ)上，通過(guò)標(biāo)號(hào)尋找增廣鏈。在已知可行流的基礎(chǔ)上，通過(guò)標(biāo)號(hào)尋找增廣鏈。()(2)=min,6=6(6)(3)=min6,2=2(2)(t)=min2,5=2(2)Page 109(2) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流?？尚辛?。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2