數(shù)模培訓(xùn)-圖論模型課件

圖論模型主講：費(fèi)文龍F(tuán)feiwl@數(shù)學(xué)建模培訓(xùn)8/16/20231南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍圖論模型主講：費(fèi)文龍數(shù)學(xué)建模培訓(xùn)8/5/2023圖論模型圖論基本概念最短路徑算法最小生成樹算法遍歷性問題二分圖與匹配網(wǎng)絡(luò)流問題關(guān)鍵路徑問題系統(tǒng)監(jiān)控模型著色模型8/16/20232南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍圖論模型圖論基本概念網(wǎng)絡(luò)流問題8/5/20232南京信息工程1、圖論的基本概念A(yù)BCD哥尼斯堡七橋示意圖問題1(哥尼斯堡七橋問題):能否從任一陸地出發(fā)通過每座橋恰好一次而回到出發(fā)點(diǎn)？8/16/20233南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍1、圖論的基本概念A(yù)BCD哥尼斯堡七橋示意圖問題1(哥尼斯堡ABDC七橋問題模擬圖歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地.8/16/20234南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍ABDC七橋問題模擬圖歐拉指出：8/5/20234南京信息工問題2(哈密頓環(huán)球旅行問題):十二面體的20個(gè)頂點(diǎn)代表世界上20個(gè)城市，能否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過每個(gè)城市恰好一次最后回到出發(fā)點(diǎn)？哈密頓圈（環(huán)球旅行游戲）8/16/20235南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍問題2(哈密頓環(huán)球旅行問題):哈密頓圈（環(huán)球旅行游戲）8/5問題3(四色問題):對任何一張地圖進(jìn)行著色，兩個(gè)共同邊界的國家染不同的顏色，則只需要四種顏色就夠了.問題4(關(guān)鍵路徑問題):一項(xiàng)工程任務(wù),大到建造一座大壩,一座體育中心,小至組裝一臺機(jī)床,一架電視機(jī),都要包括許多工序.這些工序相互約束,只有在某些工序完成之后,一個(gè)工序才能開始.即它們之間存在完成的先后次序關(guān)系,一般認(rèn)為這些關(guān)系是預(yù)知的,而且也能夠預(yù)計(jì)完成每個(gè)工序所需要的時(shí)間.這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間才能夠完成整個(gè)工程項(xiàng)目,影響工程進(jìn)度的要害工序是哪幾個(gè)？8/16/20236南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍問題3(四色問題):問題4(關(guān)鍵路徑問題):8/5/2023圖的定義圖論中的“圖”并不是通常意義下的幾何圖形或物體的形狀圖,而是以一種抽象的形式來表達(dá)一些確定的事物之間的聯(lián)系的一個(gè)數(shù)學(xué)系統(tǒng).

定義1一個(gè)有序二元組(V,E)稱為一個(gè)圖,記為G=(V,E),其中

①V稱為G的頂點(diǎn)集,V≠

,其元素稱為頂點(diǎn)或結(jié)點(diǎn),簡稱點(diǎn);②

E稱為G的邊集,其元素稱為邊,它聯(lián)結(jié)V中的兩個(gè)點(diǎn),如果這兩個(gè)點(diǎn)是無序的,則稱該邊為無向邊,否則,稱為有向邊.如果V={v1,v2,…,vn}是有限非空點(diǎn)集,則稱G為有限圖或n階圖.8/16/20237南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍圖的定義圖論中的“圖”并不是通常意義下的幾何圖形或物如果E的每一條邊都是無向邊,則稱G為無向圖(如圖1);如果E的每一條邊都是有向邊,則稱G為有向圖(如圖2);否則,稱G為混合圖.圖1圖2并且常記V={v1,v2,…,vn},|V|

=n

;E={e1,e2,…,em}(ek=vivj),|E|

=m.稱點(diǎn)vi,vj為邊vivj的端點(diǎn).在有向圖中,稱點(diǎn)vi,vj分別為邊vivj的始點(diǎn)和終點(diǎn).該圖稱為(n,m)圖8/16/20238南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍如果E的每一條邊都是無向邊,則稱G為無向圖(如圖1

對于一個(gè)圖G=(V,E),人們常用圖形來表示它,

稱其為圖解.

凡是有向邊,

在圖解上都用箭頭標(biāo)明其方向.例如,設(shè)V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4},則G=(V,E)是一個(gè)有4個(gè)頂點(diǎn)和6條邊的圖,G的圖解如下圖所示.8/16/20239南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍對于一個(gè)圖G=(V,E),人們常用圖形來表一個(gè)圖會(huì)有許多外形不同的圖解,下面兩個(gè)圖表示同一個(gè)圖G=(V,E)的圖解.其中V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4}.

這兩個(gè)圖互為同構(gòu)圖,今后將不計(jì)較這種外形上的差別,而用一個(gè)容易理解的、確定的圖解去表示一個(gè)圖.8/16/202310南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍一個(gè)圖會(huì)有許多外形不同的圖解,下面兩個(gè)圖表示同一個(gè)有邊聯(lián)結(jié)的兩個(gè)點(diǎn)稱為相鄰的點(diǎn),有一個(gè)公共端點(diǎn)的邊稱為相鄰邊.邊和它的端點(diǎn)稱為互相關(guān)聯(lián).常用d(v)表示圖G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目,d(v)稱為頂點(diǎn)v的度數(shù).對于有向圖,還有出度和入度之分.

用N(v)表示圖G中所有與頂點(diǎn)v相鄰的頂點(diǎn)的集合.d(v1)=d(v3)=d(v4)=4,d(v2)=2.握手定理：8/16/202311南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍有邊聯(lián)結(jié)的兩個(gè)點(diǎn)稱為相鄰的點(diǎn),有一個(gè)公共端點(diǎn)的邊稱我們今后只討論有限簡單圖：

(1)頂點(diǎn)個(gè)數(shù)是有限的;(2)任意一條邊有且只有兩個(gè)不同的點(diǎn)與它相互關(guān)聯(lián);(3)若是無向圖,則任意兩個(gè)頂點(diǎn)最多只有一條邊與之相聯(lián)結(jié);(4)若是有向圖,則任意兩個(gè)頂點(diǎn)最多只有兩條邊與之相聯(lián)結(jié).當(dāng)兩個(gè)頂點(diǎn)有兩條邊與之相聯(lián)結(jié)時(shí)，這兩條邊的方向相反.如果某個(gè)有限圖不滿足(2)(3)(4),可在某條邊上增設(shè)頂點(diǎn)使之滿足.8/16/202312南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍我們今后只討論有限簡單圖：(1)頂點(diǎn)個(gè)數(shù)是有限的;8/

定義2若將圖G的每一條邊e都對應(yīng)一個(gè)實(shí)數(shù)F(e),則稱F(e)為該邊的權(quán),并稱圖G為賦權(quán)圖(網(wǎng)絡(luò)),記為G=(V,E,F).

定義3任意兩點(diǎn)均有通路的圖稱為連通圖.

定義4連通而無圈的圖稱為樹,常用T表示樹.8/16/202313南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍定義2若將圖G的每一條邊e都對應(yīng)一個(gè)實(shí)數(shù)F(e)

例一擺渡人欲將一只狼,一頭羊,一籃菜從河西渡過河到河?xùn)|.由于船小,一次只能帶一物過河，并且狼與羊,羊與菜不能獨(dú)處.給出渡河方法.

解：用四維0-1向量表示(人,狼,羊,菜)在河西岸的狀態(tài)(在河西岸則分量取1,否則取0),共有24=16種狀態(tài).在河?xùn)|岸的狀態(tài)類似記作.由題設(shè),狀態(tài)(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允許的,從而對應(yīng)狀態(tài)(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允許的.

以可允許的10個(gè)狀態(tài)向量作為頂點(diǎn),將可能互相轉(zhuǎn)移的狀態(tài)用線段連接起來構(gòu)成一個(gè)圖.

根據(jù)此圖便可找到渡河方法.8/16/202314南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍例一擺渡人欲將一只狼,一頭羊,一籃菜從河西渡過河到(1,1,1,1)

(1,1,1,0)

(1,1,0,1)

(1,0,1,1)

(1,0,1,0)(0,0,0,0)

(0,0,0,1)

(0,0,1,0)

(0,1,0,0)

(0,1,0,1)(0,1,0,1)

(0,1,0,0)

(0,0,1,0)

(0,0,0,1)

(0,0,0,0)(1,0,1,0)

(1,0,1,1)

(1,1,0,1)

(1,1,1,0)

(1,1,1,1)河西=(人,狼,羊,菜)河?xùn)|=(人,狼,羊,菜)

將10個(gè)頂點(diǎn)分別記為A1,A2,…,A10,則渡河問題化為在該圖中求一條從A1到A10的路.

從圖中易得到兩條路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.8/16/202315南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍(1,1,1,1)(1,1,1,0)(1,1,0,1圖的矩陣表示⑴

鄰接矩陣鄰接矩陣表示了點(diǎn)與點(diǎn)之間的鄰接關(guān)系.一個(gè)n階圖G的鄰接矩陣A=(aij)n×n,其中

8/16/202316南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍圖的矩陣表示⑴鄰接矩陣鄰接矩陣表示了點(diǎn)與點(diǎn)之間無向圖G的鄰接矩陣A是一個(gè)對稱矩陣.

⑵

權(quán)矩陣一個(gè)n階賦權(quán)圖G=(V,E,F)的權(quán)矩陣A=(aij)n×n,其中

有限簡單圖基本上可用權(quán)矩陣來表示.8/16/202317南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍無向圖G的鄰接矩陣A是一個(gè)對稱矩陣.⑵權(quán)矩陣無向圖G的權(quán)矩陣A是一個(gè)對稱矩陣.

8/16/202318南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍無向圖G的權(quán)矩陣A是一個(gè)對稱矩陣.8/5/202318南京⑶

關(guān)聯(lián)矩陣（略）一個(gè)有m條邊的n階有向圖G的關(guān)聯(lián)矩陣A=(aij)n×m,其中

若vi是ej的始點(diǎn);若vi是ej的終點(diǎn);若vi與ej不關(guān)聯(lián).有向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有一個(gè)1,有且僅有一個(gè)

-

1.8/16/202319南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍⑶關(guān)聯(lián)矩陣（略）一個(gè)有m條邊的n階有向圖G的關(guān)一個(gè)有m條邊的n階無向圖G的關(guān)聯(lián)矩陣A=(aij)n×m,其中

若vi與ej關(guān)聯(lián);若vi與ej不關(guān)聯(lián).無向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有兩個(gè)1.8/16/202320南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍一個(gè)有m條邊的n階無向圖G的關(guān)聯(lián)矩陣A=(aij2、最短路徑算法

定義1設(shè)P(u,v)是賦權(quán)圖G=(V,E,F)中從點(diǎn)u到v的路徑,用E(P)表示路徑P(u,v)中全部邊的集合,記則稱F(P)為路徑P(u,v)的權(quán)或長度(距離).

定義2若P0(u,v)是G

中連接u,v的路徑,且對任意在G

中連接u,v的路徑P(u,v)都有F(P0)≤F(P),則稱P0(u,v)是G

中連接u,v的最短路.8/16/202321南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍2、最短路徑算法定義1設(shè)P(u,v)是賦權(quán)圖G重要性質(zhì)：

若v0v1…vm是圖G中從v0到vm的最短路,則

1≤k≤m,v0v1…vk必為G中從v0到vk的最短路.

即：最短路是一條路，且最短路的任一段也是最短路.求非負(fù)賦權(quán)圖G中某一點(diǎn)到其它各點(diǎn)最短路，一般用Dijkstra標(biāo)號算法；求非負(fù)賦權(quán)圖上任意兩點(diǎn)間的最短路，一般用Floyd算法.這兩種算法均適用于有向非負(fù)賦權(quán)圖.下面分別介紹兩種算法的基本過程.8/16/202322南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍重要性質(zhì)：若v0v1…vm是圖G中從v0到vDijkstra算法指標(biāo)（a為起點(diǎn)）

設(shè)T為V的子集，P=V-T且a∈T，對所有t∈T，設(shè)l(t)表示從a到t的所有通路中距離最短的一條的長度，且這條路徑中不包含T中其他的結(jié)點(diǎn)，則稱l(t)為t關(guān)于集合P的指標(biāo)，若不存在這樣的路徑，這記l(t)=∞注：l(t)不一定是從a到t的最短路徑，因?yàn)樽疃搪窂街锌赡馨琓中其他的節(jié)點(diǎn)。定理1

若t是T中關(guān)于P由最小指標(biāo)的結(jié)點(diǎn)，則l(t)是a和t之間的最短距離。定理2

設(shè)T為V的子集，P=V-T，設(shè)

(1)對P中的任一點(diǎn)p,存在一條從a到p的最短路徑,這條路徑僅有P中的點(diǎn)構(gòu)成,

(2)對于每一點(diǎn)t,它關(guān)于P的指標(biāo)為l(t),令x為最小指標(biāo)所在的點(diǎn),即:l(x)=min(l(t))(tT),

(3)令P'=P{x},T'=T-{x},l'(t)表示T'中結(jié)點(diǎn)t關(guān)于P'的指標(biāo),則

l'(t)=min{l(t),l(x)+w(x,t)}8/16/202323南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍Dijkstra算法指標(biāo)（a為起點(diǎn)）

設(shè)T為V的子集Dijkstra算法（求a點(diǎn)到其他點(diǎn)的最短路徑）1、初始化，P={a}，T=V-{a}，對每個(gè)結(jié)點(diǎn)t計(jì)算指標(biāo)l(t)=w(a,t)2、設(shè)x為T中關(guān)于P有最小指標(biāo)的點(diǎn),

即:l(x)=min(l(t))(t∈T),3、若T=Ф,則算法結(jié)束;

否則,令P'=PU{x},T'=T-{x}

按照公式l'(t)=min{l(t),l(x)+w(x,t)},

計(jì)算T'中每一個(gè)結(jié)點(diǎn)t'關(guān)于P'的指標(biāo).4、P'代替P,T'代替T,重復(fù)步驟2,3

（其中：w(x,y)為圖的權(quán)矩陣）

8/16/202324南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍Dijkstra算法（求a點(diǎn)到其他點(diǎn)的最短路徑）1、初始化，改進(jìn)Dijkstra算法（求a點(diǎn)到其他點(diǎn)的最短路徑）1、初始化，P={a}，T=V-{a}，對每個(gè)結(jié)點(diǎn)t計(jì)算指標(biāo)l(t)=w(a,t),pro(t)=a;2、設(shè)x為T中關(guān)于P有最小指標(biāo)的點(diǎn),

即:l(x)=min(l(t))(t∈T);3、若T=Ф,則算法結(jié)束;

否則,令P‘=PU{x},T’=T-{x}

按照公式l‘(t)=min{l(t),l(x)+w(x,t)},

計(jì)算T’中每一個(gè)結(jié)點(diǎn)t‘關(guān)于P’的指標(biāo).

若l(x)+w(x,t)<l(t),pro(t)=x;4、P'代替P,T'代替T,重復(fù)步驟2,3

（其中：w(x,y)為圖的權(quán)矩陣）

8/16/202325南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍改進(jìn)Dijkstra算法（求a點(diǎn)到其他點(diǎn)的最短路徑）1、初始ABCDEFGHA02∞∞∞∞6∞B207∞∞13∞C∞7043∞∞∞D(zhuǎn)∞∞405∞∞2E∞∞3502∞2F∞1∞∞201∞G63∞∞∞104H∞∞∞22∞40例求下圖中A點(diǎn)到其他點(diǎn)的最短路.8/16/202326南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍ABCDEFGH例求Floyd算法（求任意兩點(diǎn)的最短路徑）設(shè)A=(aij)n×n為賦權(quán)圖G=(V,E,F)的權(quán)矩陣,dij表示從vi到vj點(diǎn)的距離,rij表示從vi到vj點(diǎn)的最短路中前一個(gè)點(diǎn)的編號.

①賦初值.對所有i,j,dij=aij,rij=j.k=1.轉(zhuǎn)向②.

②更新dij,rij.對所有i,j,若dik+dkj＜dij,則令dij=dik+dkj,rij=k,轉(zhuǎn)向③;

③終止判斷.若k=n終止;否則令k=k+1,轉(zhuǎn)向②.

最短路線可由rij得到.8/16/202327南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍F(tuán)loyd算法（求任意兩點(diǎn)的最短路徑）設(shè)A=(a

0123456700281∞∞∞∞1206∞1∞∞∞28607512∞31∞70∞∞9∞4∞15∞03∞85∞∞1∞30466∞∞29∞4037∞∞∞∞8630例求下圖中任意兩點(diǎn)間的最短路.8/16/202328南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍01234567例求以下僅從圖上進(jìn)行直觀操作.

根據(jù)若dik+dkj＜dij,則令dij=dik+dkj.將原來的賦權(quán)值改變?yōu)閨v2v4|=4,|v5v6|=3.再依次改變?yōu)閨v1v2|=5,|v0v2|=7.接下來根據(jù)若dij>dik+dkj,則刪除vi到vj的連線.得到8/16/202329南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍以下僅從圖上進(jìn)行直觀操作.根據(jù)若dik+dkj＜從上圖中容易得到任意兩點(diǎn)間的最短路.例如,v1到v6的路有三條：

v1v0v3v2v6(長度為12),

v1v4v5v2v6(長度為7),

v1v4v7v6(長度為12).8/16/202330南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍從上圖中容易得到任意兩點(diǎn)間的最短路.例如,v1到v6的路有三例設(shè)備更新問題某企業(yè)每年年初,都要作出決定,如果繼續(xù)使用舊設(shè)備,要付維修費(fèi)；若購買一臺新設(shè)備,要付購買費(fèi).試制定一個(gè)5年更新計(jì)劃,使總支出最少.已知設(shè)備在每年年初的購買費(fèi)分別為11,11,12,12,13.使用不同時(shí)間設(shè)備所需的維修費(fèi)分別為5,6,8,11,18.

解設(shè)bi表示設(shè)備在第i年年初的購買費(fèi),ci表示設(shè)備使用i年后的維修費(fèi),

V={v1,v2,…,v6},點(diǎn)vi表示第i年年初購進(jìn)一臺新設(shè)備,虛設(shè)一個(gè)點(diǎn)v6表示第5年年底.

E={vivj|1≤i＜j≤6}.8/16/202331南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍例設(shè)備更新問題某企業(yè)每年年初,都要作出決定,如果這樣上述設(shè)備更新問題就變?yōu)椋涸谟邢蛸x權(quán)圖G=(V,E,F)(圖解如下)中求v1到v6的最短路問題.8/16/202332南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍這樣上述設(shè)備更新問題就變?yōu)椋涸谟邢蛸x權(quán)圖G=(V由實(shí)際問題可知,設(shè)備使用三年后應(yīng)當(dāng)更新,因此刪除該圖中v1到v5,v1到v6,v2到v6的連線；又設(shè)備使用一年后就更新則不劃算,因此再刪除該圖中v1v2,v2v3,v3v4,v4v5,v5v6五條連線后得到從上圖中容易得到v1到v6只有兩條路：v1v3v6和v1v4v6.

而這兩條路都是v1到v6的最短路.8/16/202333南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍由實(shí)際問題可知,設(shè)備使用三年后應(yīng)當(dāng)更新,因此刪除該圖3、最小生成樹

由樹的定義不難知道,任意一個(gè)連通的(n,m)圖G適當(dāng)去掉m

-

n+1條邊后,都可以變成樹,這棵樹稱為圖G的生成樹.

設(shè)T是圖G的一棵生成樹,用F(T)表示樹T中所有邊的權(quán)數(shù)之和,F(T)稱為樹T的權(quán).

一個(gè)連通圖G的生成樹一般不止一棵,圖G的所有生成樹中權(quán)數(shù)最小的生成樹稱為圖G的最小生成樹.

求最小生成樹問題有很廣泛的實(shí)際應(yīng)用.例如,把n個(gè)鄉(xiāng)鎮(zhèn)用高壓電纜連接起來建立一個(gè)電網(wǎng),使所用的電纜長度之和最短,即費(fèi)用最小,就是一個(gè)求最小生成樹問題.8/16/202334南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍3、最小生成樹由樹的定義不難知道,任意一個(gè)連通的Kruskal算法：從未選入樹中的邊中選取權(quán)重最小的且不構(gòu)成回路的邊加入到樹中.（判斷回路比較麻煩）Prim算法：把結(jié)點(diǎn)分成兩個(gè)集合，已加入樹中的(P)和未加入樹中的(Q)，然后每次選擇一個(gè)點(diǎn)在P中一個(gè)點(diǎn)在Q中的權(quán)重最小的邊，加入樹中，并把相應(yīng)點(diǎn)加入P中。其最小生成樹如下：類似地,可定義連通圖G的最大生成樹.8/16/202335南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍Kruskal算法：從未選入樹中的邊中選取權(quán)重最小的且不構(gòu)成例選址問題現(xiàn)準(zhǔn)備在n個(gè)居民點(diǎn)v1,v2,…,vn中設(shè)置一銀行.問設(shè)在哪個(gè)點(diǎn),可使最大服務(wù)距離最小?若設(shè)置兩個(gè)銀行,問設(shè)在哪兩個(gè)點(diǎn)?

模型假設(shè)假設(shè)各個(gè)居民點(diǎn)都有條件設(shè)置銀行,并有路相連,且路長已知.

模型建立與求解用Floyd算法求出任意兩個(gè)居民點(diǎn)vi,vj之間的最短距離,并用dij表示.⑴設(shè)置一個(gè)銀行,銀行設(shè)在vi點(diǎn)的最大服務(wù)距離為8/16/202336南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍例選址問題現(xiàn)準(zhǔn)備在n個(gè)居民點(diǎn)v1,v2,求k,使即若設(shè)置一個(gè)銀行,則銀行設(shè)在

vk點(diǎn),可使最大服務(wù)距離最小.⑵設(shè)置兩個(gè)銀行,假設(shè)銀行設(shè)在vs,vt點(diǎn)使最大服務(wù)距離最小.記則s,t滿足：進(jìn)一步,若設(shè)置多個(gè)銀行呢？8/16/202337南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍求k,使即若設(shè)置一個(gè)銀行,則銀行設(shè)在vk點(diǎn),可使4、遍歷性問題一、歐拉圖G=(V,E)為一連通無向圖經(jīng)過G中每條邊至少一次的回路稱為巡回；經(jīng)過G中每條邊正好一次的巡回稱為歐拉巡回；存在歐拉巡回的圖稱為歐拉圖。二、中國郵遞員問題（CPP－chinesepostmanproblem）

一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？這一問題是我國管梅谷教授1962年首先提出，國際上稱之為中國郵遞員問題。

8/16/202338南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍4、遍歷性問題一、歐拉圖8/5/202338南京信息工程大學(xué)解法：若本身就是歐拉圖，則直接可以找到一條歐拉巡回就是本問題的解。若不是歐拉圖，必定有偶數(shù)個(gè)奇度數(shù)結(jié)點(diǎn)，在這些奇度數(shù)點(diǎn)之間添加一些邊，使之變成歐拉圖，再找出一個(gè)歐拉巡回。具體解法：Fleury算法+Edmonds最小對集算法8/16/202339南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍8/5/202339南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍三、哈密爾頓圖G=(V,E)為一連通無向圖經(jīng)過G中每點(diǎn)一次且正好一次的路徑稱為哈密爾頓路徑；經(jīng)過G中每點(diǎn)一次且正好一次的回路稱為哈密爾頓回路；存在哈密爾頓回路的圖稱為哈密爾頓圖。四、旅行商問題（TSP－travelingsalesmanproblem）一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計(jì)一條最短的旅行路線？即：從駐地出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后返回駐地（最小哈密爾頓回路）對于n個(gè)節(jié)點(diǎn)的旅行商問題，n個(gè)節(jié)點(diǎn)的任意一個(gè)全排列都是問題的一個(gè)可能解（假設(shè)任意兩個(gè)點(diǎn)之間都有邊）。G個(gè)節(jié)點(diǎn)的全排列有(n-1)!個(gè)，因此間題歸結(jié)為在(n-1)!個(gè)回路中選取最小回路。TSP問題的解法屬于NP完全問題，一般只研究其近似解法8/16/202340南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍三、哈密爾頓圖8/5/202340南京信息工程大學(xué)數(shù)理學(xué)院最鄰近算法(1)選取任意一個(gè)點(diǎn)作為起始點(diǎn),找出與該點(diǎn)相關(guān)聯(lián)的權(quán)重最小的邊,形成一條初始路徑.

(2)找出與最新加入到路徑中的點(diǎn)相關(guān)聯(lián)的權(quán)重最小的邊加入到路徑中,且要求不再路徑中產(chǎn)生回路.

(3)重復(fù)(2)直到所有的結(jié)點(diǎn)都加入到路徑中.

(4)將起點(diǎn)和最后加入的結(jié)點(diǎn)之間的邊加入到路徑中,形成Hamilton回路.其他數(shù)值算法：

人工神經(jīng)元方法，

遺傳算法等等8/16/202341南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍最鄰近算法8/5/202341南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文5、二分圖與匹配

定義1設(shè)X,Y都是非空有限集,且X∩Y=

,

E

{xy|x∈X,y∈Y},稱G=(X,Y,E)為二部圖.

二部圖可認(rèn)為是有限簡單無向圖.如果X中的每個(gè)點(diǎn)都與Y中的每個(gè)點(diǎn)鄰接,則稱G=(X,Y,E)為完備二部圖.若F：E→R+,則稱G=(X,Y,E,F)為二部賦權(quán)圖.二部賦權(quán)圖的權(quán)矩陣一般記作A=(aij)|X|×|Y|

,其中aij=F(xiyj).8/16/202342南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍5、二分圖與匹配定義1設(shè)X,Y都是非空有限集,

定義2設(shè)G=(X,Y,E)為二部圖,且M

E.若M中任意兩條邊在G中均不鄰接,則稱M是二部圖G的一個(gè)匹配.定義3設(shè)M是二部圖G的一個(gè)匹配,如果G的每一個(gè)點(diǎn)都是M中邊的頂點(diǎn),則稱M是二部圖G的完美匹配；如果G中沒有另外的匹配M0,使|M0|＞|M|,則稱M是二部圖G的最大匹配.在二部賦權(quán)圖G=(X,Y,E,F)中,權(quán)數(shù)最大的最大匹配M稱為二部賦權(quán)圖G的最佳匹配.顯然,每個(gè)完美匹配都是最大匹配,反之不一定成立.8/16/202343南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍定義2設(shè)G=(X,Y,E)為二部圖,且M工作安排問題之一給n個(gè)工作人員x1,x2,…,xn安排n項(xiàng)工作y1,y2,…,yn.n個(gè)工作人員中每個(gè)人能勝任一項(xiàng)或幾項(xiàng)工作,但并不是所有工作人員都能從事任何一項(xiàng)工作.比如x1能做y1,y2工作,x2能做y2,y3,y4工作等.這樣便提出一個(gè)問題,對所有的工作人員能不能都分配一件他所能勝任的工作？

我們構(gòu)造一個(gè)二部圖G=(X,Y,E),這里X={x1,x2,…,xn},Y={y1,y2,…,yn},并且當(dāng)且僅當(dāng)工作人員xi勝任工作yj時(shí),xi與yj才相鄰.于是,問題轉(zhuǎn)化為求二部圖的一個(gè)完美匹配.因?yàn)閨X|=|Y|,所以完美匹配即為最大匹配.8/16/202344南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍工作安排問題之一給n個(gè)工作人員x1,x2,…求二部圖G=(X,Y,E)的最大匹配算法(匈牙利算法,交替鏈算法)迭代步驟:從G的任意匹配M開始.①將X中M的所有非飽和點(diǎn)都給以標(biāo)號0和標(biāo)記*,轉(zhuǎn)向②.

M的非飽和點(diǎn)即非M的某條邊的頂點(diǎn).②若X中所有有標(biāo)號的點(diǎn)都已去掉了標(biāo)記*,則M是G的最大匹配.否則任取X中一個(gè)既有標(biāo)號又有標(biāo)記*的點(diǎn)xi,去掉xi的標(biāo)記*,轉(zhuǎn)向③.③找出在G中所有與xi鄰接的點(diǎn)yj,若所有這樣的yj都已有標(biāo)號,則轉(zhuǎn)向②,否則轉(zhuǎn)向④.8/16/202345南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍求二部圖G=(X,Y,E)的最大匹配算法④對與xi鄰接且尚未給標(biāo)號的yj都給定標(biāo)號i.若所有的

yj都是M的飽和點(diǎn),則轉(zhuǎn)向⑤,否則逆向返回.即由其中M的任一個(gè)非飽和點(diǎn)

yj的標(biāo)號i找到xi,再由

xi的標(biāo)號k找到

yk,…,最后由

yt的標(biāo)號s找到標(biāo)號為0的xs時(shí)結(jié)束,獲得M-增廣路xsyt…xiyj,記P={xsyt,…,xiyj

},重新記M為M⊕P,轉(zhuǎn)向①.不必理會(huì)M-增廣路的定義.

M⊕P=M∪P

\

M∩P,是對稱差.

⑤

將yj在M中與之鄰接的點(diǎn)xk,給以標(biāo)號j和標(biāo)記*,轉(zhuǎn)向②.8/16/202346南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍④對與xi鄰接且尚未給標(biāo)號的yj都給定標(biāo)號i.例求下圖所示二部圖G的最大匹配.解①取初始匹配M0={x2

y2,x3

y3,x5

y5}(上圖粗線所示).②給X中M0的兩個(gè)非飽和點(diǎn)x1,x4都給以標(biāo)號0和標(biāo)記*(如下圖所示).③

去掉x1的標(biāo)記*,將與x1鄰接的兩個(gè)點(diǎn)y2,y3都給以標(biāo)號1.

因?yàn)閥2,y3都是M0的兩個(gè)飽和點(diǎn),所以將它們在M0中鄰接的兩個(gè)點(diǎn)x2,x3都給以相應(yīng)的標(biāo)號和標(biāo)記*(如下圖所示).8/16/202347南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍例求下圖所示二部圖G的最大匹配.解①取初始匹配M0④

去掉x2的標(biāo)記*,將與x2鄰接且尚未給標(biāo)號的三個(gè)點(diǎn)y1,y4,y5都給以標(biāo)號2(如下圖所示).⑤

因?yàn)閥1是M0的非飽和點(diǎn),所以順著標(biāo)號逆向返回依次得到x2,y2,直到x1為0為止.于是得到M0的增廣路x1y2x2y1,記P={x1y2,y2x2,x2y1}.取M1=M0⊕P={x1y2,x2y1,x3

y3,x5

y5},則M1是比M多一邊的匹配(如下圖所示).8/16/202348南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍④去掉x2的標(biāo)記*,將與x2鄰接且尚未給標(biāo)號的三⑥

再給X中M1的非飽和點(diǎn)x4給以標(biāo)號0和標(biāo)記*,然后去掉x4的標(biāo)記*,將與x4鄰接的兩個(gè)點(diǎn)y2,y3都給以標(biāo)號4.因?yàn)閥2,y3都是M1的兩個(gè)飽和點(diǎn),所以將它們在M1中鄰接的兩個(gè)點(diǎn)x1,x3都給以相應(yīng)的標(biāo)號和標(biāo)記*(如下圖所示).⑦

去掉x1的標(biāo)記*,因?yàn)榕cx1鄰接的兩個(gè)點(diǎn)y2,y3都有標(biāo)號4,所以去掉x3的標(biāo)記*.而與x3鄰接的兩個(gè)點(diǎn)y2,y3也都有標(biāo)號4,此時(shí)X中所有有標(biāo)號的點(diǎn)都已去掉了標(biāo)記*(如下圖所示),因此M1是G的最大匹配.

G不存在飽和X的每個(gè)點(diǎn)的匹配,當(dāng)然也不存在完美匹配.8/16/202349南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍⑥再給X中M1的非飽和點(diǎn)x4給以標(biāo)號0和標(biāo)記*,工作安排問題之二給n個(gè)工作人員x1,x2,…,xn安排n項(xiàng)工作y1,y2,…,yn.如果每個(gè)工作人員工作效率不同,要求工作分配的同時(shí)考慮總效率最高.我們構(gòu)造一個(gè)二部賦權(quán)圖G=(X,Y,E,F),這里X={x1,x2,…,xn},Y={y1,y2,…,yn},F(xi

yj)為工作人員xi勝任工作yj時(shí)的工作效率.則問題轉(zhuǎn)化為：求二部賦權(quán)圖G的最佳匹配.在求G

的最佳匹配時(shí),總可以假設(shè)G為完備二部賦權(quán)圖.若xi與yj不相鄰,可令F(xi

yj)=0.同樣地,還可虛設(shè)點(diǎn)x或y,使|X|=|Y|.如此就將G

轉(zhuǎn)化為完備二部賦權(quán)圖,而且不會(huì)影響結(jié)果.8/16/202350南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍工作安排問題之二給n個(gè)工作人員x1,x2,…

定義設(shè)G=(X,Y,E,F)為完備的二部賦權(quán)圖,

若L：X∪Y→R+滿足：

x∈X,y∈Y,L(x)+L(y)≥F(xy),則稱L為G的一個(gè)可行點(diǎn)標(biāo)記,

記相應(yīng)的生成子圖為GL=(X,Y,EL,F),這里EL

={xy∈E|L(x)+L(y)=F(xy)}.

求完備二部賦權(quán)圖G=(X,Y,E,F)的最佳匹配算法迭代步驟：

設(shè)G=(X,Y,E,F)為完備的二部賦權(quán)圖,L是其一個(gè)初始可行點(diǎn)標(biāo)記,通常取

L(x)=max{F(xy)|y∈Y},x∈X,

L(y)=0,y∈Y.8/16/202351南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍定義設(shè)G=(X,Y,E,F)為完備的二部賦M是GL的一個(gè)匹配.①若X的每個(gè)點(diǎn)都是飽和的,則M是最佳匹配.否則取M的非飽和點(diǎn)u∈X,令S={u},T=

,轉(zhuǎn)向②.②記NL(S)={v|u∈S,uv∈GL}.

若NL(S)=T,則GL沒有完美匹配,轉(zhuǎn)向③.否則轉(zhuǎn)向④.③調(diào)整標(biāo)記,計(jì)算aL=min{L(x)+L(y)-

F(xy)|x∈S,y∈Y\T}.由此得新的可行點(diǎn)標(biāo)記

令L=H,GL

=GH

,重新給出GL的一個(gè)匹配M,轉(zhuǎn)向①.④取y∈NL

(S)\T,若y是M的飽和點(diǎn),轉(zhuǎn)向⑤.否則,轉(zhuǎn)向⑥.⑤

設(shè)xy∈M,則令S=S∪{x},T=T∪{y},轉(zhuǎn)向②.⑥

在GL中的u-

y路是M-增廣路,設(shè)為P,并令M=M⊕P,轉(zhuǎn)向①.8/16/202352南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍M是GL的一個(gè)匹配.①若X的每個(gè)點(diǎn)都是飽和的,則M是最佳6、網(wǎng)絡(luò)流問題

定義1設(shè)G=(V,E)為有向圖,在V中指定一點(diǎn)稱為發(fā)點(diǎn)(記為vs),和另一點(diǎn)稱為收點(diǎn)(記為vt),其余點(diǎn)叫做中間點(diǎn).對每一條邊vivj∈E,對應(yīng)一個(gè)非負(fù)實(shí)數(shù)Cij,稱為它的容量.這樣的G稱為容量網(wǎng)絡(luò),簡稱網(wǎng)絡(luò),記作G=(V,E,C).定義2網(wǎng)絡(luò)G=(V,E,C)中任一條邊vivj有流量

fij,稱集合

f={

fij}為網(wǎng)絡(luò)G上的一個(gè)流.

滿足下述條件的流f

稱為可行流：

①(限制條件)對每一邊vivj,有0≤fij≤Cij;②(平衡條件)對于中間點(diǎn)vk有∑fik

=∑fkj

,即中間點(diǎn)vk的輸入量=輸出量.8/16/202353南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍6、網(wǎng)絡(luò)流問題定義1設(shè)G=(V,E)為有向如果

f是可行流,則對收、發(fā)點(diǎn)vt、vs有∑fsi

=∑fjt=Wf,即從vs點(diǎn)發(fā)出的物質(zhì)總量=vt點(diǎn)輸入的量.Wf稱為網(wǎng)絡(luò)流

f的總流量.上述概念可以這樣來理解,如G是一個(gè)運(yùn)輸網(wǎng)絡(luò),則發(fā)點(diǎn)vs表示發(fā)送站,收點(diǎn)vt表示接收站,中間點(diǎn)vk表示中間轉(zhuǎn)運(yùn)站,可行流

fij表示某條運(yùn)輸線上通過的運(yùn)輸量,容量Cij表示某條運(yùn)輸線能承擔(dān)的最大運(yùn)輸量,Wf表示運(yùn)輸總量.可行流總是存在的.比如所有邊的流量

fij=0就是一個(gè)可行流(稱為零流).8/16/202354南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍如果f是可行流,則對收、發(fā)點(diǎn)vt、vs有所謂最大流問題就是在容量網(wǎng)絡(luò)中,尋找流量最大的可行流.實(shí)際問題中,一個(gè)網(wǎng)絡(luò)會(huì)出現(xiàn)下面兩種情況：⑴發(fā)點(diǎn)和收點(diǎn)都不止一個(gè).解決的方法是再虛設(shè)一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt,發(fā)點(diǎn)vs到所有原發(fā)點(diǎn)邊的容量都設(shè)為無窮大,所有原收點(diǎn)到收點(diǎn)vt邊的容量都設(shè)為無窮大.⑵網(wǎng)絡(luò)中除了邊有容量外,點(diǎn)也有容量.解決的方法是將所有有容量的點(diǎn)分成兩個(gè)點(diǎn),如點(diǎn)v有容量Cv,將點(diǎn)v分成兩個(gè)點(diǎn)v'和v",令C(v'v"

)=Cv.8/16/202355南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍所謂最大流問題就是在容量網(wǎng)絡(luò)中,尋找流量最大的可行流最小費(fèi)用流問題這里我們要進(jìn)一步探討不僅要使網(wǎng)上的流達(dá)到最大,或者達(dá)到要求的預(yù)定值,而且還要使運(yùn)輸流的費(fèi)用是最小的,這就是最小費(fèi)用流問題.最小費(fèi)用流問題的一般提法：已知網(wǎng)絡(luò)G=(V,E,C),每條邊vivj∈E除了已給容量Cij外,還給出了單位流量的費(fèi)用bij(≥0).所謂最小費(fèi)用流問題就是求一個(gè)總流量已知的可行流

f={

fij}使得總費(fèi)用最小.8/16/202356南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍最小費(fèi)用流問題這里我們要進(jìn)一步探討不僅要使網(wǎng)上的流特別地,當(dāng)要求

f為最大流時(shí),即為最小費(fèi)用最大流問題.設(shè)網(wǎng)絡(luò)G=(V,E,C),取初始可行流

f為零流,求解最小費(fèi)用流問題的迭代步驟：

①

構(gòu)造有向賦權(quán)圖Gf=(V,Ef,F),對于任意的vivj∈E,Ef,F的定義如下：

當(dāng)fij=0時(shí),vivj∈Ef,F(vivj)=bij;

當(dāng)fij=Cij時(shí),vjvi∈Ef,F(vjvi)=-bij;

當(dāng)0＜fij＜Cij時(shí),vivj∈Ef,F(vivj)=bij,vjvi∈Ef,F(vjvi)=-bij.然后轉(zhuǎn)向②.8/16/202357南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍?zhí)貏e地,當(dāng)要求f為最大流時(shí),即為最小費(fèi)用最大流②求出含有負(fù)權(quán)的有向賦權(quán)圖Gf=(V,Ef,F)中發(fā)點(diǎn)vs到收點(diǎn)vt的最短路

,若最短路

存在轉(zhuǎn)向③;否則f是所求的最小費(fèi)用最大流,停止.③增流.vivj與

相同,vivj與

相反.令

=min{

ij|vivj∈

},重新定義流f={

fij}為其它情況不變.如果Wf大于或等于預(yù)定的流量值,則適當(dāng)減少

值,使Wf等于預(yù)定的流量值,那么f是所求的最小費(fèi)用流,停止;否則轉(zhuǎn)向①.8/16/202358南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍②求出含有負(fù)權(quán)的有向賦權(quán)圖Gf=(V,Ef,下面介紹求解有向賦權(quán)圖G=(V,E,F)中含有負(fù)權(quán)的最短路的Ford算法.設(shè)邊的權(quán)vivj為wij,v1到vi的路長記為

(i).Ford算法的迭代步驟：①賦初值

(1)=0,

(i)=∞,i=2,3,…,n.②更新

(i),i=2,3,…,n.

(i)=min{

(i),min{

(j)+wji|j≠i}}.③若所有的

(i)都無變化,停止;否則轉(zhuǎn)向②.在算法的每一步,

(i)都是從v1到vi的最短路長度的上界.若不存在負(fù)長回路,則從v1到vi的最短路長度是

(i)的下界,經(jīng)過n

-1次迭代后

(i)將保持不變.若在第n次迭代后

(i)仍在變化時(shí),說明存在負(fù)長回路.

8/16/202359南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍下面介紹求解有向賦權(quán)圖G=(V,E,F)中7、關(guān)鍵路徑問題（拓?fù)渑判颍┮豁?xiàng)工程任務(wù),大到建造一座大壩,一座體育中心,小至組裝一臺機(jī)床,一架電視機(jī),都要包括許多工序.這些工序相互約束,只有在某些工序完成之后,一個(gè)工序才能開始.即它們之間存在完成的先后次序關(guān)系,一般認(rèn)為這些關(guān)系是預(yù)知的,而且也能夠預(yù)計(jì)完成每個(gè)工序所需要的時(shí)間.這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間才能夠完成整個(gè)工程項(xiàng)目,影響工程進(jìn)度的要害工序是哪幾個(gè)？8/16/202360南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍7、關(guān)鍵路徑問題（拓?fù)渑判颍┮豁?xiàng)工程任務(wù),大到建造一PT(Potentialtaskgraph)圖在PT(Potentialtaskgraph)圖中,用結(jié)點(diǎn)表示工序,如果工序

i完成之后工序

j才能啟動(dòng),則圖中有一條有向邊(i,j),其長度wi表示工序

i所需的時(shí)間.這種圖必定不存在有向回路,否則某些工序?qū)⒃谧陨硗瓿芍蟛拍荛_始,這顯然不符合實(shí)際情況.在PT圖中增加兩個(gè)虛擬結(jié)點(diǎn)v0和vn,使所有僅為始點(diǎn)的結(jié)點(diǎn)都直接與v0聯(lián)結(jié),v0為新增邊的始點(diǎn),這些新增邊的權(quán)都設(shè)為0;使所有僅為終點(diǎn)的結(jié)點(diǎn)都直接與vn聯(lián)結(jié),vn為新增邊的終點(diǎn).這樣得到的圖G仍然不存在有向回路.8/16/202361南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍PT(Potentialtaskgraph)圖在例一項(xiàng)工程由13道工序組成,所需時(shí)間(單位：天)及先行工序如下表所示(P172).工序序號ABCDEFGHI所需時(shí)間263243842先行工序—AABC,DDDDG,H工序序號JKLM所需時(shí)間3856先行工序GH,EJK試問這項(xiàng)工程至少需要多少天才能完成?那些工程不能延誤?那些工程可以延誤?最多可延誤多少天?8/16/202362南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍例一項(xiàng)工程由13道工序組成,所需時(shí)間(單位：天)先作出該工程的PT圖.由于除了工序A外，均有先行工序,因此不必虛設(shè)虛擬結(jié)點(diǎn)v0.AB22C6D3E2F2G2H2K4N3I8J8442L3M856

在PT圖中,容易看出各工序先后完成的順序及時(shí)間.虛擬結(jié)點(diǎn)8/16/202363南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍先作出該工程的PT圖.由于除了工序A外，均有先行工序AB22C6D3E2F2G2H2K4N3I8J8442L3M856這項(xiàng)工程至少需要多少天才能完成?就是要求A到N的最長路,此路徑稱為關(guān)鍵路徑.那些工程不能延誤?那些工程可以延誤?最多可延誤多少天?關(guān)鍵路徑上的那些工程不能延誤.8/16/202364南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍AB22C6D3E2F2G2H2K4N3I8J8442L3M關(guān)鍵路徑(最長路徑)算法

定理若有向圖G中不存在有向回路,則可以將G的結(jié)點(diǎn)重新編號為u1,u2,…,un,使得對任意的邊uiuj∈E(G),都有i＜

j.各工序最早啟動(dòng)時(shí)間算法步驟：

①根據(jù)定理對結(jié)點(diǎn)重新編號為u1,u2,…,un.②賦初值

(u1)=0.③依次更新

(uj),j=2,3,…,n.

(uj)=max{

(ui)+

(ui,uj)|uiuj∈E(G)}.④結(jié)束.其中

(uj)表示工序

uj最早啟動(dòng)時(shí)間,而

(un)即

(vn)是整個(gè)工程完工所需的最短時(shí)間.8/16/202365南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍關(guān)鍵路徑(最長路徑)算法定理若有向圖G中不存在有AB22C6D3E2F2G2H2K4N3I8J8442L3M856此例不必重新編號，只要按字母順序即可.

(A)=0,

(B)=

(C)=2,

(D)=8,

(E)=max{2+3,8+2}=10,

(F)=

(G)=

(H)=

(D)+2=10,

(I)=max{

(G)+8,

(H)+4}=18,

(J)=

(G)+8=18,

(K)=max{

(E)+4,

(H)+4}=14,

(L)=

(J)+3=21,

(M)=

(K)+8=22,

(N)=max{

(F)+3,

(I)+2,

(L)+5,

(M)+6}=28.關(guān)鍵路徑?8/16/202366南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍AB22C6D3E2F2G2H2K4N3I8J8442L3M通過以上計(jì)算表明：這項(xiàng)工程至少需要28天才能完成.關(guān)鍵路徑(最長路徑):A→B→D→E→K→M→NA→B→D→H→K→M→N工序A,B,D,E,H,K,M不能延誤,否則將影響工程的完成.但是對于不在關(guān)鍵路徑上的工序,是否允許延誤？如果允許,最多能夠延誤多長時(shí)間呢？各工序允許延誤時(shí)間t(uj)等于各工序最晚啟動(dòng)時(shí)間

(uj)減去各工序最早啟動(dòng)時(shí)間

(uj).即

t(uj)=

(uj)-

(uj).8/16/202367南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍通過以上計(jì)算表明：這項(xiàng)工程至少需要28天才能完成.工最晚啟動(dòng)時(shí)間算法步驟(已知結(jié)點(diǎn)重新編號)：

①賦初值

(un)=

(un).②更新

(uj),j=n-1,n-2,…,1.

(uj)=min{

(ui)-

(ui,uj)|uiuj∈E(G)}.③結(jié)束.順便提一句,根據(jù)工序uj允許延誤時(shí)間t(uj)是否為0,可判斷該工序是否在關(guān)鍵路徑上.8/16/202368南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍最晚啟動(dòng)時(shí)間算法步驟(已知結(jié)點(diǎn)重新編號)：①賦初值A(chǔ)B22C6D3E2F2G2H2K4N3I8J8442L3M856

(N)=28,

(M)=28-6=22,

(L)=28-5=23,

(K)=

(M)-8=14,

(J)=

(L)-3=20,

(I)=28-2=26,

(H)=min{

(K)-4,

(I)-4}=10,

(G)=min{

(J)-8,

(I)-8}=12,

(F)=28-3=25,

(E)=

(K)-4=10,

(D)=min{

(E)-2,

(F)-2,

(G)-2,

(H)-2}=8,

(C)=

(E)-3=7,

(B)=

(D)-6=2,

(A)=0.8/16/202369南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍AB22C6D3E2F2G2H2K4N3I8J8442L3M各工序允許延誤時(shí)間如下：t(A)=t(B)=t(D)=t(E)=t(H)=t(K)=t(M)=0,t(C)=5,t(F)=15,t(G)=2,t(I)=8,t(J)=2,t(L)=2.8/16/202370南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍各工序允許延誤時(shí)間如下：t(A)=t(B)=t(D)=t(EPERT圖

在PERT(Programmeevaluationandreviewtechnique)圖中,采用有向邊表示工序,其權(quán)值表示該工序所需時(shí)間.如果工序ei完成后ej才能開始,則令vk是ei的終點(diǎn),ej的始點(diǎn).根據(jù)這種約定,前例的PERT圖如下：

ABCEFDDGGHHIJKLM

對于PERT圖,一些算法與PT圖類似.8/16/202371南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍PERT圖在PERT(Programmeeval

PT圖要比PERT圖好一些.PT圖的結(jié)點(diǎn)數(shù)基本上是固定的,這是最重要的一點(diǎn),容易編程計(jì)算.另外PT圖比PERT圖更加靈活,它能適應(yīng)一些額外的約束.例如下圖中

(i

)/2vivj⑴

(i

)+tvivj⑵bjv0vj⑶⑴

表示工序vi完成一半之后vj就可以開始.⑵

表示工序vi完成后經(jīng)過t時(shí)刻vj才開始.⑶表示在時(shí)間bj

之后工序vj才能開始,其中v0表示虛擬結(jié)點(diǎn).8/16/202372南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍PT圖要比PERT圖好一些.PT圖的結(jié)點(diǎn)數(shù)基本上是8、系統(tǒng)監(jiān)控模型

定義1設(shè)圖G=(V,E),K

V如果圖G的每條邊都至少有一個(gè)頂點(diǎn)在K中,則稱K是G的一個(gè)點(diǎn)覆蓋.若G的一個(gè)點(diǎn)覆蓋中任意去掉一個(gè)點(diǎn)后不再是點(diǎn)覆蓋,則稱此點(diǎn)覆蓋是G的一個(gè)極小點(diǎn)覆蓋.頂點(diǎn)數(shù)最少的點(diǎn)覆蓋,稱為G的最小點(diǎn)覆蓋.例如,右圖中,{v0,v2,v3,v5,v6}等都是極小點(diǎn)覆蓋.{v0,v1,v3,v5},{v0,v2,v4,v6}都是最小點(diǎn)覆蓋.8/16/202373南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍8、系統(tǒng)監(jiān)控模型定義1設(shè)圖G=(V,E),系統(tǒng)監(jiān)控問題之一

假設(shè)v1,v2,…,v7是7個(gè)哨所,監(jiān)視著11條路段(如下圖所示),為節(jié)省人力,問至少需要在幾個(gè)哨所派人站崗,就可以監(jiān)視全部路段?這就是要求最小點(diǎn)覆蓋問題.v2v1v3v7v6v5v4{v1,v3,v5,v6}和{v1,v3,v5,v7}都是最小點(diǎn)覆蓋,所以至少需要在4個(gè)哨所派人站崗來監(jiān)視全部路段.到目前為止,還沒有找到求最小點(diǎn)覆蓋的有效算法,即多項(xiàng)式時(shí)間算法(算法步數(shù)不超過nc,n為G的頂點(diǎn)數(shù),c為常數(shù)).有一些啟發(fā)式近似算法.8/16/202374南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍系統(tǒng)監(jiān)控問題之一假設(shè)v1,v2,…,v7是最大獨(dú)立點(diǎn)集

定義2設(shè)圖G=(V,E),I

V如果I中任意兩個(gè)頂點(diǎn)在G中都不相鄰,則稱I是G的一個(gè)獨(dú)立點(diǎn)集.若G的一個(gè)獨(dú)立點(diǎn)集中,任意添加一個(gè)點(diǎn)后不再是獨(dú)立點(diǎn)集,則稱此獨(dú)立點(diǎn)集是G的一個(gè)極大獨(dú)立點(diǎn)集.頂點(diǎn)數(shù)最多的獨(dú)立點(diǎn)集,稱為G的最大獨(dú)立點(diǎn)集.例如,右圖中,{v1,v4}等都是極大獨(dú)立點(diǎn)集.{v1,v3,v5},{v2,v2,v6}是最大獨(dú)立點(diǎn)集.8/16/202375南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍最大獨(dú)立點(diǎn)集定義2設(shè)圖G=(V,E),I最小控制集

定義3設(shè)圖G=(V,E),D

V如果

v∈V,要么v∈D,要么v與D的某個(gè)點(diǎn)相鄰,則稱D是G的一個(gè)控制集.若G的一個(gè)控制集中任意去掉一個(gè)點(diǎn)后不再是控制集,則稱此控制集是G的一個(gè)極小控制集.頂點(diǎn)數(shù)最少的控制集,稱為G的最小控制集.例如,右圖中,{v1,v3,v5}是極小控制集,{v0}是最小控制集.8/16/202376南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍最小控制集定義3設(shè)圖G=(V,E),D系統(tǒng)監(jiān)控問題之二假設(shè)下圖代表一指揮系統(tǒng),頂點(diǎn)v1,v2,…,v7表示被指揮的單位,邊表示可以直接下達(dá)命令的通信線路.欲在某些單位建立指揮站,以便可以通過指揮站直接給各單位下達(dá)命令,問至少需要建立幾個(gè)指揮站?這就是要求最小控制集問題.v2v1v3v7v6v5v4{v1,v3},{v3,v5}等都是最小控制集,所以至少需要在2個(gè)單位建立指揮站.到目前為止,還沒有找到求最小控制集的有效算法..8/16/202377南京信息工程大學(xué)數(shù)理學(xué)院費(fèi)文龍系統(tǒng)監(jiān)控問題之二假設(shè)下圖代表一指揮系統(tǒng),頂點(diǎn)v1,最小點(diǎn)覆蓋、最大獨(dú)立點(diǎn)集和最小控制集的關(guān)系

定理1設(shè)無向圖G=(V,E)中無孤立點(diǎn)(