空中交通系統(tǒng)優(yōu)化與管理圖與網(wǎng)路分析圖論

Graph

TheoryBCDBC哥尼斯堡七橋問(wèn)題(K?nigsbergBridge

Problem)Leonhard

Euler

(1707-1783)

在1736年發(fā)表第一篇圖論方面的論文，奠基了圖論中的一些基本定理很多問(wèn)題都可以用點(diǎn)和線來(lái)表示，一般點(diǎn)表示實(shí)體，線表示實(shí)體間的關(guān)聯(lián)AAD6.1

圖與網(wǎng)路的基本概念

6.1.1圖與網(wǎng)路節(jié)點(diǎn)(Vertex)物理實(shí)體、事物、概念一般用vi

表示邊

(Edge)節(jié)點(diǎn)間的連線，表示有關(guān)系一般用eij

表示v1v5v4v3v2e12e34e13e24e22e'13e45圖 6.1

圖

(Graph)

節(jié)點(diǎn)和邊的集合，

一般用G(V,E)

表示

點(diǎn)集V={v1,v2,…,

vn}

邊集E={eij}v1v5v4v3v2e12e13e24e22e'13

網(wǎng)路(Network)

邊上具有表示連接強(qiáng)度的權(quán)值，如wij

又稱加權(quán)圖(Weighted

graph)856142e451e343圖 6.1圖v1v5v4v3v2e12e34e13e24e'13e45圖

6.1多重邊環(huán)孤立點(diǎn)e22V6v1v5v3v2e12e34e13e24e45v4圖6.2 簡(jiǎn)單圖無(wú)環(huán)、無(wú)多重邊的圖稱為簡(jiǎn)單圖懸掛點(diǎn)6.1.2

無(wú)向圖與有向圖邊都沒(méi)有方向的圖稱為無(wú)向圖，如圖6.1在無(wú)向圖中eij=eji，或

(vi,

vj)=(vj,

vi)當(dāng)邊都有方向時(shí)，稱為有向圖，用G(V,A)表示在有向圖中，有向邊又稱為弧，用aij表示，i,

j

的順序是不能顛倒的，圖中弧的方向用箭頭標(biāo)識(shí)圖中既有邊又有弧，稱為混合圖6.1.3

端點(diǎn)，關(guān)聯(lián)邊，相鄰，次圖中可以只有點(diǎn)，而沒(méi)有邊；而有邊必有點(diǎn)若節(jié)點(diǎn)vi ,vj

之間有一條邊eij，則稱vi ,vj 是eij

的端點(diǎn)(end

vertex)，而

eij

是節(jié)點(diǎn)vi,

vj

的關(guān)聯(lián)邊(incident

edge)同一條邊的兩個(gè)端點(diǎn)稱為相鄰(adjacent)節(jié)點(diǎn)，具有共同端點(diǎn)的邊稱為相鄰邊一條邊的兩個(gè)端點(diǎn)相同，稱為自環(huán)(環(huán)、self-loop)；具有兩個(gè)共同端點(diǎn)的兩條邊稱為平行邊(多重邊、paralleledges)既沒(méi)有自環(huán)也沒(méi)有平行邊的圖稱為簡(jiǎn)單圖(simplegraph)6.1.3

端點(diǎn)，關(guān)聯(lián)邊，相鄰，次在無(wú)向圖中，與節(jié)點(diǎn)相關(guān)聯(lián)邊的數(shù)目，稱為該節(jié)點(diǎn)的“次”(degree)，記為d

；次數(shù)為奇數(shù)的點(diǎn)稱為奇點(diǎn)(odd)，次數(shù)為偶數(shù)的點(diǎn)稱為偶點(diǎn)(even)；圖中都是偶點(diǎn)的圖稱為偶圖(even

graph)有向圖中，由節(jié)點(diǎn)指向外的弧的數(shù)目稱為正次數(shù)，記為

d+，指向該節(jié)點(diǎn)的弧的數(shù)目稱為負(fù)次數(shù)，記為d–次數(shù)為

0

的點(diǎn)稱為孤立點(diǎn)(isolated

vertex)

，次數(shù)為

1

的點(diǎn)稱為懸掛點(diǎn)(pendant

vertex)定理

1：圖中奇點(diǎn)的個(gè)數(shù)總是偶數(shù)個(gè)6.1.4

鏈，圈，路徑，回路，歐拉回路相鄰節(jié)點(diǎn)的序列{v1

,v2

,…,

vn

}

構(gòu)成一條鏈(link)，又稱為行走(walk)；首尾相連的鏈稱為圈(loop)，或閉行走在無(wú)向圖中，節(jié)點(diǎn)不重復(fù)出現(xiàn)的鏈稱為路徑(path)；在有向圖中，節(jié)點(diǎn)不重復(fù)出現(xiàn)且鏈中所有弧的方向一致，則稱為有向路徑(directed

path)首尾相連的路徑稱為回路(circuit)歐拉回路與道路

連通圖G中，若存在一條道路，經(jīng)過(guò)每邊一次且僅一次，則稱這條路為歐拉道路。若存在一條回路，經(jīng)過(guò)每邊一次且僅一次，則稱這條回路為歐拉回路。

具有歐拉回路的圖稱為歐拉圖。

偶圖一定存在歐拉回路(一筆畫定理)定理3 無(wú)向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中無(wú)奇點(diǎn)。定理4 連通有向圖G是歐拉圖，當(dāng)且僅當(dāng)它每個(gè)頂點(diǎn)的出次等于入次。定理3證明：（必要性）因?yàn)镚是歐拉圖，則存在一條回路，經(jīng)由G中所有的邊，在這條回路上，頂點(diǎn)可能重復(fù)出現(xiàn)，但邊不重復(fù)。對(duì)于圖中的任一頂點(diǎn)vi，只要在回路中出現(xiàn)一次，必關(guān)聯(lián)兩條邊，即這條回路沿一條邊進(jìn)入這點(diǎn)，再沿另一邊離開(kāi)這點(diǎn)。所以認(rèn)點(diǎn)雖然可以在回路中重復(fù)出現(xiàn)，但deg(vi)必為偶數(shù)。所以G中沒(méi)有奇點(diǎn)。6.1.4

鏈，圈，路徑，回路，歐拉回路

（充分性）由于G中沒(méi)有奇點(diǎn)，從任一點(diǎn)出發(fā)，如從v1點(diǎn)出發(fā)，經(jīng)關(guān)聯(lián)邊e1

“進(jìn)入”v2，由于v2是偶點(diǎn)．則必可由v2經(jīng)關(guān)聯(lián)邊即進(jìn)入另一點(diǎn)v3，如此進(jìn)行下去，每邊僅取一次。由于G圖中點(diǎn)數(shù)有限，所以這條路不能無(wú)休止地走下去，必可走回v1，得到一條回路c1。(1)若回路c1經(jīng)過(guò)G的所有邊，則c1就是歐拉回路。(2)從G中去掉c1后得到子圖G

’，則G’中每個(gè)頂點(diǎn)的次數(shù)仍為偶數(shù)。因?yàn)镚圖是連通圖，所以c1與G‘至少有一個(gè)頂點(diǎn)vi重合，在G’中從vi出發(fā)，重復(fù)前面c1的方法，得到回路c2。把c1與c2組合在一起，如果恰是圖G，則得到歐拉回路。否則重復(fù)(2)可得回路c3，依此類推，由于圖G小邊數(shù)有限，最終可得一條經(jīng)過(guò)圖G所有邊的回路，即為歐拉回路。6.1.4

鏈，圈，路徑，回路，歐拉回路

設(shè)有兩個(gè)圖G1(V1,

E1),

G2(V2,

E2),

若V2

V1,

E2

E1，

則G2

是

G1

的子圖無(wú)向圖中，若任意兩點(diǎn)間至少存在一條路徑，則稱為連通圖(connected

graph)，否則為非連通圖(

discon-nected

graph)；非連通圖中的每個(gè)連通子圖稱為成分(component)鏈，圈，路徑(簡(jiǎn)稱路)，回路都是原圖的子圖6.1.5

連通圖，子圖，成分給定一個(gè)連通圖G，每邊有非負(fù)權(quán)l(xiāng)(e)，要求一條回路過(guò)每邊至少一次，且滿足總權(quán)最小。解法：由定理3知，如果G沒(méi)有奇點(diǎn)，則是一個(gè)歐拉圖，顯然按歐拉回路定就是滿足要求的過(guò)每邊至少一次且總權(quán)最小的回路。如果G中有奇點(diǎn)，要求連續(xù)走過(guò)每邊至少一次。必然有些邊不止一次走過(guò)，這相當(dāng)于在圖G中對(duì)某些邊增加一些重復(fù)邊，使所得到的新圖G’沒(méi)有奇點(diǎn)，且滿足總路程最短。6.1.6

中國(guó)郵路問(wèn)題充分必要條件為：

(1)每條邊最多重夏一次；

(2)對(duì)圖G中每個(gè)回路來(lái)講，重復(fù)邊的長(zhǎng)度和不超過(guò)回路總長(zhǎng)的一半。6.1.6

中國(guó)郵路問(wèn)題e

E1

定理5 已知圖G*＝G+E1無(wú)奇點(diǎn)，則

L(E1

)

l(e) 最小的由于總路程的長(zhǎng)短完全取決于所增加的重復(fù)邊的長(zhǎng)度，所以中國(guó)郵路問(wèn)題也可以轉(zhuǎn)為如下問(wèn)題：在連通圖G＝(V，E)中，求一個(gè)邊集E1

E，把G中屬于E1的邊均變?yōu)槎剡叺玫綀DG*＝G+E1，使其滿足G*無(wú)奇點(diǎn)，且 最小。e

E1L(E1

)

l(e)v5v1 9v844v4 4 v734v253v3 2

v6 v956 4v9v5v1 9v844v4 4 v7434v2536v3 2 v65第一步：確定初始可行方案。第二步：調(diào)整可行方案，使重復(fù)邊最多為一次。l12

l14

l69

l98

21例4 求解下圖所示網(wǎng)絡(luò)的中國(guó)郵路問(wèn)題。

第三步：檢查圖中每個(gè)回路是否滿足定理?xiàng)l件(2)。如不滿足則進(jìn)行調(diào)整，直至滿足為止。

6.1.6

中國(guó)郵路問(wèn)題 v1v9v5749v 4 vv844434v2536v3 2

v65l25

l45

l69

l98

171對(duì){v1v2v5v4v1},

l12

l14

2

(l12

l14

l69

l98

)236985

225

69

9823對(duì){vvvvvvv

},2l

l

l

1

(l

l

l

l

l

l )36 69 98 85 52l23

l36

l45

l58

156.2

樹(shù)圖與最小生成樹(shù)一般研究無(wú)向圖樹(shù)圖：倒置的樹(shù)，根(root)在上，樹(shù)葉(leaf)在下多級(jí)輻射制的電信網(wǎng)絡(luò)、管理的指標(biāo)體系、家譜、分類學(xué)、組織結(jié)構(gòu)等都是典型的樹(shù)圖C1C2C3C4根葉6.2.1

樹(shù)的定義及其性質(zhì)任兩點(diǎn)之間有且只有一條路徑的圖稱為樹(shù)(tree)，（無(wú)圈的連通圖）記為T樹(shù)的性質(zhì)：樹(shù)的兩點(diǎn)間有且僅有一條鏈在樹(shù)中去掉一邊，則不連通在樹(shù)中不相鄰的兩點(diǎn)間添一邊，恰成一圈若樹(shù)有m個(gè)頂點(diǎn)，則必有m-1條邊樹(shù)

T

是連通圖G

的生成樹(shù)(spanning

tree)，若

T

是

G的子圖且包含圖G

的所有的節(jié)點(diǎn)；則稱T是G的部分樹(shù)或生成樹(shù)（steiner

tree）（邊少點(diǎn)不少）6.2.2 圖的生成樹(shù)如何找到一棵生成樹(shù)避圈法深探法(depth

first

search)：任選一點(diǎn)標(biāo)記為

0

點(diǎn)開(kāi)始搜索，選一條未標(biāo)記的邊走到下一點(diǎn)，該點(diǎn)標(biāo)記為

1，將走過(guò)的邊標(biāo)記；假設(shè)已標(biāo)記到i

點(diǎn)，總是從最新標(biāo)記的點(diǎn)向下搜索，若從i

點(diǎn)無(wú)法向下標(biāo)記，即與i

點(diǎn)相關(guān)聯(lián)的邊都已標(biāo)記或相鄰節(jié)點(diǎn)都已標(biāo)記，則退回到i

1

點(diǎn)繼續(xù)搜索，直到所有點(diǎn)都被標(biāo)記廣探法(breadth

first

search)：是一種有層級(jí)結(jié)構(gòu)的搜索，一般得到的是樹(shù)形圖破圈法：見(jiàn)圈就破6.2.3 最小生成樹(shù)有n

個(gè)鄉(xiāng)村，各村間道路的長(zhǎng)度是已知的，如何敷設(shè)電話線路使n

個(gè)鄉(xiāng)村連通且總長(zhǎng)度最短顯然，這要求在已知邊長(zhǎng)度的網(wǎng)路圖中找最小生成樹(shù)最小生成樹(shù)不一定唯一最小生成樹(shù)定理是一個(gè)構(gòu)造性定理，它指出了找最小生成樹(shù)的有效算法6.2.3 最小生成樹(shù)Kruskal（避圈法）

：將圖中所有邊按權(quán)值從小到大排列，依次選所剩最小的邊加入邊集T，只要不和前面加入的邊構(gòu)成回路，直到T

中有

n

1

條邊，則T

是最小生成樹(shù)Kruskal（破圈法）：在給定的賦權(quán)的連通圖上任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條）。在余下的圖中，重復(fù)這個(gè)步驟，一直得到一個(gè)不含圈的圖為止，這時(shí)的圖便是一個(gè)最小生成樹(shù)。6.2.3 最小生成樹(shù)例：求出下圖的最小生成樹(shù)1.用避圈法解：v5v3v4v623744655v1 1v5v2v3v2v4v623744655v1 12.用破圈法解：6.2.3 最小生成樹(shù)

Prim

算法：不需要對(duì)邊權(quán)排序，即可以直接在網(wǎng)路圖上操作，也可以在邊權(quán)矩陣上操作，后者適合計(jì)算機(jī)運(yùn)算6.2.3 最小生成樹(shù)邊權(quán)矩陣上的Prim

算法：1、根據(jù)網(wǎng)路寫出邊權(quán)矩陣，兩點(diǎn)間若沒(méi)有邊，則用

表示；2、從v1

開(kāi)始標(biāo)記，在第一行打

，劃去第一列；3、從所有打

的行中找出尚未劃掉的最小元素，對(duì)該元素畫圈，劃掉該元素所在列，與該列數(shù)對(duì)應(yīng)的行打

；4、若所有列都劃掉，則已找到最小生成樹(shù)(所有畫圈元素所對(duì)應(yīng)的邊)；否則，返回第

3

步。該算法中，打

行對(duì)應(yīng)的節(jié)點(diǎn)在V1中，未劃去的列在V2中6.2.3 最小生成樹(shù)Prim算法是多項(xiàng)式算法Prim算法可以求最大生成樹(shù)網(wǎng)路的邊權(quán)可以有多種解釋，如效率1v4v6v3v5

10

vv21081177169.5129 1719.5

9

179

19.5

10

10 16 11 10 17

9.5

16 9.5

7

12

11

7

8 7

10

8

19.5 12 7

6.3

最短路問(wèn)題6.3.1

狄克斯特拉算法(Dijkstra

algorithm,

1959)計(jì)算兩節(jié)點(diǎn)之間或一個(gè)節(jié)點(diǎn)到所有節(jié)點(diǎn)之間的最短路令

dij

表示

vi

到

vj

的直接距離(兩點(diǎn)之間有邊)，若兩點(diǎn)之間沒(méi)有邊，則令dij

=

，若兩點(diǎn)之間是有向邊，則dji=

；令dii

=0，s

表示始點(diǎn)，t

表示終點(diǎn)0、令始點(diǎn)Ts=0，并用

框住，所有其它節(jié)點(diǎn)標(biāo)記Tj=

；1、從vs

出發(fā)，對(duì)其相鄰節(jié)點(diǎn)vj1

進(jìn)行臨時(shí)標(biāo)記，有Tj1=ds,j1

；2、在所有臨時(shí)標(biāo)記中找出最小者，并用

框住，設(shè)其為vr

。若此時(shí)全部節(jié)點(diǎn)都永久標(biāo)記，算法結(jié)束；否則到下一步；3、從新的永久標(biāo)記節(jié)點(diǎn)vr

出發(fā)，對(duì)其相鄰的臨時(shí)標(biāo)記節(jié)點(diǎn)進(jìn)行再標(biāo)記，設(shè)

vj2

為其相鄰節(jié)點(diǎn)，則Tj2=min{Tj2,

Tr+dr,j2

}，返回第2步。例1

狄克斯特拉算法0

8151012151131132s5t6341074918815220230341332726122v1v2v3v8v7v4v5v6Dijkstra最短路算法的特點(diǎn)和適應(yīng)范圍一種隱階段的動(dòng)態(tài)規(guī)劃方法每次迭代只有一個(gè)節(jié)點(diǎn)獲得永久標(biāo)記，若有兩個(gè)或兩個(gè)以上節(jié)點(diǎn)的臨時(shí)標(biāo)記同時(shí)最小，可任選一個(gè)永久標(biāo)記；總是從一個(gè)新的永久標(biāo)記開(kāi)始新一輪的臨時(shí)標(biāo)記，是一種深探法被框住的永久標(biāo)記Tj

表示

vs

到vj

的最短路，因此要求

dij

0，第k

次迭代得到的永久標(biāo)記，其最短路中最多有k條邊，因此最多有n

1

次迭代

可以應(yīng)用于簡(jiǎn)單有向圖和混合圖，在臨時(shí)標(biāo)記時(shí)，所謂相鄰必須是箭頭指向的節(jié)點(diǎn)；若第n

1

次迭代后仍有節(jié)點(diǎn)的標(biāo)記為

，則表明vs

到該節(jié)點(diǎn)無(wú)有向路徑

如果只求vs

到

vt

的最短路，則當(dāng)vt

得到永久標(biāo)記算法就結(jié)束了；但算法復(fù)雜度是一樣的

應(yīng)用Dijkstra

算法

n

1

次

，可以求所有點(diǎn)間的最短路

vs

到所有點(diǎn)的最短路也是一棵生成樹(shù)，但不是最小生成樹(shù)6.3.2

逐次逼近算法可用于網(wǎng)絡(luò)中有帶負(fù)權(quán)的邊時(shí)求某指定點(diǎn)v1

到網(wǎng)絡(luò)中任意點(diǎn)的最短路。算法基本思路：如果v1到vj的最短路總沿著該路從v1先到某一點(diǎn)vi，然后再沿邊(vi，vj)

到達(dá)vj

，則v1到vi的這條路必然也是v1到vi的最短路。若令P1j表示從v1到vj的最短路長(zhǎng)，P1i為v1到vi的最短路長(zhǎng)，則必有：P1j? =min(P1i + lij ）

l ] k

(2,3,....)ijiP(

k

)

min[P(k

1)1

j

1i1

j 1

j第二步起，使用迭代公式當(dāng)進(jìn)行到第t步時(shí)，若出現(xiàn)P

(t

)

P

(

t

1)6.3.2

逐次逼近算法1

j 1

j則停止即為v1點(diǎn)到各點(diǎn)的最短路長(zhǎng)(

j

1,2,3,....,

n)P(t

)1

jj

(1,2,....,

n)P(1)

l迭代方法：第一步：6.3.2

逐次逼近算法例：求下圖中V1到各點(diǎn)的最短路長(zhǎng)v5v2v1v362374465-1v7v82v-3-3-24v4解：初始條件為：11 12 13 14P(1)

P(1)

P(1)

P(1)

15 16 17 18P(1)

0,

P(1)

2,

P(1)

5,

P(1)

3,6.3.2

逐次逼近算法

第一輪迭代： 13

14

15

16P(2)

0,P(2)

3,P(2)

6,P(2)

11,P(2)

P(2)

17 18(1)(2)11(1)51

16

61

17

71

18

minPP

l ,P(1)

l ,P(1)

l ,P(1)

l ,

11 11 12 21 13 31 14 41

P

l ,P(1)

l ,P(1)

l ,P(1)

l

15 81

min

0

0,

2

,

5

,

3

,

,

,

,

0(1)1112

1222

1332

1442(

2)12(1)52

16

62

17

72

18

minP,

P(1) ,

P(1),

P(1),

P(1)P

l ,P(1)

ll

l

,

P

l ,P(1)

ll

l

15 82

min

0

2,

2

0,

5

,

3

,

,

,

,

,

26.3.2

逐次逼近算法迭代全過(guò)程可用下表表示：15 0 10 101 23 456v v v7 8v2v3v4v5v6v7v83-1 00 -242222220650000040-3-3-3-3-3-3066333-3041166667201499ivvvvvv1025-3jlij1jP(1)1jP(2)1jP(3)P(4)

P(5)1

j 1

j0 0 0 0 0 01

j 1

jP(6)

P(7)v2 v5v1v32376

4 4654v4-1v7v82v-3-3-26.3.2

逐次逼近算法用反向追蹤法可找出到各點(diǎn)的最短路：10932-3600v1到v8最短路： v1-

v2- v3 - v6

- v8同理可推出v1到各點(diǎn)的最短路求圖12-6所示的網(wǎng)絡(luò)，從v1到任一點(diǎn)vj的最短路長(zhǎng)，j＝1，2，…，6。0，-2，3，-2，-3，-16.3.3

Warshall-Floyd算法 (1962)Warshall-Floyd算法可以解決有負(fù)權(quán)值邊(弧)的最短路問(wèn)題該算法是一種整體算法，一次求出所有點(diǎn)間的最短路該算法不允許有負(fù)權(quán)值回路，但可以發(fā)現(xiàn)負(fù)權(quán)值回路該算法基于基本的三角運(yùn)算定義：對(duì)給定的點(diǎn)間初始距離矩陣{dij}。對(duì)一個(gè)固定點(diǎn)j，運(yùn)算dik=min{dik,

dij+djk},

對(duì)所有i,

k

j

,

稱為三角運(yùn)算。(注意，這里允許i=k)定理：依次對(duì)j=1,2,…,n

執(zhí)行三角運(yùn)算，則dik

最終等于i

到k

間最短路的長(zhǎng)度。kjidij djkdik6.3.3Floyd-Warshall算法 (1962)算法基本步驟為；輸入權(quán)矩陣D(0)=D(2) 計(jì)算D(k)=（dij(k))nxn（k=1,2，3，....,n)其中 dij(k) =min[dij(k-1) , dik(k-1) + dkj(k-1) ](3) D(n)= （dij(n))nxn中元素di

(n)就是v

到v

的最短路j i j長(zhǎng)。6.3.3Floyd-Warshall

算法

(1962)例16 求圖所示的圖G中任意兩點(diǎn)間的最短路。解： 圖中有四條無(wú)向邊，每條均可化為兩條方向相反的有向邊。則：4

5

D

D(0)

2

2

v1

v12

v2

0 5 1 20 10

3 0 2 8

v3

6 02 4 4v2 v3 v4

52

0 5 1 2

0 (6) (7)

3 0 2 8

(7) (3) 02 4 4

D(1)

2

24

0

v40

v5v51

jd

(1)

min[d

(0)

,

d

(0)ij ij i1

d

(0)

]12

12

11d

(1)

min[d

(0)

,

d

(0)12

d

(0)

]11 11 11d

(1)

min[d

(0)

,

d

(0)11

d

(0)

]23 23 21d

(1)

min[d

(0)

,

d

(0)13

d

(0)

]42

42

41d

(1)

min[d

(0)

,

d

(0)12

d

(0)

]6.3.3Floyd-Warshall

算法

(1962)

5D(2)

2

24

0

ij iji

2 2

j

0 5 1 2 (7)

0 6 7 2

3 0 2 (5)

7 3 0

(7) 2 4 4d

(

2)

min[d

(1)

,

d

(1)

d

(1)

]5120(6)(7)302(7)(3)0244

0

52

8

D(1)

2

24

0

25d

(2)

min[d

(1)

,

d

(1)15 15 12

d

(1)

]23d

(2)

min[d

(1)

,

d

(1)43 43 42

d

(1)

]21d

(2)

min[d

(1)

,

d

(1)51 51 52

d

(1)

]D(3)

52

5

4

2302

2(6)30

(6)244

0

ijij i3 3

j

0

(4)

1

2

(6)

0 6 7d

(3)

min[d

(2)

,

d

(2)

d

(2)

]

52

24

6

0

52

D(5)

2

24

6

0

ijij i

4

0 4 1 2 6

0 6 7

D(4)

2 3 0 2 5

6 3 02 4 44

jd

(4)

min[d

(3)

,

d

(3)

d

(3)

]ij iji5 5

j

0 4 1 2 6

0 6 (6)

3 0 2 5

6 3 02 4 4d

(5)

min[d

(4)

,

d

(4)

d

(

4)

]

如果希望計(jì)算結(jié)果不僅給出任意兩點(diǎn)的最短路長(zhǎng)，而且給出具體的最短路徑，則在運(yùn)算過(guò)程中要保留下標(biāo)信息。213214

52

7125

52

0 5 1 2

0 6 72 8

D(2)

2 3 0 2 50 4

7 3 0

4 0

2 4 4325

2

75214

0

0

0 5 1 2

0 6 7D(1)

2 3 0

2 7 3

412 413

2 4

061325

52

4132 1 2

0 6 7D(3)

2 3 0 2 5

6 3 041322 4 4

4

2

6531

21213254233132346 620 2 564132 3413 0 445252 453 454 0

04123 113 214 61325

5 0

D(5)

2 3

325

241

6531

6.3.4

網(wǎng)絡(luò)的中心和重心1、網(wǎng)絡(luò)的中心假設(shè)為一網(wǎng)絡(luò)N中各點(diǎn)間的最短路長(zhǎng)矩陣。令，若中心。

ijn

nD

diji1

j

nd

v

max

d

1

i

nmin

d

vi

d

vk

，則稱點(diǎn)為該網(wǎng)絡(luò)的i

1,2,

,

n2、網(wǎng)絡(luò)的重心假設(shè)為一網(wǎng)絡(luò)N中各點(diǎn)間的最短路長(zhǎng)矩陣。設(shè)

gi

為點(diǎn)vi

（i=1,2,…,n）的權(quán)重系數(shù)，令，

（j=1,2,…,n），若6.3.4

網(wǎng)絡(luò)的中心和重心

h

v

j

ni ijg di

1則稱點(diǎn)為該網(wǎng)絡(luò)的重心。rj1

j

nmin

h

v

h

v

例6.10

已知某地區(qū)的空中交通網(wǎng)絡(luò)如圖6-15所示，其中點(diǎn)代表機(jī)場(chǎng)，邊表示連接機(jī)場(chǎng)間的航線，權(quán)wij表示機(jī)場(chǎng)間的航線距離（千米）。問(wèn)基地機(jī)場(chǎng)應(yīng)建在哪個(gè)機(jī)場(chǎng)，可使離基地最遠(yuǎn)的機(jī)場(chǎng)航班返回基地時(shí)所走的路程最近。6.3.4

網(wǎng)絡(luò)的中心和重心6.3.4

網(wǎng)絡(luò)的中心和重心圖6-15v4v3v1200020002500v2v5v630001500

6000 300018001500v7解：這是個(gè)選址問(wèn)題，實(shí)際要求出網(wǎng)絡(luò)的中心?？梢曰癁橐幌盗星笞疃搪穯?wèn)題或用Floyd算法求出任意兩點(diǎn)間的最短路長(zhǎng)dij。d

vi

max

dij

1

j

7i

1,

2,

,

7令表示若基地機(jī)場(chǎng)設(shè)在vi

，則離基地最遠(yuǎn)的機(jī)場(chǎng)距離為d(vi)

，然后選取其中的最小者即為所求的基地機(jī)場(chǎng)。計(jì)算結(jié)果如表6-4所示。

由于d(v6)

=4800最小，所以基地機(jī)場(chǎng)應(yīng)建在（網(wǎng)絡(luò)中心），此時(shí)離基地最遠(yuǎn)的機(jī)場(chǎng)v5的距離為4800千米。6.3.4

網(wǎng)絡(luò)的中心和重心jiv1v2v3v4v5v6v7d

vi

max

dij

1

j

7v103000500063009300450060009300v230000200033006300150030006300v350002000020005000250040005000v463003300200003000180033006300v593006300500030000480063009300v645001500250018004800015004800v760003000400033006300150006300表

6-4

例：設(shè)備更新問(wèn)題。某公司使用一臺(tái)設(shè)備，在每年年初，公司就要決定是購(gòu)買新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購(gòu)置新設(shè)備，就要支付一定的購(gòu)置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，這樣可以省去了購(gòu)置費(fèi)，但維修費(fèi)用就高了?，F(xiàn)在需要我們制定一個(gè)五年之內(nèi)的更新設(shè)備的計(jì)劃，使得五年內(nèi)購(gòu)置費(fèi)和維修費(fèi)總的支付費(fèi)用最小。這種設(shè)備每年年初的價(jià)格如下表所示。6.4

應(yīng)用舉例年份12345年初價(jià)格1111121213還已知使用不同時(shí)間（年）的設(shè)備所需要的維修費(fèi)如表7-2所示。使用年數(shù)每年維修費(fèi)用1234511111212136.4

應(yīng)用舉例

解：總費(fèi)用最小的設(shè)備更新計(jì)劃問(wèn)題可化為最短路的問(wèn)題。Vi

表示第i年年初購(gòu)進(jìn)一臺(tái)新設(shè)備弧(Vi，Vj)表示在第i年年初購(gòu)進(jìn)的設(shè)備一直使用到第j年年初，即第j-1年年底。此最短路問(wèn)題如圖下圖所示。

接著對(duì)上圖中的每條弧賦予權(quán)數(shù)。對(duì)于弧(Vi，Vj)

，它的權(quán)數(shù)應(yīng)為第i年年初購(gòu)進(jìn)設(shè)備使用到第j-1年年底所花費(fèi)的購(gòu)置費(fèi)及維修費(fèi)的總和。6.4

應(yīng)用舉例

從V1到V6的距離為53，其最短路徑有兩條，一條為v1

→

v3

→v6

，

，另一條為v1

→

v4

→v6

，

也就是說(shuō)一個(gè)方案為第1年初的購(gòu)置新設(shè)備使用到第2年底（第3年初），第3年初再購(gòu)置新設(shè)備使用到第5年底（第6年初）。第二個(gè)方案為第1年初購(gòu)置新設(shè)備使用到第3年底（第4年初），第4年初再購(gòu)置新設(shè)備使用到第5年底（第6年初），這兩種方案都使得總的支付為最小，均為53。6.4

應(yīng)用舉例

例6.8

運(yùn)行時(shí)間最短如圖6-13所示的航空運(yùn)輸網(wǎng)絡(luò)，結(jié)點(diǎn)代表城市，弧代表相應(yīng)的航班，弧旁的數(shù)字為兩城市之間的飛行時(shí)間（分鐘），要求尋找從結(jié)點(diǎn)1（起點(diǎn)）到結(jié)點(diǎn)10（終點(diǎn)）間飛行時(shí)間最短的最佳路線。6.4

應(yīng)用舉例

該航空運(yùn)輸網(wǎng)絡(luò)每條弧的權(quán)系數(shù)均為正數(shù)，可用雙標(biāo)號(hào)算法或逐次逼近法求得結(jié)點(diǎn)城市1到10之間的最短路徑為①→④→⑥→⑩，最短路長(zhǎng)為56+45+97=198分鐘。6.4

應(yīng)用舉例小結(jié)最短路有廣泛的應(yīng)用最短路的多種形式：無(wú)向圖，有向圖無(wú)循環(huán)圈，有向圖，混合圖，無(wú)負(fù)邊權(quán)，有負(fù)邊權(quán)，有負(fù)回路當(dāng)存在負(fù)權(quán)值邊時(shí)，F(xiàn)loyd算法比Dijkstra和逐次逼近算法效率高，且程序極簡(jiǎn)單。但Dijkstra和逐次逼近算法靈活若圖是前向的，則Dijkstra算法也可以求兩點(diǎn)間最長(zhǎng)路6.4

網(wǎng)路的最大流和最小截

網(wǎng)路流一般在有向圖上討論定義網(wǎng)路上支路的容量為其最大通過(guò)能力，記為

cij

，支路上的實(shí)際流量記為

fij圖中規(guī)定一個(gè)發(fā)點(diǎn)s，一個(gè)收點(diǎn)t節(jié)點(diǎn)沒(méi)有容量限制，流在節(jié)點(diǎn)不會(huì)存儲(chǔ)容量限制條件：0

fij

cij

9，7

7，7

5，5

3，2

5，3

6，3

2，1

3，1

4，4

6.4.1

網(wǎng)路的最大流的概念

平衡條件：滿足上述條件的網(wǎng)路流稱為可行流，總存在最大可行流當(dāng)支路上

fij

=

cij ，稱為飽和弧

最大流問(wèn)題也是一個(gè)線性規(guī)劃問(wèn)題viA(vi)B(vi)

v(f

)i

s0 i

s,

t

i

t

v(f

)f

v

j

B(vi)

v

j

A(

vi

)fjiij6.4

網(wǎng)路的最大流和最小截6.4.2

截集與截集容量

福特-富克森定理：網(wǎng)路的最大流等于最小截集容量st3 5(3,0)(2,0)(1,0)(1,0)(5,0)(2,0)定義：把網(wǎng)路分割為兩個(gè)成分的弧的最小集合，其中一

個(gè)成分包含s

點(diǎn)，另一個(gè)包含t

點(diǎn)

。一般包含s

點(diǎn)的成分中的節(jié)點(diǎn)集合用V表示，包含t點(diǎn)的成分中的節(jié)點(diǎn)集合用V表示截集容量是指截集中正向弧的容量之和C

(V

,V

)

ciji

Vj

V(3,0) 2

(4,0)

4 (5,0)6.4.3

確定網(wǎng)路最大流的標(biāo)號(hào)法增廣鏈(augmenting

path)增廣鏈中與s

到

t

方向一致的弧稱為前向弧，反之后向st4 532(3,0)(5,3)(5,1)(1,1)

(1,1)

45=3

5t=2

32=1

43=1增廣量

=min

ij=min(4,1,1,3,2)=

1st5432(3,1)

(5,4)(1,0)(1,0)

(5,2)前向弧后向弧ij

s2=4

c

ij

f

ij

ijfij ij弧，滿足

0

f

c

,前向弧

0

fij

cij

,

后向弧6.4.3

確定網(wǎng)路最大流的標(biāo)號(hào)法從任一個(gè)初始可行流出發(fā)，如

0流基本算法：找一條從

s

到

t

點(diǎn)的增廣鏈(augmenting

path)增廣過(guò)程：前向弧f

ij=fij

+q

, 后向弧

f

ij=fij

q增廣后仍是可行流若在當(dāng)前可行流下找不到增廣鏈，則已得到最大流最大流最小截的標(biāo)號(hào)法步驟第一步：標(biāo)號(hào)過(guò)程，找一條增廣鏈1、給源點(diǎn)s

標(biāo)號(hào)[s+,q(s)=

]，表示從

s

點(diǎn)有無(wú)限流出潛力2、找出與已標(biāo)號(hào)節(jié)點(diǎn)i

相鄰的所有未標(biāo)號(hào)節(jié)點(diǎn)j，若(i,j)是前向弧且飽和，則節(jié)點(diǎn)j

不標(biāo)號(hào)；(i,

j)是前向弧且未飽和，則節(jié)點(diǎn)j

標(biāo)號(hào)為[i+,q(j)]，表示從節(jié)點(diǎn)i

正向流出，可增廣q(j)=min[q(i),

cij

fij]

；(j,i)是后向弧，若fji=0，則節(jié)點(diǎn)j

不標(biāo)號(hào)；(j,

i)是后向弧，若fji>0，則節(jié)點(diǎn)j

標(biāo)號(hào)為[i

,q(j)]，表示從節(jié)點(diǎn)j

流向

i，可增廣q(j)=min[q(i), fji]

；3、重復(fù)步驟

2，可能出現(xiàn)兩種情況：節(jié)點(diǎn)

t

尚未標(biāo)號(hào)，但無(wú)法繼續(xù)標(biāo)記，說(shuō)明網(wǎng)路中已不存在增廣鏈，當(dāng)前流v(f)

就是最大流；所有獲標(biāo)號(hào)的節(jié)點(diǎn)在V

中，未獲標(biāo)號(hào)節(jié)點(diǎn)在V

中，V

與V

間的弧即為最小截集；算法結(jié)束節(jié)點(diǎn)

t

獲得標(biāo)號(hào)，找到一條增廣鏈，由節(jié)點(diǎn)t

標(biāo)號(hào)回溯可找出該增廣鏈；到第二步最大流最小截的標(biāo)號(hào)法步驟最大流最小截的標(biāo)號(hào)法步驟第二步：增廣過(guò)程1、對(duì)增廣鏈中的前向弧，令f

=f+q(t)，q(t)

為節(jié)點(diǎn)

t的標(biāo)記值2、對(duì)增廣鏈中的后向弧，令f

=f

q(t)3、非增廣鏈上的所有支路流量保持不變第三步：抹除圖上所有標(biāo)號(hào)，回到第一步一次只找一條增廣鏈，增廣一次換一張圖t134256(14,14)(9,9)s

(15,9) (16,15)(3,1)(12,10)(6,6)(4,3)(5,5)(22,22)(13,12)(7,5)(6,3)(19,10)最大流最小截集的標(biāo)號(hào)法舉例st134256(14,14)(9,9)(15,9)(16,15)(3,1)(12,10)(6,6)(4,3)(5,5)(22,22)(13,12)(7,5)(6,3)(19,10)t1346(14,14)(9,9)(16,15)(3,1)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)(s+,5)s

(15,10) 2

(12,10) 5(2+,2)(s+,

)(s+,6)(2

,6)(3+,1)(4+,1)(s+,

)(5

,2)(4+,2)最大流最小截集的標(biāo)號(hào)法舉例t1346(14,14)(9,9)(16,15)(3,1)s

(15,10) 2

(12,10) 5(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,3)(19,11)t134256(14,14)(9,9)s

(15,12) (16,15)(3,1)(12,12)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,1)(19,13)(s+,

)(s+,3)(2

,3)最小截集例6.12

例6.12

某航空公司必須確定從佛羅里達(dá)州的代頓灘機(jī)場(chǎng)（DAB）到印第安納州的拉菲德機(jī)場(chǎng)（LAF）之間每日的銜接航班數(shù)量。銜接航班必須在喬治亞州的亞特蘭大機(jī)場(chǎng)（ATL）經(jīng)停，然后再在伊利諾州的芝加哥機(jī)場(chǎng)（ORD）或密西根州的底特律機(jī)場(chǎng)（DTW）經(jīng)停一次。根據(jù)該航空公司與這些機(jī)場(chǎng)目前的協(xié)議，在這些城市對(duì)之間該公司每天可運(yùn)營(yíng)的航班數(shù)量有限制，詳見(jiàn)表6-5;該航空公司的目標(biāo)是，基于目前的限制因素使從佛羅里達(dá)州的代頓灘機(jī)場(chǎng)（DAB）到印第安納州的拉菲德機(jī)場(chǎng)（LAF）的每日銜接航班數(shù)量最大化。例6.12表6-5城市對(duì)每日最大航班數(shù)量DAB—ATL3ATL—ORD2ATL—DTW3ORD—LAF1DTW—LAF2例6.12

解：根據(jù)題意，可以畫出該航空公司的航線網(wǎng)絡(luò)如圖。結(jié)果:

DAB—ATL—ORD—LAF航線上1個(gè)航班，DAB—ATL—DTW—LAF航線上2個(gè)航班6.5

最小費(fèi)用流問(wèn)題一、最小費(fèi)用最大流問(wèn)題的提法假設(shè)有網(wǎng)絡(luò)G=（V，E，C）其每一條?。╲i，vj）∈G上，除了給定容量cij外，還給定一個(gè)單位流量的費(fèi)用dij(≥0)，記圖為G=（V，E，C，d）

。求G的一個(gè)可行流fij={fij}，使得流量W（f)=v,且總費(fèi)用特別地，當(dāng)要求f為最大流時(shí)，此問(wèn)題即為最小費(fèi)用最大流問(wèn)題。最小(vi

,v

j

E

)

dij

fijd

(

f

)

6.5

最小費(fèi)用流問(wèn)題稱為鏈

的費(fèi)用。如右圖所示的可增廣鏈

中，

{(v

,v

),(v

,v

),(v

,v

),(v

,v

)}s 1 2 3 3 4 5 t

{(v

,v

),(v

,v

)}2 1 5 4d(

)=(3+4+1+6)-(5+7)=

2。若

*是從隊(duì)vs到vt所有可增廣鏈中費(fèi)用最小的鏈，則稱

*

為最小費(fèi)可增廣鏈。

定義

1已知網(wǎng)絡(luò)G

=（V，E，C，d），f是G上的一個(gè)可行流，

為從vs到vt的（關(guān)于f

的）可增廣鏈，d(

)

dij

dij兩種解法：原始法和對(duì)偶法對(duì)偶算法的基本思想：先找一個(gè)流量<v的最小費(fèi)用流，如果把每條弧的單位費(fèi)用看成弧的長(zhǎng)度，也就是要選擇一條從發(fā)點(diǎn)到收點(diǎn)的最短路。然后尋找最小費(fèi)用流上的可增廣鏈，用最大流方法調(diào)整此鏈，并保持當(dāng)前流量下的最小費(fèi)用流，直到流量達(dá)到所需流量或最大流。二、最小費(fèi)用最大流問(wèn)題的解法定理 1：若f是流量為W(f)的最小費(fèi)用流，

是關(guān)于f的從vs到vt的一條最小費(fèi)用可增廣鏈，則f經(jīng)過(guò)調(diào)整流量

得到新可行流f

’

，一定是流量為W(

f

)+

的可行流中的最小費(fèi)用流。（證明略）由于dij

0，f={0}是流量為0的最小費(fèi)用流，所以初始最小費(fèi)用流可以取f(0)={0}，余下的問(wèn)題是如何尋找關(guān)于f的最小費(fèi)用可增廣鏈。為了計(jì)算方便，我們構(gòu)造長(zhǎng)度網(wǎng)絡(luò)。6.5

最小費(fèi)用流問(wèn)題（這里+∞的意義是此邊流量已減少到0，不能再減少，權(quán)為+∞的邊也可以去掉。）這樣得到的網(wǎng)絡(luò)L(f)稱為長(zhǎng)度網(wǎng)絡(luò)（將費(fèi)用看成長(zhǎng)度）。顯然在G中求關(guān)于f

的最小費(fèi)用可增廣鏈等價(jià)于在長(zhǎng)度網(wǎng)絡(luò)L(f)中求從vs到vt的最短路。（這里+∞的意義是：這條邊已飽和，不能再增大流量，否則要花費(fèi)很高的代價(jià)，實(shí)際無(wú)法實(shí)現(xiàn)，因此權(quán)為+∞的邊可從網(wǎng)絡(luò)中去掉）2.

當(dāng)邊（Vj，Vi）為原來(lái)G中邊（Vi

，Vj）的反向邊，令6.5

最小費(fèi)用流問(wèn)題定義2:

對(duì)網(wǎng)絡(luò)G=（V，E，C，d），有可行流f,

保持原網(wǎng)絡(luò)各點(diǎn)，每條邊用兩條方向相反的有向邊代替，各邊的權(quán)l(xiāng)ij按如下規(guī)則：6.5

最小費(fèi)用流問(wèn)題對(duì)偶算法的基本步驟如下：取零流為初始可行流，即 f(0)=0。若有f(k-1)

，流量為W(

f(k-1))<

v，構(gòu)造長(zhǎng)度網(wǎng)絡(luò)L

(f(k-1))

。在長(zhǎng)度網(wǎng)絡(luò)L

(

f(k-1))中求從vs到vt的最短路。若不存在最短路，則f(k-1)已為最大流，不存在流量等于v的流，停止；否則轉(zhuǎn)（4）。在G中與這條最短路相應(yīng)的可增廣鏈

上，作f(k)=

f(k-1)

此時(shí)f(k)

的流量為W

(f(k-1)

)+

,若W

(f(k-1)

)+

=V則停止，否則令f(k)代替

f(k-1)

返回（2）。例:

在左圖所示運(yùn)輸網(wǎng)絡(luò)上，求流量v為10的最小費(fèi)用流，邊上括號(hào)內(nèi)為（cij,dij)。解：

從f(0)=0

開(kāi)始，作L

(

f(0))如圖(b)，用Dijkstra算法求得網(wǎng)絡(luò)中最短路為vs

→v2

→

v1

→vt

，在網(wǎng)絡(luò)G中相應(yīng)的可增廣鏈

1={vs

,v2

,

v1

,vt

}，上用最大流算法進(jìn)行流的調(diào)整W(f(1))=

5，d(f(1))=

5×1＋5×2＋5×1=20結(jié)果見(jiàn)圖（C）。作L

(

f(1))

如圖（d），由于邊上有負(fù)權(quán)，所以求最短路不能用Dijkstra算法，可用逐次逼近法。最短路為vs

→

v1

→vt

，在網(wǎng)絡(luò)G內(nèi)相應(yīng)的可增廣鏈上進(jìn)行調(diào)整，得流f(2)

，如圖

(e)W(f(2))=7，d(f(2))=4×2＋5×1+5×2＋7×

1=

30作L

(

f(2))

如圖（f），最短路為vs

→v2

→

v3

→vt

，在網(wǎng)絡(luò)G內(nèi)相應(yīng)的可增廣鏈上進(jìn)行調(diào)整，得流f(3)

，如圖

(g)W(

f(3))=10=v，d(f(3))=

2×4＋8×1+5×2+3×3

+3×2

＋7×1

=48f(3)即為最小費(fèi)用流。最小費(fèi)用流例6.13

某航空公司要通過(guò)如圖6-20所示的網(wǎng)絡(luò)將貨物分別自結(jié)點(diǎn)1、2運(yùn)到結(jié)點(diǎn)5、6和7。該公司從起始地到目的地沒(méi)有直達(dá)航班，需要在其樞紐機(jī)場(chǎng)——節(jié)點(diǎn)3或4中轉(zhuǎn)。圖中結(jié)點(diǎn)旁的數(shù)字表示供給和需求量（噸），弧線上數(shù)字為對(duì)應(yīng)航線飛機(jī)的容量和每噸貨物的運(yùn)輸成本，現(xiàn)需要找出將貨物從起始地全部運(yùn)到目的地且總成本最低的最佳運(yùn)輸方式。例6.13據(jù)題意，需要將貨物從起始地全部運(yùn)到目的地，因此要求網(wǎng)絡(luò)的流量為75（噸），利用線性規(guī)劃方法或最小費(fèi)用流方法可解得該問(wèn)題的具體運(yùn)輸方案為：結(jié)點(diǎn)1到3：75噸；

結(jié)點(diǎn)2到3：25噸； 結(jié)點(diǎn)2到4：50噸；結(jié)點(diǎn)3到5：50噸；

結(jié)點(diǎn)3到6：50噸； 結(jié)點(diǎn)4到6：10噸；結(jié)點(diǎn)4到7：40噸；

其余航線結(jié)點(diǎn)間運(yùn)輸量均為零。此時(shí)，總的最低運(yùn)輸成本為1250。例6.13編制航班銜接表是航空公司制訂日常生產(chǎn)計(jì)劃的基礎(chǔ)。所謂航班銜接就是將本航空公司的一個(gè)到港航班與另一個(gè)離港航班銜接起來(lái)，生成若干個(gè)“航班串(through)”。在此基礎(chǔ)上生產(chǎn)調(diào)度人員為每個(gè)航班串指派執(zhí)行的飛機(jī)(即飛機(jī)指派問(wèn)題)和空勤機(jī)組(即機(jī)組指派問(wèn)題)。因此，航班銜接問(wèn)題是航空公司制定日常生產(chǎn)計(jì)劃的基礎(chǔ)，合理地安排航班可以更好的進(jìn)行人員配置、節(jié)約資源，并可以在很大程度上提高航空公司的效益。6.6 航班銜接問(wèn)題的網(wǎng)絡(luò)流模型6.6.1

航班銜接問(wèn)題的圖論模型1．基本概念