運(yùn)籌學(xué)10-圖與網(wǎng)絡(luò)優(yōu)化

第十章

圖與網(wǎng)絡(luò)優(yōu)化

(GraphTheoryandNetworkAnalysis)圖的基本概念樹(shù)及最小支撐樹(shù)最短路問(wèn)題網(wǎng)絡(luò)最大流問(wèn)題最小費(fèi)用最大流問(wèn)題中國(guó)郵遞員問(wèn)題圖論的起源和發(fā)展1736年，Euler哥尼斯堡七橋問(wèn)題(K?nigsbergBridgeProblem)BACDABCD一筆畫(huà)問(wèn)題1847年，kirchhoff，電網(wǎng)絡(luò)，“樹(shù)”；1852年，《四色猜想》；1964年，華羅庚，《統(tǒng)籌方法平話(huà)》。1857年，Cogley，同分異構(gòu)，“樹(shù)”；1956年，杜邦公司，CPM，關(guān)鍵路線(xiàn)法；1958年，美國(guó)海軍部，PERT，計(jì)劃評(píng)審技術(shù)；1962年，管梅谷，《中國(guó)郵路問(wèn)題》；第一節(jié)圖的基本概念一、幾個(gè)例子例1

是北京、上海等十個(gè)城市間的鐵路交通圖。與此類(lèi)似的還有電話(huà)線(xiàn)分布圖、煤氣管道圖、航空路線(xiàn)圖等。北京天津濟(jì)南青島武漢南京上海鄭州連云港徐州例2

分別用點(diǎn)v1,v2,v3,v4,v5分別代表甲、乙、丙、丁、戊五支球隊(duì)。若有兩支球隊(duì)之間比賽過(guò)，就在相應(yīng)的點(diǎn)之間聯(lián)一條線(xiàn)，且這條線(xiàn)不過(guò)其他點(diǎn)。如下圖所示：v1v2v3v4v5可知各隊(duì)之間的比賽情況如下：甲——乙、丙、丁、戊乙——甲、丙丙——甲、乙、丁丁——甲、丙、戊戊——甲、丁例3“染色問(wèn)題”儲(chǔ)存8種化學(xué)藥品，其中某些藥品不能存放在同一個(gè)庫(kù)房里。用v1,v2,…,v8分別代表這8種藥品。規(guī)定若兩種藥品不能存放在一起，則其相應(yīng)的點(diǎn)之間聯(lián)一條線(xiàn)。如下圖所示：v1v2v3v4v5v6v7v8可知需要4個(gè)庫(kù)房，其中一個(gè)答案是：

{v1}{v2,v4,v7}{v3,v5}{v6,v8}還有其他的答案。二、基本概念

有向圖

由點(diǎn)及弧所構(gòu)成的圖，記為D=(V,A)，

V,A分別是D的點(diǎn)集合和弧集合。

無(wú)向圖由點(diǎn)及邊所構(gòu)成的圖。記為G=(V,E),V，E分別是G的點(diǎn)集合和邊集合。v1v2v3v4v1v2v3v4a1a2a3a4a5e1e2e3e4e5a6e6

邊兩點(diǎn)之間不帶箭頭的聯(lián)線(xiàn)。如e3v1v4a3

弧兩點(diǎn)之間帶箭頭的聯(lián)線(xiàn)。如a3v1v4e3

端點(diǎn)及關(guān)聯(lián)邊若邊e=[u,v]∈E，則稱(chēng)u,v

為e的端點(diǎn)，也稱(chēng)u,v是相鄰的，稱(chēng)e是點(diǎn)u(及點(diǎn)v)的關(guān)聯(lián)邊。如：v1,v4為e3的端點(diǎn)，v1,v4是相鄰的，e3是v1（v4

）的關(guān)聯(lián)邊。

環(huán)若在圖G中，某個(gè)邊的兩個(gè)端點(diǎn)相同，則稱(chēng)e是環(huán)。如e7v1v2v3v4e1e2e3e4e5e6e7

多重邊若兩個(gè)點(diǎn)之間有多于一條的邊，稱(chēng)這些邊為多重邊。如e1,e2

簡(jiǎn)單圖一個(gè)無(wú)環(huán)，無(wú)多重邊的圖。

多重圖一個(gè)無(wú)環(huán)、但允許有多重邊的圖。

點(diǎn)v的次以點(diǎn)vi為端點(diǎn)邊的個(gè)數(shù)，記為dG(vi)或d(vi)。v1v2v3v4e1e2e3e4e5e6e7如d(v4)=5d(v2)=4v5

懸掛點(diǎn)次為1的點(diǎn)，如v5

懸掛邊懸掛點(diǎn)的關(guān)聯(lián)邊，如e8e8

孤立點(diǎn)次為0的點(diǎn)

偶點(diǎn)次為偶數(shù)的點(diǎn)，如v2

奇點(diǎn)

次為奇數(shù)的點(diǎn),如v5

鏈中間點(diǎn)初等鏈圈初等圈簡(jiǎn)單圈

v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9

在上圖中,(v1,v2,v3,v4,v5,v3,v6,v7)是一條鏈,但不是初等鏈在該鏈中,v2,v3,v4,v5,v3,v6是中間點(diǎn)(v1,v2,v3,v6,v7)是一條初等鏈(v1,v2,v3,v4,v1)是一個(gè)初等圈(v4,v1,v2,v3,v5,v7,v6,v3,v4)是一個(gè)簡(jiǎn)單圈

連通圖圖G中，若任何兩個(gè)點(diǎn)之間，至少有一條鏈，稱(chēng)為連通圖。否則稱(chēng)為不連通圖。

連通分圖(分圖)若G是不連通圖，則它的每個(gè)連通的部分稱(chēng)為連通分圖。v1v2v3v4e1e2e3e4e5e6v5v6e7如左圖就是個(gè)不連通圖，它是由兩個(gè)連通分圖構(gòu)成的。

支撐子圖給定一個(gè)圖G=(V,E)，如果圖G’=(V’,E’)，使V’=V及E’

E，則稱(chēng)G’是G的一個(gè)支撐子圖。v1v2v3v4(G)v1v2v3v4(G’)

基礎(chǔ)圖給定一個(gè)有向圖D=(V,A)，從D中去掉所有弧上的箭頭，所得到的無(wú)向圖稱(chēng)為基礎(chǔ)圖。記之為G(D)。v1v2v3v4a1a2a3a4a5a6D=(V,A)v1v2v3v4e1e2e3e4e5e6G(D)v1v2v3v4a1a2a3a4a5a6a7a8a9a10a11v6v7

路初等路回路v5

簡(jiǎn)單有向圖多重有向圖

權(quán)與網(wǎng)絡(luò)在實(shí)際應(yīng)用中，給定一個(gè)圖G=（V，E）或有向圖D=（V，A），在V中指定兩個(gè)點(diǎn)，一個(gè)稱(chēng)為始點(diǎn)（或發(fā)點(diǎn)），記作v1，一個(gè)稱(chēng)為終點(diǎn)（或收點(diǎn)），記作vn

，其余的點(diǎn)稱(chēng)為中間點(diǎn)。對(duì)每一條弧，對(duì)應(yīng)一個(gè)數(shù)，稱(chēng)為弧上的“權(quán)”。通常把這種賦權(quán)的圖稱(chēng)為網(wǎng)絡(luò)。對(duì)于網(wǎng)絡(luò)（賦權(quán)圖）G=（V，E），其中邊有權(quán)，構(gòu)造矩陣，其中：稱(chēng)矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣。設(shè)圖G=（V，E）中頂點(diǎn)的個(gè)數(shù)為n，構(gòu)造一個(gè)矩陣

，其中：稱(chēng)矩陣A為網(wǎng)絡(luò)G的鄰接矩陣。圖的矩陣表示權(quán)矩陣為：鄰接矩陣為：v5v1v2v3v4v64332256437圖的矩陣表示

定理1圖G=(V,E)中，所有點(diǎn)的次之和是邊數(shù)的兩倍，即

定理2任一圖中奇點(diǎn)的個(gè)數(shù)為偶數(shù)。三、基本定理第二節(jié)樹(shù)一、定義例1在五個(gè)城市之間架設(shè)電話(huà)線(xiàn)，要求任兩個(gè)城市之間都可以相互通話(huà)（允許通過(guò)其他城市），并且電話(huà)線(xiàn)的根數(shù)最少。v1v5v2v3v4用v1,v2,v3,v4,v5代表五個(gè)城市,如果在某兩個(gè)城市之間架設(shè)電話(huà)線(xiàn),則在相應(yīng)的兩點(diǎn)之間聯(lián)一條邊,這樣一個(gè)電話(huà)線(xiàn)網(wǎng)就可以用一個(gè)圖來(lái)表示。顯然,這個(gè)圖必須是連通的,而且是不含圈的連通圖。如右圖所示。樹(shù)的定義：一個(gè)無(wú)圈的連通圖。例2某工廠的組織機(jī)構(gòu)如下圖所示廠長(zhǎng)行政辦公室生產(chǎn)辦公室生產(chǎn)計(jì)劃科技術(shù)科設(shè)計(jì)組工藝組供銷(xiāo)科財(cái)務(wù)科行政科車(chē)間鑄造工段鍛壓工段二車(chē)間三車(chē)間四車(chē)間該廠的組織機(jī)構(gòu)圖就是一個(gè)樹(shù)。例3樹(shù)圖倒置的樹(shù)，根(root)在上，葉(leaf)在下定理1

設(shè)圖G=(V,E)是一個(gè)樹(shù)，p(G)≥2，則G中至少有兩個(gè)懸掛點(diǎn)。二、性質(zhì)證明定理2

圖G=(V,E)是一個(gè)樹(shù)的充分必要條件是G中不含圈，且恰有p-1條邊。證明

定理3

圖G=(V,E)是一個(gè)樹(shù)的充分必要條件是G是連通圖，并且q(G)=p(G)-1。證明由定理2，必要性顯然。定理4

圖G是樹(shù)的充分必要條件是任意兩個(gè)頂點(diǎn)之間恰有一條鏈。證明由樹(shù)的定義，必要性顯然。因?yàn)槿蝺蓚€(gè)頂點(diǎn)間恰有一條鏈，顯然G是連通的。如果G中含有圈的話(huà)，則其中至少有兩個(gè)頂點(diǎn)間有兩條鏈，這與題設(shè)矛盾。充分性得證。推論：

從一個(gè)樹(shù)中去掉一條邊，則余下的圖是不連通的。

在樹(shù)中不相鄰的兩個(gè)點(diǎn)間添上一條邊，則恰好得到一個(gè)圈。三、圖的支撐樹(shù)定義：設(shè)圖T=(V,E’)是圖G的支撐子圖，如果圖T=(V,E’)是一個(gè)樹(shù)，則稱(chēng)T是G的一個(gè)支撐樹(shù)。定理：圖G有支撐樹(shù)的充分必要條件是圖G是連通的。證明必要性顯然。再證充分性。設(shè)圖G是連通圖，若G不含圈，則G本身是一個(gè)樹(shù)，從而G是它自身的一個(gè)支撐樹(shù)。

如果G含圈，任取一個(gè)圈，從圈中任意地去掉一條邊，得到圖G的一個(gè)支撐子圖G1。如果G1不含圈，那么G1是G的一個(gè)支撐樹(shù)；如果G1仍含圈，那么從G1中任取一個(gè)圈，從圈中再任意去掉一條邊，得到圖G的一個(gè)支撐子圖G2，如此重復(fù)，最終可以得到G的一個(gè)支撐子圖Gk,它不含圈，于是Gk是G的一個(gè)支撐樹(shù)。支撐樹(shù)的求解方法

破圈法例用破圈法求解圖的一個(gè)支撐樹(shù)v1v2v3v4v5e1e2e3e4e5e6e7e8這就得到了該圖的一個(gè)支撐樹(shù)。

避圈法v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9這就得到了該圖的一個(gè)支撐樹(shù)。四、最小支撐樹(shù)定義1

給圖G=(V,E)，對(duì)G中的每一條邊[vi,vj]，相應(yīng)地有一個(gè)數(shù)wij，則稱(chēng)這樣的圖G為賦權(quán)圖，wij稱(chēng)為邊[vi,vj]上的權(quán)。1.定義定義2

如果T=(V,E’)是G的一個(gè)支撐樹(shù)，稱(chēng)E’中所有邊的權(quán)之和為支撐樹(shù)T的權(quán)，記為w(T)，即最小支撐樹(shù)如果支撐樹(shù)T*的權(quán)w(T*)是G的所有支撐樹(shù)的權(quán)中最小者，則稱(chēng)T*是G的最小支撐樹(shù)(簡(jiǎn)稱(chēng)最小樹(shù)),即

2.最小支撐樹(shù)的求法方法一避圈法

開(kāi)始選一條權(quán)最小的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈。v1v2v3v4v5v6651572344這就得到了該圖的一個(gè)最小支撐樹(shù)。方法二破圈法

任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊。在余下的圖中，重復(fù)這個(gè)步驟，一直到一個(gè)不含圈的圖為止，這時(shí)的圖便是最小樹(shù)。v1v2v3v4v5v6651572344這就得到了該圖的一個(gè)最小支撐樹(shù)。第三節(jié)最短路問(wèn)題一、最短路問(wèn)題的提出v1v2v3v4v5v6v7v8v9132216610410423236例左圖為單行線(xiàn)交通網(wǎng)，弧旁數(shù)字表示通過(guò)這條單行線(xiàn)所需要的費(fèi)用。求從v1出發(fā)到v8總費(fèi)用最小的路線(xiàn)。(1)有很多條路線(xiàn)，與圖論中的路一一對(duì)應(yīng)；(2)一條路線(xiàn)的費(fèi)用就是相應(yīng)的路中各條弧的費(fèi)用之和。如上圖所示的路線(xiàn)為最短路。在圖論中，最短路問(wèn)題可歸結(jié)為：(1)給定一個(gè)賦權(quán)有向圖D＝(V,A)及W(a)=

Wij；(2)給定D中兩個(gè)頂點(diǎn)vs、vt，P是D中從vs到vt的一條路；(3)定義路P的權(quán)為P中所有弧的權(quán)之和，W(P)＝

Wij

；(4)求一條權(quán)最小的路P0:W(P0)=minW(P)二、求解方法基本原理：最短路問(wèn)題的特性最短路線(xiàn)上的任一中間點(diǎn)到終（起）點(diǎn)的路線(xiàn)一定是該中間點(diǎn)到終（起）點(diǎn)的所有路線(xiàn)中最短的路線(xiàn)。若求起點(diǎn)A到任一點(diǎn)G的最短路線(xiàn)，可先求A到G點(diǎn)的相鄰前點(diǎn)的最短距離，在此基礎(chǔ)上求出A到G點(diǎn)的最短距離。這樣，最終求出起點(diǎn)到終點(diǎn)的最短距離。狄克斯屈拉算法

(Dijkstra,1959)。從起點(diǎn)vs出發(fā)，逐步向外探尋最短路。在已知前點(diǎn)的最短距離基礎(chǔ)上，求其后點(diǎn)的最短距離。1.wij0v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,1)第一步：v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)第二步：第三步：v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)(v3,5)第四步：v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)(v3,5)(v2,6)第五步：(v5,9)v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)(v3,5)(v2,6)第六步：(v5,9)v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)(v3,5)(v2,6)(v5,10)第七步：(v5,12)(v5,9)v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v1,3)(v1,1)(v3,5)(v2,6)(v5,10)v1v2v3v4v5v6v7v8v9132216610410423236(v1,0)(v3,5)(v1,3)(v1,1)最后，找出v1到v8的最短路為：(v4,11)(v2,6)(v5,10)(v5,9)(v5,12)缺點(diǎn)：不能解決存在負(fù)權(quán)圖的最短路問(wèn)題。計(jì)算步驟：

(1)考察從所有標(biāo)號(hào)點(diǎn)(已求出最短距離的點(diǎn))出發(fā)的弧的終點(diǎn)vj

(已標(biāo)號(hào)的點(diǎn)除外)

，計(jì)算起點(diǎn)vs

到vj的距離dsj(標(biāo)號(hào)值＋Wij)；若vj不存在，算法終止，轉(zhuǎn)(3)。

(2)增加新的標(biāo)號(hào)點(diǎn)。比較所有dsj

，最小者對(duì)應(yīng)的點(diǎn)成為新的標(biāo)號(hào)點(diǎn)，即求出了vs

到某個(gè)vj的最短距離dsj*，轉(zhuǎn)(1)。

(3)逆著計(jì)算過(guò)程反推，找出最短路。DP最短路與Dijkstra最短路的比較相同點(diǎn)：

(1)依據(jù)最短路的特性；

(2)隱含比較了vs

到vj

的所有路線(xiàn)。不同點(diǎn)：

(1)Dijkstra更具普遍性，DP是特例；

(2)DP隱含比較vs

到vj

的所有路線(xiàn)是完整的；Dijkstra隱含比較vs

到vj

的所有路線(xiàn)中，只有一部分是完整的，其它的只是vs

到vj

的路線(xiàn)的一段；

(3)每迭代一次，DP可求出起點(diǎn)至某階段末所有點(diǎn)的最短距離，而Dijkstra只能求出起點(diǎn)至一個(gè)中間點(diǎn)的最短距離。2.wij不全0

Dijkstra算法失效，即雖然完整的路線(xiàn)比完整中的片斷距離短，但也不能斷定該完整路線(xiàn)一定最短。只能采用最原始的思想，即找出vs

到vj

的所有路線(xiàn)的權(quán)，才能確定vs

到vj

的最短距離。具體算法如下：設(shè)有向圖中有n個(gè)點(diǎn)，從vi到vj的最短路線(xiàn)不一定從vi直達(dá)vj，也可能經(jīng)過(guò)一個(gè)、兩個(gè)或n－2個(gè)中間點(diǎn)才能到達(dá)vj

。把從vi直達(dá)vj，稱(chēng)為走一步，經(jīng)過(guò)一個(gè)中間點(diǎn)稱(chēng)為走二步，則vi到vj的最短路線(xiàn)最多走n－1步。應(yīng)用條件：圖中不存在負(fù)回路。v1v2v3v4v5v6v7v8表格法6-1-283-3-5-121112-1-3-57(v1,0)(v1,-1)(v1,3)(v1,-2)(v1,

)(v1,

)(v1,

)(v1,

)例:求v1到圖中其他各點(diǎn)的最短路。走1步時(shí)v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-1)(v1,3)(v1,-2)(v1,

)(v1,

)(v1,

)(v1,

)(v3,-5)(v3,-7)(v3,-1)(v2,5)(v4,11)(v4,5)(v2,1)走2步時(shí)v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-2)(v1,

)(v1,

)(v3,-5)(v3,-7)(v3,-1)(v2,1)(v6,0)(v4,5)(v4,-5)(v6,6)走3步時(shí)(v5,0)(v2,1)(v4,1)(v2,-3)(v6,0)(v7,4)v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-2)(v6,6)(v1,

)(v3,-5)(v3,-7)(v3,-1)(v2,-3)(v6,0)(v4,-5)走4步時(shí)(v5,-4)(v2,1)(v4,1)(v6,0)(v7,-6)(v8,3)(v8,1)wijd(t)(vi

,vj

)

v1v2v3v4v5v6v7v8t=1t=2t=3t=4v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v48023-7-7-7v5-101-3-3v61017-1-1-1v7-105-5-5v8-3-5066說(shuō)明：表中空格處為+

。缺點(diǎn)：不能解決負(fù)回路的情況。3.Floyd（佛洛伊德）算法這里介紹得Floyd（1962年）可直接求出網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路。令網(wǎng)絡(luò)中的權(quán)矩陣為其中當(dāng)其他算法基本步驟為：⑴輸入權(quán)矩陣?yán)?求圖中任意兩點(diǎn)間的最短路。⑵計(jì)算其中例如：

中不帶角標(biāo)的元素表示從到的距離（直接有邊），帶角標(biāo)的元素表示借為中間點(diǎn)時(shí)的最短路長(zhǎng)。

中不帶角標(biāo)的元素表示從到的距離（直接有邊），帶角標(biāo)的元素表示借為中間點(diǎn)時(shí)的最短路長(zhǎng)。在放開(kāi)的基礎(chǔ)上，再放開(kāi)注意到：在放開(kāi)點(diǎn)的基礎(chǔ)上，再放開(kāi)考察最短路。注意到：說(shuō)明所有點(diǎn)經(jīng)過(guò)并沒(méi)有縮短路程。只有一個(gè)新增元素表示任意兩點(diǎn)間的最短路長(zhǎng)及其路徑。三、應(yīng)用舉例例設(shè)備更新問(wèn)題。某企業(yè)使用一臺(tái)設(shè)備，在每年年初都要決定是購(gòu)置新設(shè)備還是繼續(xù)使用舊的。購(gòu)置新設(shè)備要支付一定的購(gòu)置費(fèi)，使用舊設(shè)備則要支付維修費(fèi)。制定一個(gè)五年內(nèi)的設(shè)備更新計(jì)劃，使得總支付費(fèi)用最少。已知該設(shè)備在各年年初的價(jià)格為：第一年第二年第三年第四年第五年1111121213已知使用不同時(shí)間的設(shè)備維修費(fèi)用為：使用年數(shù)0~11~22~33~44~5維修費(fèi)用5681118

設(shè)以vi(i=1,2,3,4,5)表示“第i年初購(gòu)進(jìn)一臺(tái)新設(shè)備”這種狀態(tài)，以v6表示“第5年末”這種狀態(tài)；以弧(vi,

vj)表示“第i年初購(gòu)置的一臺(tái)設(shè)備一直使用到第j年初”這一方案，以wij表示這一方案所需購(gòu)置費(fèi)和維修費(fèi)之和。這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問(wèn)題就可歸結(jié)為從圖中找出一條從v1到v6的最短路問(wèn)題。從圖中可以得出兩條最短路：

v1—v3—v6;v1—v4—v6v1v2v3v5v6v4163022165941224130173123172318(v1,0)(v1,16)v1v2v3v5v6v4163022165941224130173123172318(v1,0)(v1,16)(v1,22)v1v2v3v5v6v4163022165941224130173123172318(v1,0)(v1,16)(v1,22)(v1,30)v1v2v3v5v6v4163022165941224130173123172318(v1,0)(v1,16)(v1,22)(v1,30)(v1,41)v1v2v3v5v6v4163022165941224130173123172318(v1,0)(v1,16)(v1,22)(v1,30)(v1,41)(v3,53)(v4,53)第四節(jié)網(wǎng)絡(luò)最大流問(wèn)題

如下是一運(yùn)輸網(wǎng)絡(luò)，弧上的數(shù)字表示每條弧上的容量，問(wèn)：該網(wǎng)絡(luò)的最大流量是多少？vsv2v1v3v4vt432115234一、問(wèn)題的提出二、求解方法（一）概念1.可行流和最大流

容量限制條件：0

fij

cij

平衡條件：

對(duì)于網(wǎng)絡(luò)D＝(V，A，C)，網(wǎng)絡(luò)D上的流

f指定義在弧集合A上的一個(gè)函數(shù)f={fij

}，

fij

為弧aij

的流量。滿(mǎn)足下列條件的流f稱(chēng)為可行流：

v(f)最大的可行流f稱(chēng)為最大流，記為f*?？捎靡韵翷P模型求解。

對(duì)于任何網(wǎng)絡(luò)，其可行流f一定存在。如令fij=0，f為可行流，其v(f)=0。零流弧:

fij

=0的弧

若是網(wǎng)絡(luò)中連接起點(diǎn)vs和終點(diǎn)vt的一條鏈，定義鏈的方向是從vs到vt，則鏈上的弧被分成兩類(lèi)：前向?。夯〉姆较蚺c鏈的方向一致,+表示中前向弧的集合后向?。夯〉姆较蚺c鏈的方向相反,‐表示中后向弧的集合3.前向弧和后向弧零流弧和飽和弧

設(shè)f是一可行流，是從vs到vt的一條鏈，若滿(mǎn)足下列條件，則稱(chēng)之為（關(guān)于流f的）一條增廣鏈：在弧(vi,vj)

+上，0fij<cij(非飽和弧)

在弧(vi,vj)

‐上，0<fijcij

(非零流弧)4.增廣鏈vsv2v1v3v4vt10(5)8(3)4(1)5(2)3(2)6(3)3(3)11(6)17(2)5(1)在左圖中,(vs,v1,v2,v3,v4,vt)是一條增廣鏈,因?yàn)?/p>

+

和‐中的弧滿(mǎn)足增廣鏈的條件。如：5.可擴(kuò)充量6.調(diào)整后的弧流量v5v1v2v3v4v6(2,2)(8,3)(3,1)(2,2)(4,1)(2,1)(2,2)(5,3)(二)標(biāo)號(hào)法求最大流(FordFulkerson)例：

思路：從一可行流出發(fā)，檢查關(guān)于此流是否存在增廣鏈。若存在增廣鏈，則增大流量，使此鏈變?yōu)榉窃鰪V鏈；這時(shí)再檢查是非還有增廣鏈，若還有，繼續(xù)調(diào)整，直至不存在增廣鏈為止。v5v1v2v3v4v6(2,2)(8,3)(3,1)(2,2)(4,1)(2,1)(2,2)(5,3)(0,+

)(v1,5)(v3,3)(-v4,1)(v2,1)(v5,1)按

=1進(jìn)行調(diào)整，可得下圖：第一步：尋找增廣鏈，通過(guò)給結(jié)點(diǎn)標(biāo)號(hào)實(shí)現(xiàn)第二步：調(diào)整可行流(增廣鏈)的流量v5v1v2v3v4v6(2,2)(8,4)(3,0)(2,2)(4,2)(2,2)(2,2)(5,4)(0,+

)(v1,4)(v3,2)按同樣的步驟找可行流。此時(shí),標(biāo)號(hào)過(guò)程無(wú)法進(jìn)行下去，算法結(jié)束。三、標(biāo)號(hào)算法的理論依據(jù)定義vsv2v1v3v4vt432115234截集截量

截集的概念將任何復(fù)雜的網(wǎng)絡(luò)抽象成兩個(gè)點(diǎn)之間的流量關(guān)系：

顯然，若把截集去掉，則從vs到vt的路將不存在。截量制約了從vs到vt的流量。最小截集定理可行流f*是最大流的充要條件是不存在關(guān)于f*的增廣鏈。證明：

該定理證明的充分性部分就是標(biāo)號(hào)法的尋找增廣鏈過(guò)程；其必要性部分就是調(diào)整可行流的過(guò)程。v5v1v2v3v4v6(2,2)(8,4)(3,0)(2,2)(4,2)(2,2)(2,2)(5,4)(0,+

)(v1,4)(v3,2)例：四、最大流最小截集的標(biāo)號(hào)法舉例(0,+)(vs,6)(-v2,6)(v3,1)(v4,1)(0,)(vs,5)(v2,2)(-v5,2)(v4,2)(0,)(vs,3)(-v2,3)最小截集(0,)(vs,5)(v2,2)(-v5,2)(v4,2)第五節(jié)最小費(fèi)用最大流問(wèn)題一、問(wèn)題的提出v1v2vsv3vt(4,10)(1,8)(6,2)(3,10)(2,5)(1,7)(2,4)二、算法的理論基礎(chǔ)(1)若f是流量為v(f)的所有可行流中費(fèi)用最小者，而

是關(guān)于f

的所有增廣鏈中費(fèi)用最小的增廣鏈，那么沿

去調(diào)整f，得到的可行流f’

，就是流量為v(f’)的所有可行流中的最小費(fèi)用流。這樣，當(dāng)f’

是最大流時(shí),也就得到了我們所要的最小費(fèi)用最大流。

由于同一流量存在多個(gè)可行流f，所以一定存在費(fèi)用最小的可行流f。設(shè)

是關(guān)于可行流f的一條增廣鏈，以

=1調(diào)整f得到新的可行流f’

，b(f’)比b(f)增加的費(fèi)用為：把調(diào)整后增加的費(fèi)用稱(chēng)為這條增廣鏈

的費(fèi)用。

已知最小費(fèi)用流f，問(wèn)題的關(guān)鍵是如何找到關(guān)于f

的最小費(fèi)用增廣鏈

，從而沿

去調(diào)整f，得到新的最小費(fèi)用流f’

。

找關(guān)于f

的最小費(fèi)用增廣鏈

，等價(jià)于求從vs到vt的最短路。vsv2vtv1bs1b21b2t已知下圖為關(guān)于f

的最小費(fèi)用增廣鏈

其最小費(fèi)用：bs1+b2t－b21-bs1-b21-b2t從vs到vt的路為vs

v1

v2

vt，距離為bs1+b2t－b21

，與最小費(fèi)用相等。三、求解方法v1v2vsv3vt4163212解：（1）構(gòu)造賦權(quán)有向圖W（f（0））用標(biāo)號(hào)法求最短路(vs,1)(0,0)v1v2vsv3vt4163212(vs,1)(0,0)(v2,3)v1v2vsv3vt4163212(vs,1)(0,0)(v2,3)(v2,4)v1v2vsv3vt4163212(vs,1)(0,0)(v2,3)(v2,4)(v1,4)由此得到vs到vt的最短路：v1v2vsv3vt(4,10)(1,8)(6,2)(3,10)(2,5)(1,7)(2,4)(vs,1)(v2,3)(v1,4)v1v2vsv3vt(0,10)(0,8)(0,2)(0,10)(0,5)(0,7)(0,4)調(diào)整f（0）=0,弧旁數(shù)字為(fij,cij)。調(diào)整最短路對(duì)應(yīng)的增廣鏈，

=5。(5,8)(5,5)(5,7)（2）構(gòu)造賦權(quán)有向圖W（f（1））v1v2vsv3vt416312-1-2-1v1v2vsv3vt416312-1-2-1用標(biāo)號(hào)法求出最短路：v1v2vsv3vt(0,10)(5,8)(0,2)(0,10)(5,5)(5,7)(0,4)調(diào)整最短路對(duì)應(yīng)的增廣鏈，

=2。(2,10)(7,7)（3）構(gòu)造賦權(quán)有向圖W（f（2））v1v2vsv3vt4163-12-1-2-4用標(biāo)號(hào)法求出最短路：v1v2vsv3vt4163-12-1-2-4調(diào)整最短路對(duì)應(yīng)的增廣鏈，

=3。v1v2vsv3vt(0,10)(5,8)(0,2)(0,10)(5,5)(5,