圖及網絡分析(4課時)起訖點不同最短路最大流問題

1、圖的基本概念與模型圖的基本概念與模型樹與圖的最小樹樹與圖的最小樹最短路問題最短路問題網絡的最大流網絡的最大流Page 3近代圖論的歷史可追溯到近代圖論的歷史可追溯到18世紀的七橋問題世紀的七橋問題穿過穿過Knigsberg城的七座橋，要求每座橋通過一次且僅通過一次。城的七座橋，要求每座橋通過一次且僅通過一次。 這就是著名的這就是著名的“哥尼斯堡哥尼斯堡 7 橋橋”難題。難題。Euler1736年證明了不年證明了不可能存在這樣的路線。可能存在這樣的路線。Page 4圖論中圖是由點和邊構成，可以反映一些對象之間的關系。圖論中圖是由點和邊構成，可以反映一些對象之間的關系。一般情況下圖中點的相對位置如

2、何、點與點之間聯(lián)線的長短一般情況下圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，對于反映對象之間的關系并不是重要的。曲直，對于反映對象之間的關系并不是重要的。若用點表示研究的對象，用邊表示這些對象之間的聯(lián)系，若用點表示研究的對象，用邊表示這些對象之間的聯(lián)系，則圖則圖G可以定義為點和邊的集合，記作：可以定義為點和邊的集合，記作：,EVG 其中其中: V點集點集 E邊集邊集 圖圖G區(qū)別于幾何學中的圖。這里只關心圖中有多少個點以區(qū)別于幾何學中的圖。這里只關心圖中有多少個點以及哪些點之間有連線。及哪些點之間有連線。Page 5(v1)趙趙(v2)錢錢孫孫(v3) 李李(v4)周周(v5)吳吳(v6)

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

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

5、重邊的圖，對無環(huán)、無多重邊的圖稱作稱作簡單圖簡單圖。v3e7e4e8e5e6e1e2e3v1v2v4v5Page 8 次，奇點，偶點，孤立點次，奇點，偶點，孤立點與某一個點與某一個點vi相關聯(lián)的邊的數目稱為相關聯(lián)的邊的數目稱為點點vi的的次次（也叫做度），記作（也叫做度），記作d(vi)。右圖中右圖中d(v1),d(v3)=5,d(v5)=1。次。次為奇數的點稱作為奇數的點稱作奇點奇點，次為偶數的，次為偶數的點稱作點稱作偶點偶點，次為，次為1的點稱為的點稱為懸掛點懸掛點，次為次為0的點稱作的點稱作孤立點孤立點。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的次圖的次: 一個圖的次等于各

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

7、、E1和圖和圖G2=V2，E2如果有如果有 稱稱G1是是G2的一個的一個子圖子圖。若有若有 ，則稱，則稱G1是是G2的一的一個個部分圖部分圖(支撐子圖支撐子圖)。2121EEVV 和和2121EEVV ，v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G圖）圖）Page 11 網絡（賦權圖）網絡（賦權圖）設圖設圖G（V，E），對），對G的每一條邊的每一條邊(vi,vj)相應賦予數量指標相應賦予數量指標wij，wij稱為邊稱為邊(vi,vj)的的權權,賦予權的圖賦予權的圖G稱為網絡稱為網絡(或或賦權圖）

8、賦權圖）。權可以代表距離、費用、通過能力權可以代表距離、費用、通過能力(容量容量)等等。等等。端點無序的賦權圖稱為端點無序的賦權圖稱為無向網絡無向網絡，端點有序的賦權圖稱為，端點有序的賦權圖稱為有有向網絡。向網絡。910201571419256Page 12 出次與入次出次與入次 有向圖中，以有向圖中，以vi為始點的邊數稱為點為始點的邊數稱為點vi的的出次出次，用，用d+(vi)表表示；以示；以vi為終點的邊數稱為點為終點的邊數稱為點vi 的的入次入次，用表示，用表示d-(vi) ；vi 點點的出次和入次之和就是該點的次。的出次和入次之和就是該點的次。 有向圖中，所有頂點的入次之和等于所有頂點

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

10、有同一名運動員參加，在代表這兩個項目的點之個項目有同一名運動員參加，在代表這兩個項目的點之間連一條線，可得下圖。間連一條線，可得下圖。ABCDEF在圖中找到一個點序在圖中找到一個點序列，使得依次排列的列，使得依次排列的兩點不相鄰，即能滿兩點不相鄰，即能滿足要求。如：足要求。如：1) A,C,B,F,E,D2) D,E,F,B,C,APage 15一個班級的學生共計選修一個班級的學生共計選修A、B、C、D、E、F六六門課程，其中一部分人同時選修門課程，其中一部分人同時選修D、C、A，一部分人同，一部分人同時選修時選修B、C、F，一部分人同時選修，一部分人同時選修B、E，還有一部分，還有一部分人同

11、時選修人同時選修A、B，期終考試要求每天考一門課，六天內，期終考試要求每天考一門課，六天內考完，為了減輕學生負擔，要求每人都不會連續(xù)參加考考完，為了減輕學生負擔，要求每人都不會連續(xù)參加考試，試設計一個考試日程表。試，試設計一個考試日程表。Page 16以每門課程為一個頂點，共同被選修的課程之間用邊以每門課程為一個頂點，共同被選修的課程之間用邊相連，得圖，按題意，相鄰頂點對應課程不能連續(xù)考試，不相連，得圖，按題意，相鄰頂點對應課程不能連續(xù)考試，不相鄰頂點對應課程允許連續(xù)考試，因此，作圖的補圖，問題相鄰頂點對應課程允許連續(xù)考試，因此，作圖的補圖，問題是在圖中尋找一條哈密頓道路，如是在圖中尋找一條哈

12、密頓道路，如，就是一個符合要求的考試課程表。就是一個符合要求的考試課程表。Page 17Page 18Page 19定理定理1 任何圖中，頂點次數之和等于所有邊數的任何圖中，頂點次數之和等于所有邊數的2倍。倍。定理定理2 任何圖中，次為奇數的頂點必為偶數個。任何圖中，次為奇數的頂點必為偶數個。證明：由于每條邊必與兩個頂點關聯(lián)，在計算點的次時，每條邊證明：由于每條邊必與兩個頂點關聯(lián)，在計算點的次時，每條邊均被計算了兩次，所以頂點次數的總和等于邊數的均被計算了兩次，所以頂點次數的總和等于邊數的2倍。倍。證明：設證明：設V1和和V2分別為圖分別為圖G中奇點與偶點的集合。由定理中奇點與偶點的集合。由定

13、理1可得：可得：mvdvdvdVvVvVv2)()()(21 2m為偶數，且偶點的次之和為偶數，且偶點的次之和 也為偶數，所以也為偶數，所以 必為偶必為偶數，即奇數點的個數必為偶數。數，即奇數點的個數必為偶數。 2)(Vvvd 1)(VvvdPage 20圖的矩陣描述：圖的矩陣描述：如何在計算機中存儲一個圖呢？現在已有很多存儲的方法，如何在計算機中存儲一個圖呢？現在已有很多存儲的方法，但最基本的方法就是采用矩陣來表示一個圖，圖的矩陣表示但最基本的方法就是采用矩陣來表示一個圖，圖的矩陣表示也根據所關心的問題不同而有：也根據所關心的問題不同而有：鄰接矩陣、關聯(lián)矩陣、權矩陣等。鄰接矩陣、關聯(lián)矩陣、權

14、矩陣等。1. 鄰接矩陣鄰接矩陣對于圖對于圖G=（V，E），），| V |=n， | E |=m，有，有n n階方矩陣階方矩陣A=(aij) n n，其中，其中 其其它它之之間間有有關關聯(lián)聯(lián)邊邊時時與與當當且且僅僅檔檔0vv1jiijaPage 21v5v1v2v3v4v64332256437 010101101001010111101010001101111010 65432166654321 vvvvvvAvvvvvv例例6.2 下圖所表示的圖可以構造鄰接矩陣下圖所表示的圖可以構造鄰接矩陣A如下如下Page 22對于賦權圖對于賦權圖G=(V,E), 其中邊其中邊 有權有權 , 構造矩陣構造矩

15、陣B=(bij) n n 其中：其中：對于圖對于圖G=(V,E), | V |=n, | E |=m, 有有m n階矩陣階矩陣M=(mij) m n，其中其中: 其他其他的一個端點的一個端點是邊是邊當且僅當當且僅當的兩個端點的兩個端點是邊是邊當且僅當當且僅當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 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00

16、 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 下圖所表示的圖可以構造鄰接矩陣下圖所表示的圖可以構造鄰接矩陣M如下如下:M=（mij）=Page 24654321654321 030303302004020576305020007204346040vvvvvvvvvvvvB v5v1v2v3v4v643

17、32256437例例6.4 下圖所表示的圖可以構造權矩陣下圖所表示的圖可以構造權矩陣B如下如下:Page 25樹是圖論中結構最簡單但又十分重要的圖。在自然和社會領樹是圖論中結構最簡單但又十分重要的圖。在自然和社會領域應用極為廣泛。域應用極為廣泛。例例6.2 乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如乒乓求單打比賽抽簽后，可用圖來表示相遇情況，如下圖所示。下圖所示。AB CDEF GH運動員運動員Page 26例例6.3 某企業(yè)的組織機構圖也可用樹圖表示。某企業(yè)的組織機構圖也可用樹圖表示。廠長廠長人事科人事科財務科財務科總工總工程師程師生產副生產副廠長廠長經營副經營副廠長廠長開發(fā)科開發(fā)科技術

18、科技術科生產科生產科設備科設備科供應科供應科銷售科銷售科檢驗科檢驗科動力科動力科Page 27 樹：無圈的連通圖即為樹樹：無圈的連通圖即為樹性質性質1：任何樹中必存在次為：任何樹中必存在次為1的點。的點。性質性質2：n 個頂點的樹必有個頂點的樹必有n-1 條邊。條邊。性質性質3：樹中任意兩個頂點之間，恰有且僅有一條鏈。：樹中任意兩個頂點之間，恰有且僅有一條鏈。性質性質4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。性質性質5：樹無回圈，但不相鄰的兩個點之間加一條邊，恰：樹無回圈，但不相鄰的兩個點之間加一條邊，恰得到一個圈。得到一個圈。v1v2v3v4v5v6P

19、age 28 圖的最小部分樹圖的最小部分樹(支撐樹支撐樹)如果如果G2是是G1的部分圖，又是樹圖，則稱的部分圖，又是樹圖，則稱G2是是G1的部分樹的部分樹（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖（或支撐樹）。樹圖的各條邊稱為樹枝，一般圖G1含有多含有多個部分樹，其中樹枝總長最小的部分樹，稱為該圖的最小個部分樹，其中樹枝總長最小的部分樹，稱為該圖的最小部分樹（或最小支撐樹）。部分樹（或最小支撐樹）。v1v2v3v4v5v1v2v3v4v5G1G2Page 29Page 30Page 31Page 32Page 33Page 34Page 35部分樹部分樹Page 36v1v2v3v4v5v6v

20、1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5Page 37破圈法破圈法：任取一圈，去掉圈中最長邊，直到無圈。：任取一圈，去掉圈中最長邊，直到無圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521邊數邊數n-1=5Page 38v1v2v3v4v5v643521得到最小樹：得到最小樹：Min C(T)=15Page 39避圈法避圈法:去掉去掉G中所有邊，得到中所有邊，得到n個孤立點；然后加邊。個孤立點；然后加邊。加邊的原則為：從最短邊開始添加，加邊的過程中不能形成加邊的原則為：從最短邊開始添加，加邊的過程中不能形成圈，直到點點連通圈

21、，直到點點連通(即即: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)=12Min C(T)=15254173314475答案：答案：Page

22、 6234122323242Min C(T)=12213638534567454321Min C(T)=18Page 63如何用最短的線路將三部電話連起來？如何用最短的線路將三部電話連起來？此問題可抽象為設此問題可抽象為設ABC為等邊三角形，連接三頂點的為等邊三角形，連接三頂點的路線（稱為網絡）。這種網絡有許多個，其中最短路線者顯路線（稱為網絡）。這種網絡有許多個，其中最短路線者顯然是二邊之和（如然是二邊之和（如ABAC）。）。ABCPage 64ABCP但若增加一個周轉站（新點但若增加一個周轉站（新點P），連接），連接4點的新網絡的最短路點的新網絡的最短路線為線為PAPBPC。最短新路徑之長

23、。最短新路徑之長N比原來只連三點的最比原來只連三點的最短路徑短路徑O要短。這樣得到的網絡不僅比原來節(jié)省材料，而且要短。這樣得到的網絡不僅比原來節(jié)省材料，而且穩(wěn)定性也更好。穩(wěn)定性也更好。Page 65問題描述：問題描述：就是從給定的網絡圖中找出一點到各點或任意兩點之就是從給定的網絡圖中找出一點到各點或任意兩點之間距離最短的一條路間距離最短的一條路 .有些問題，如選址、管道鋪設時的選線、設備更新、有些問題，如選址、管道鋪設時的選線、設備更新、投資、某些整數規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結為求最投資、某些整數規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結為求最短路的問題。因此這類問題在生產實際中得到廣泛應用。短路

24、的問題。因此這類問題在生產實際中得到廣泛應用。Page 66求最短路有兩種算法求最短路有兩種算法: 狄克斯屈拉狄克斯屈拉(Dijkstra)標號算法標號算法 逐次逼近算法逐次逼近算法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的最短路。的最短路。v1v2v3v4v5Page 68求網絡圖的最

25、短路，設圖的起點是求網絡圖的最短路，設圖的起點是vs,終點是終點是vt ,以以vi為起點為起點vj為終點的弧記為為終點的弧記為 (i, j) 距離為距離為dij：b(j) 起點起點vs到點到點vj的最短路長；的最短路長；： k(i,j)=b(i)+dij，步驟：步驟： 1. 令起點的標號；令起點的標號；b(s)0。 2. 找出所有找出所有vi已標號已標號vj未標號的弧集合未標號的弧集合 B=(i, j) 如果這樣的如果這樣的弧不存在或弧不存在或vt已標號則計算結束；已標號則計算結束；3. 計算集合計算集合B中弧中弧k(i，j)=b(i)+dij的標號的標號4. 選一個點標號選一個點標號 在終點

26、在終點vl處標處標號號b(l), 返回到第返回到第2步。步。 ,),( | ),(min)(Bjijiklbj Page 69例例6.5 求下圖求下圖v1到到v7的最短路長及最短路線的最短路長及最短路線86252353421057086225441114751071211v7已標號，計算結束。從已標號，計算結束。從v1到到v7的最短路長是的最短路長是 11,最短路線：最短路線： v1 v4 v6 v7P標號標號T標號標號Page 70從上例知，只要某點已標號，說明已找到起點從上例知，只要某點已標號，說明已找到起點vs到到該點的最短路線及最短距離，因此可以將每個點標該點的最短路線及最短距離，因此

27、可以將每個點標號，求出號，求出vs到任意點的最短路線，如果某個點到任意點的最短路線，如果某個點vj不能不能標號，說明標號，說明vs不可達不可達vj 。注：無向圖最短路的求法只將上述步驟注：無向圖最短路的求法只將上述步驟2將弧改成邊即可。將弧改成邊即可。Page 71例例6.6 求下圖求下圖v1到各點的最短距離及最短路線。到各點的最短距離及最短路線。4526178393261216180452231039612641166188122482418所有點都已標號，點上的標號就是所有點都已標號，點上的標號就是v1到該點的最短距離，最短到該點的最短距離，最短路線就是紅色的鏈。路線就是紅色的鏈。Page

28、 72課堂練習：課堂練習：1. 用用Dijkstra算法求下圖從算法求下圖從v1到到v6的最短距離及路線。的最短距離及路線。v3v54v1v2v4v635222421v1到到v6的最短路為：的最短路為：6521vvvvPage 732. 求從求從v1到到v8的最短路徑的最短路徑237184566134105275934682Page 74237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路徑為的最短路徑為v1v4v7v5v8，最短距離為，最短距離為10Page 753. 求下圖中求下圖中v1點到另外任意一點的最短

29、路徑點到另外任意一點的最短路徑v1v2v3v4v6v5322762133Page 76v1V2V3V4 V6V5322762133024714Page 77v1V2V3V4 V6V5322762133024714Page 78算法適用條件：算法適用條件：Dijkstra算法只適用于全部權為非負情況，如果某算法只適用于全部權為非負情況，如果某邊上權為負的，算法失效。此時可采用逐次逼近邊上權為負的，算法失效。此時可采用逐次逼近算法。算法。例例6.7 如右圖所示中按如右圖所示中按dijkstra算算法可得法可得P(v1)=5為從為從vsv1的最短的最短路長顯然是錯誤的，從路長顯然是錯誤的，從vsv2

30、v1路長只有路長只有3。v2vsv15-58Page 79最短路問題的應用：最短路問題的應用：例例6.7 電信公司準備準備在甲、乙兩地沿路架設一條光纜線，電信公司準備準備在甲、乙兩地沿路架設一條光纜線，問如何架設使其光纜線路最短？下圖給出了甲乙兩地間的交問如何架設使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權數表示兩地間公路的長度（單位：公里）。通圖。權數表示兩地間公路的長度（單位：公里）。 v1 （甲地）（甲地）1517624431065v2v7 (乙地乙地)v3v4v5v6Page 80例例6.8 設備更新問題。某公司使用一臺設備，在每年年初，設備更新問題。某公司使用一臺設備，在每年年

31、初，公司就要決定是購買新的設備還是繼續(xù)使用舊設備。如果購公司就要決定是購買新的設備還是繼續(xù)使用舊設備。如果購置新設備，就要支付一定的購置費，當然新設備的維修費用置新設備，就要支付一定的購置費，當然新設備的維修費用就低。如果繼續(xù)使用舊設備，可以省去購置費，但維修費用就低。如果繼續(xù)使用舊設備，可以省去購置費，但維修費用就高了。請設計一個五年之內的更新設備的計劃，使得五年就高了。請設計一個五年之內的更新設備的計劃，使得五年內購置費用和維修費用總的支付費用最小。已知：內購置費用和維修費用總的支付費用最小。已知：設備每年年初的價格表設備每年年初的價格表年份年份12345年初價格年初價格111112121

32、3Page 81設備維修費如下表設備維修費如下表使用年數使用年數0-11-22-33-44-5每年維修費用每年維修費用5681118解：解：將問題轉化為最短路問題，如下圖：用將問題轉化為最短路問題，如下圖：用vi表示表示“第第i年年年年初購進一臺新設備初購進一臺新設備”,?。ɑ。╲i,vj）表示第）表示第i年年初購進的設備一年年初購進的設備一直使用到第直使用到第j年年初。年年初。v1v2v3v4v5v6Page 82把所有弧的權數計算如下表，把所有弧的權數計算如下表，把權數賦到圖中，再用把權數賦到圖中，再用Dijkstra算法求最短路。算法求最短路。1234561162230415921622

33、30413172331417235186v1v2v3v4v5v6162230415916223041312317181723Page 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如何制定一個運輸計劃使生產地到銷售地的產品輸送量最大。如何制定一個運輸計劃使生產地到銷售地的產品輸送量最大。這就是一個網絡最大流問題。這就

34、是一個網絡最大流問題。Page 85基本概念：基本概念：對網絡上的每條弧對網絡上的每條弧(vi,vj)都給出一個最大的通都給出一個最大的通過能力，稱為該弧的過能力，稱為該弧的，簡記為，簡記為cij。容量網絡中通常規(guī)定。容量網絡中通常規(guī)定一個一個(也稱源點，記為也稱源點，記為s)和一個和一個(也稱匯點，記為也稱匯點，記為t)，網絡中其他點稱為網絡中其他點稱為。st4844122679Page 862. 網絡的最大流網絡的最大流是指網絡中從發(fā)點到收點之間允許通過的最大流量。是指網絡中從發(fā)點到收點之間允許通過的最大流量。3. 流與可行流流與可行流 流流是指加在網絡各條弧上的實際流量，對加在弧是指加在

35、網絡各條弧上的實際流量，對加在弧(vi,vj)上上的負載量記為的負載量記為fij。若。若fij=0，稱為零流。，稱為零流。滿足以下條件的一組流稱為滿足以下條件的一組流稱為可行流可行流。 容量限制條件。容量網絡上所有的弧滿足：容量限制條件。容量網絡上所有的弧滿足：0fijcij 中間點平衡條件。中間點平衡條件。),(0),(),(tsivvfvvfijji 若以若以v(f)表示網絡中從表示網絡中從st的流量，則有：的流量，則有： 0),(),()(tjjsvvfvvffvPage 87結論：任何網絡上一定存在可行流。（零流即是結論：任何網絡上一定存在可行流。（零流即是可行流）可行流）網絡最大流問

36、題：網絡最大流問題：指滿足容量限制條件和中間點平衡的條件下，使指滿足容量限制條件和中間點平衡的條件下，使v(f)值達到最大。值達到最大。Page 88 割與割集割與割集割是指容量網絡中的發(fā)點和收點分割開，并使割是指容量網絡中的發(fā)點和收點分割開，并使st的流中斷的流中斷的一組的一組弧的集合弧的集合。割容量是組成割集合中的各條弧的容量之。割容量是組成割集合中的各條弧的容量之和，用和，用 表示。表示。),(VVc ),(),(),(),(VVjijivvcVVc如下圖中，如下圖中，AA將網絡上的點分割成將網絡上的點分割成 兩個集合。并兩個集合。并有有 ，稱弧的集合，稱弧的集合(v1,v3),(v2,

37、v4)是一個割，且是一個割，且 的流量為的流量為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 設網絡設網絡N中一個從中一個從 s 到到 t 的流的流 f 的流量為的流量為v(f )， (V, V )為任意一個割集，則為任意一個割集，則 v(f ) = f(V, V ) f(V , V) 對網絡對網絡 N中任意流量中任意流量v(f )和割集和割集 (V, V )，有，有v(f ) c(V, V )證明證明 w= f(V, V ) f(V , V) f(V, V ) c(V, V )

38、 最大流量最大流量v (f )不大于最小割集的容量，即：不大于最小割集的容量，即：v (f ) minc(V, V ) 在網絡中在網絡中st的最大流量等于它的最小割集的容量，的最大流量等于它的最小割集的容量，即：即： v (f ) = c (V, V ) Page 91在網絡的發(fā)點和收點之間能找到一條鏈，在該鏈上所在網絡的發(fā)點和收點之間能找到一條鏈，在該鏈上所有指向為有指向為st的弧，稱為前向弧，記作的弧，稱為前向弧，記作+,存在存在f0，則稱這樣的鏈，則稱這樣的鏈為增廣鏈。例如下圖中，為增廣鏈。例如下圖中，sv2v1v3v4t。 網絡網絡N中的流中的流 f 是最大流當且僅當是最大流當且僅當N

39、中不包含任何增廣中不包含任何增廣鏈鏈Page 92v1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)Page 93求網絡最大流的標號算法：求網絡最大流的標號算法：由一個流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增由一個流開始，系統(tǒng)地搜尋增廣鏈，然后在此鏈上增流，繼續(xù)這個增流過程，直至不存在增廣鏈。流，繼續(xù)這個增流過程，直至不存在增廣鏈。找出第一個可行流，（例如所有弧的流量找出第一個可行流，（例如所有弧的流量fij =0。）。）用標號的方法找一條增廣鏈用標號的方法找一條增廣鏈 首先給發(fā)點首先給發(fā)點s標號標號(),標號中的數字表示允許的最大調整量。標號中的數字表

40、示允許的最大調整量。 選擇一個點選擇一個點 vi 已標號并且另一端未標號的弧沿著某條鏈向已標號并且另一端未標號的弧沿著某條鏈向收點檢查：收點檢查：Page 94 如果弧的起點為如果弧的起點為vi，并且有，并且有fij0，則，則vj標號標號(fji)(3) 重復第重復第(2)步，可能出現兩種結局：步，可能出現兩種結局： 標號過程中斷，標號過程中斷，t無法標號，說明網絡中不存在增廣鏈，目無法標號，說明網絡中不存在增廣鏈，目前流量為最大流。同時可以確定最小割集，前流量為最大流。同時可以確定最小割集，記已標號的點集記已標號的點集為為V,未標號的點集合為未標號的點集合為V,(V,V)為網絡的最小割。為網

41、絡的最小割。 t得到標號，反向追蹤在網絡中找到一條從得到標號，反向追蹤在網絡中找到一條從s到到t得由標號點得由標號點及相應的弧連接而成的增廣鏈。繼續(xù)第及相應的弧連接而成的增廣鏈。繼續(xù)第(4)步步Page 95 所所有有非非增增廣廣鏈鏈上上的的弧弧對對增增廣廣鏈鏈上上所所有有后后向向弧弧對對增增廣廣鏈鏈上上所所有有前前向向弧弧ftftff)()(4) 修改流量。設原圖可行流為修改流量。設原圖可行流為f，令，令得到網絡上一個新的可行流得到網絡上一個新的可行流f。(5) 擦除圖上所有標號，重復擦除圖上所有標號，重復(1)-(4)步，直到圖中找不到任何步，直到圖中找不到任何增廣鏈，計算結束。增廣鏈，計

42、算結束。Page 96例例6.10 用標號算法求下圖中用標號算法求下圖中st的最大流量，并找出最小割。的最大流量，并找出最小割。v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)Page 97解：解：(1) 先給先給s標號標號()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點相鄰的未標號的點，因點相鄰的未標號的點，因fs1cs1，故對，故對v1標號標號=min, cs1-fs1

43、=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點相鄰的未標號的點，因點相鄰的未標號的點，因f13c13，故對，故對v3標號標號=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點相鄰的未標號的點，因點相鄰的未標號的點，因f3tc3t，故對，故對vt標號標號=min1, c3t-f3t= min1, 1= 1)(t (1)找到

44、一條增廣鏈找到一條增廣鏈sv1v3tPage 101(4) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流。可行流。v1v3v2v48(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) 擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。v1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7(5)()(1)(1)(1)Page 103(5) 擦除所有標號，重復上述

45、標號過程，尋找另外的增廣鏈。擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。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) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流?？尚辛?。v1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)()(2)(2)(2)(1)(1)12 sf121

46、 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) 擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。Page 106v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(1)(1)(1)(7) 擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。擦除所有標號，重復上述標號過程，尋找另外的增廣鏈。(2)=min,1=1(1)=min1,2=1(3)=min1,4=1,4321V

47、VtvVvvvsV 最小割為最小割為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) 在已知可行流的基礎上，通過標號尋找增廣鏈。在已知可行流的基礎上，通過標號尋找增廣鏈。()(2)=min,6=6(6)(3)=min6,2=2(2)(t)=min2,5=2(2)Page 109(2) 修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的修改增廣鏈上的流量，非增廣鏈上的流量不變，得到新的可行流?？尚辛鳌tv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6