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

數(shù)模培訓(xùn)圖論模型2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍1第一頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍2圖論模型圖論基本概念最短路徑算法最小生成樹算法遍歷性問題二分圖與匹配網(wǎng)絡(luò)流問題關(guān)鍵路徑問題系統(tǒng)監(jiān)控模型著色模型第二頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍31、圖論的基本概念A(yù)BCD哥尼斯堡七橋示意圖問題1(哥尼斯堡七橋問題):

能否從任一陸地出發(fā)通過每座橋恰好一次而回到出發(fā)點？第三頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍4ABDC七橋問題模擬圖歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地.第四頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍5問題2(哈密頓環(huán)球旅行問題):

十二面體的20個頂點代表世界上20個城市，能否從某個城市出發(fā)在十二面體上依次經(jīng)過每個城市恰好一次最后回到出發(fā)點？哈密頓圈（環(huán)球旅行游戲）第五頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍6問題3(四色問題):

對任何一張地圖進行著色，兩個共同邊界的國家染不同的顏色，則只需要四種顏色就夠了.問題4(關(guān)鍵路徑問題):

一項工程任務(wù),大到建造一座大壩,一座體育中心,小至組裝一臺機床,一架電視機,都要包括許多工序.這些工序相互約束,只有在某些工序完成之后,一個工序才能開始.即它們之間存在完成的先后次序關(guān)系,一般認為這些關(guān)系是預(yù)知的,而且也能夠預(yù)計完成每個工序所需要的時間.

這時工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時間才能夠完成整個工程項目,影響工程進度的要害工序是哪幾個？第六頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍7圖的定義圖論中的“圖”并不是通常意義下的幾何圖形或物體的形狀圖,而是以一種抽象的形式來表達一些確定的事物之間的聯(lián)系的一個數(shù)學(xué)系統(tǒng).

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

①V稱為G的頂點集,V≠,其元素稱為頂點或結(jié)點,簡稱點;②

E稱為G的邊集,其元素稱為邊,它聯(lián)結(jié)V中的兩個點,如果這兩個點是無序的,則稱該邊為無向邊,否則,稱為有向邊.

如果V={v1,v2,…,vn}是有限非空點集,則稱G為有限圖或n階圖.第七頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍8如果E的每一條邊都是無向邊,則稱G為無向圖(如圖1);

如果E的每一條邊都是有向邊,則稱G為有向圖(如圖2);

否則,稱G為混合圖.圖1圖2并且常記V={v1,v2,…,vn},|V|

=n

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

=m.稱點vi,vj為邊vivj的端點.在有向圖中,稱點vi,vj分別為邊vivj的始點和終點.該圖稱為(n,m)圖第八頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍9

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

稱其為圖解.

凡是有向邊,

在圖解上都用箭頭標(biāo)明其方向.例如,設(shè)V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4},則G=(V,E)是一個有4個頂點和6條邊的圖,G的圖解如下圖所示.第九頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍10一個圖會有許多外形不同的圖解,下面兩個圖表示同一個圖G=(V,E)的圖解.其中V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4}.

這兩個圖互為同構(gòu)圖,今后將不計較這種外形上的差別,而用一個容易理解的、確定的圖解去表示一個圖.第十頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍11有邊聯(lián)結(jié)的兩個點稱為相鄰的點,有一個公共端點的邊稱為相鄰邊.邊和它的端點稱為互相關(guān)聯(lián).常用d(v)表示圖G中與頂點v關(guān)聯(lián)的邊的數(shù)目,d(v)稱為頂點v的度數(shù).對于有向圖,還有出度和入度之分.

用N(v)表示圖G中所有與頂點v相鄰的頂點的集合.d(v1)=d(v3)=d(v4)=4,d(v2)=2.握手定理：第十一頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍12我們今后只討論有限簡單圖：

(1)頂點個數(shù)是有限的;(2)任意一條邊有且只有兩個不同的點與它相互關(guān)聯(lián);(3)若是無向圖,則任意兩個頂點最多只有一條邊與之相聯(lián)結(jié);(4)若是有向圖,則任意兩個頂點最多只有兩條邊與之相聯(lián)結(jié).當(dāng)兩個頂點有兩條邊與之相聯(lián)結(jié)時，這兩條邊的方向相反.

如果某個有限圖不滿足(2)(3)(4),可在某條邊上增設(shè)頂點使之滿足.第十二頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍13

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

定義3任意兩點均有通路的圖稱為連通圖.

定義4連通而無圈的圖稱為樹,常用T表示樹.第十三頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍14

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

解：用四維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個狀態(tài)向量作為頂點,將可能互相轉(zhuǎn)移的狀態(tài)用線段連接起來構(gòu)成一個圖.

根據(jù)此圖便可找到渡河方法.第十四頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍15(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個頂點分別記為A1,A2,…,A10,則渡河問題化為在該圖中求一條從A1到A10的路.

從圖中易得到兩條路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.第十五頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍16圖的矩陣表示⑴

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

其中

第十六頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍17無向圖G的鄰接矩陣A是一個對稱矩陣.

⑵

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

其中

有限簡單圖基本上可用權(quán)矩陣來表示.第十七頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍18無向圖G的權(quán)矩陣A是一個對稱矩陣.

第十八頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍19⑶

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

其中

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

-

1.第十九頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍20一個有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)矩陣每列的元素中有且僅有兩個1.第二十頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍212、最短路徑算法

定義1

設(shè)P(u,v)是賦權(quán)圖G=(V,E,F)中從點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的最短路.第二十一頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍22重要性質(zhì)：

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

即：最短路是一條路，且最短路的任一段也是最短路.

求非負賦權(quán)圖G中某一點到其它各點最短路，一般用Dijkstra標(biāo)號算法；求非負賦權(quán)圖上任意兩點間的最短路，一般用Floyd算法.

這兩種算法均適用于有向非負賦權(quán)圖.

下面分別介紹兩種算法的基本過程.第二十二頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍23Dijkstra算法指標(biāo)（a為起點）

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

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

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

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

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

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

l'(t)=min{l(t),l(x)+w(x,t)}第二十三頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍24Dijkstra算法（求a點到其他點的最短路徑）1、初始化，P={a}，T=V-{a}，對每個結(jié)點t計算指標(biāo)l(t)=w(a,t)2、設(shè)x為T中關(guān)于P有最小指標(biāo)的點,

即: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)},

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

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

第二十四頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍25改進Dijkstra算法（求a點到其他點的最短路徑）1、初始化，P={a}，T=V-{a}，對每個結(jié)點t計算指標(biāo)l(t)=w(a,t),pro(t)=a;2、設(shè)x為T中關(guān)于P有最小指標(biāo)的點,

即: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)},

計算T’中每一個結(jié)點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)矩陣）

第二十五頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍26

ABCDEFGHA02∞∞∞∞6∞B207∞∞13∞C∞7043∞∞∞D(zhuǎn)∞∞405∞∞2E∞∞3502∞2F∞1∞∞201∞G63∞∞∞104H∞∞∞22∞40例求下圖中A點到其他點的最短路.第二十六頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍27Floyd算法（求任意兩點的最短路徑）設(shè)A=(aij)n×n為賦權(quán)圖G=(V,E,F)的權(quán)矩陣,dij表示從vi到vj點的距離,rij表示從vi到vj點的最短路中前一個點的編號.

①賦初值.對所有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得到.第二十七頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍28

0123456700281∞∞∞∞1206∞1∞∞∞28607512∞31∞70∞∞9∞4∞15∞03∞85∞∞1∞30466∞∞29∞4037∞∞∞∞8630例求下圖中任意兩點間的最短路.第二十八頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍29以下僅從圖上進行直觀操作.

根據(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的連線.得到第二十九頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍30從上圖中容易得到任意兩點間的最短路.例如,v1到v6的路有三條：

v1v0v3v2v6(長度為12),

v1v4v5v2v6(長度為7),

v1v4v7v6(長度為12).第三十頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍31例設(shè)備更新問題某企業(yè)每年年初,都要作出決定,如果繼續(xù)使用舊設(shè)備,要付維修費；若購買一臺新設(shè)備,要付購買費.試制定一個5年更新計劃,使總支出最少.

已知設(shè)備在每年年初的購買費分別為11,11,12,12,13.使用不同時間設(shè)備所需的維修費分別為5,6,8,11,18.

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

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

E={vivj|1≤i＜j≤6}.第三十一頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍32這樣上述設(shè)備更新問題就變?yōu)椋涸谟邢蛸x權(quán)圖G=(V,E,F)(圖解如下)中求v1到v6的最短路問題.第三十二頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍33由實際問題可知,設(shè)備使用三年后應(yīng)當(dāng)更新,因此刪除該圖中v1到v5,v1到v6,v2到v6的連線；又設(shè)備使用一年后就更新則不劃算,因此再刪除該圖中v1v2,v2v3,v3v4,v4v5,v5v6五條連線后得到從上圖中容易得到v1到v6只有兩條路：v1v3v6和v1v4v6.

而這兩條路都是v1到v6的最短路.第三十三頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍343、最小生成樹

由樹的定義不難知道,任意一個連通的(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的所有生成樹中權(quán)數(shù)最小的生成樹稱為圖G的最小生成樹.

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

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

模型建立與求解用Floyd算法求出任意兩個居民點vi,vj之間的最短距離,并用dij表示.⑴設(shè)置一個銀行,銀行設(shè)在vi點的最大服務(wù)距離為第三十六頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍37求k,使即若設(shè)置一個銀行,則銀行設(shè)在

vk點,可使最大服務(wù)距離最小.⑵設(shè)置兩個銀行,假設(shè)銀行設(shè)在vs,vt點使最大服務(wù)距離最小.記則s,t滿足：進一步,若設(shè)置多個銀行呢？第三十七頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍384、遍歷性問題一、歐拉圖G=(V,E)為一連通無向圖經(jīng)過G中每條邊至少一次的回路稱為巡回；經(jīng)過G中每條邊正好一次的巡回稱為歐拉巡回；存在歐拉巡回的圖稱為歐拉圖。二、中國郵遞員問題（CPP－chinesepostmanproblem）

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

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

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

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

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

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

遺傳算法等等第四十一頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍425、二分圖與匹配

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

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

二部圖可認為是有限簡單無向圖.

如果X中的每個點都與Y中的每個點鄰接,則稱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).第四十二頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍43

定義2設(shè)G=(X,Y,E)為二部圖,且ME.若M中任意兩條邊在G中均不鄰接,則稱M是二部圖G的一個匹配.定義3

設(shè)M是二部圖G的一個匹配,如果G的每一個點都是M中邊的頂點,則稱M是二部圖G的完美匹配；如果G中沒有另外的匹配M0,使|M0|＞|M|,則稱M是二部圖G的最大匹配.

在二部賦權(quán)圖G=(X,Y,E,F)中,權(quán)數(shù)最大的最大匹配M稱為二部賦權(quán)圖G的最佳匹配.

顯然,每個完美匹配都是最大匹配,反之不一定成立.第四十三頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍44工作安排問題之一給n個工作人員x1,x2,…,xn安排n項工作y1,y2,…,yn.n個工作人員中每個人能勝任一項或幾項工作,但并不是所有工作人員都能從事任何一項工作.比如x1能做y1,y2工作,x2能做y2,y3,y4工作等.

這樣便提出一個問題,對所有的工作人員能不能都分配一件他所能勝任的工作？

我們構(gòu)造一個二部圖G=(X,Y,E),這里X={x1,x2,…,xn},Y={y1,y2,…,yn},并且當(dāng)且僅當(dāng)工作人員xi勝任工作yj時,xi與yj才相鄰.

于是,問題轉(zhuǎn)化為求二部圖的一個完美匹配.因為

|X|=|Y|,所以完美匹配即為最大匹配.第四十四頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍45求二部圖G=(X,Y,E)的最大匹配算法(匈牙利算法,交替鏈算法)迭代步驟:從G的任意匹配M開始.①將X中M的所有非飽和點都給以標(biāo)號0和標(biāo)記*,轉(zhuǎn)向②.

M的非飽和點即非M的某條邊的頂點.②若X中所有有標(biāo)號的點都已去掉了標(biāo)記*,則M是G的最大匹配.否則任取X中一個既有標(biāo)號又有標(biāo)記*的點xi,去掉xi的標(biāo)記*,轉(zhuǎn)向③.③找出在G中所有與xi鄰接的點yj,若所有這樣的yj都已有標(biāo)號,則轉(zhuǎn)向②,否則轉(zhuǎn)向④.第四十五頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍46④對與xi鄰接且尚未給標(biāo)號的yj都給定標(biāo)號i.若所有的

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

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

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

yk,…,最后由

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

},重新記M為M⊕P,轉(zhuǎn)向①.

不必理會M-增廣路的定義.

M⊕P=M∪P

\

M∩P,是對稱差.

⑤

將yj在M中與之鄰接的點xk,給以標(biāo)號j和標(biāo)記*,轉(zhuǎn)向②.第四十六頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍47例求下圖所示二部圖G的最大匹配.解①取初始匹配M0={x2

y2,x3

y3,x5

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

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

因為y2,y3都是M0的兩個飽和點,所以將它們在M0中鄰接的兩個點x2,x3都給以相應(yīng)的標(biāo)號和標(biāo)記*(如下圖所示).第四十七頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍48④

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

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

y3,x5

y5},則M1是比M多一邊的匹配(如下圖所示).第四十八頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍49⑥

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

去掉x1的標(biāo)記*,因為與x1鄰接的兩個點y2,y3都有標(biāo)號4,所以去掉x3的標(biāo)記*.而與x3鄰接的兩個點y2,y3也都有標(biāo)號4,此時X中所有有標(biāo)號的點都已去掉了標(biāo)記*(如下圖所示),因此M1是G的最大匹配.

G不存在飽和X的每個點的匹配,當(dāng)然也不存在完美匹配.第四十九頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍50工作安排問題之二給n個工作人員x1,x2,…,xn安排n項工作y1,y2,…,yn.如果每個工作人員工作效率不同,要求工作分配的同時考慮總效率最高.我們構(gòu)造一個二部賦權(quán)圖G=(X,Y,E,F),這里X={x1,x2,…,xn},Y={y1,y2,…,yn},F(xi

yj)為工作人員xi勝任工作yj時的工作效率.

則問題轉(zhuǎn)化為：求二部賦權(quán)圖G的最佳匹配.

在求G

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

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

轉(zhuǎn)化為完備二部賦權(quán)圖,而且不會影響結(jié)果.第五十頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍51

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

若L：X∪Y→R+滿足：x∈X,y∈Y,L(x)+L(y)≥F(xy),則稱L為G的一個可行點標(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是其一個初始可行點標(biāo)記,通常取

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

L(y)=0,y∈Y.第五十一頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍52M是GL的一個匹配.①若X的每個點都是飽和的,則M是最佳匹配.否則取M的非飽和點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)記,計算aL=min{L(x)+L(y)-

F(xy)|x∈S,y∈Y\T}.

由此得新的可行點標(biāo)記

令L=H,GL

=GH

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

(S)\T,若y是M的飽和點,轉(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)向①.第五十二頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍536、網(wǎng)絡(luò)流問題

定義1設(shè)G=(V,E)為有向圖,在V中指定一點稱為發(fā)點(記為vs),和另一點稱為收點(記為vt),其余點叫做中間點.對每一條邊vivj∈E,對應(yīng)一個非負實數(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上的一個流.

滿足下述條件的流f

稱為可行流：

①

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

=∑fkj

,即中間點vk的輸入量=輸出量.第五十三頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍54如果

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

=∑fjt=Wf,即從vs點發(fā)出的物質(zhì)總量

=vt點輸入的量.Wf稱為網(wǎng)絡(luò)流

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

fij表示某條運輸線上通過的運輸量,容量Cij表示某條運輸線能承擔(dān)的最大運輸量,Wf表示運輸總量.

可行流總是存在的.比如所有邊的流量

fij=0就是一個可行流(稱為零流).第五十四頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍55所謂最大流問題就是在容量網(wǎng)絡(luò)中,尋找流量最大的可行流.實際問題中,一個網(wǎng)絡(luò)會出現(xiàn)下面兩種情況：⑴發(fā)點和收點都不止一個.

解決的方法是再虛設(shè)一個發(fā)點vs和一個收點vt,發(fā)點vs到所有原發(fā)點邊的容量都設(shè)為無窮大,所有原收點到收點vt邊的容量都設(shè)為無窮大.⑵網(wǎng)絡(luò)中除了邊有容量外,點也有容量.

解決的方法是將所有有容量的點分成兩個點,如點v有容量Cv,將點v分成兩個點v'和v",令C(v'v"

)=Cv.第五十五頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍56最小費用流問題這里我們要進一步探討不僅要使網(wǎng)上的流達到最大,或者達到要求的預(yù)定值,而且還要使運輸流的費用是最小的,這就是最小費用流問題.最小費用流問題的一般提法：已知網(wǎng)絡(luò)G=(V,E,C),每條邊vivj∈E除了已給容量Cij外,還給出了單位流量的費用bij(≥0).

所謂最小費用流問題就是求一個總流量已知的可行流

f={

fij}使得總費用最小.第五十六頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍57特別地,當(dāng)要求

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

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

①

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

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

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

當(dāng)0＜fij＜Cij時,vivj∈Ef,F(vivj)=bij,vjvi∈Ef,F(vjvi)=-bij.

然后轉(zhuǎn)向②.第五十七頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍58②求出含有負權(quán)的有向賦權(quán)圖Gf=(V,Ef,F)中發(fā)點vs到收點vt的最短路

,若最短路存在轉(zhuǎn)向③;

否則f是所求的最小費用最大流,停止.③增流.vivj與相同,vivj與相反.令

=min{ij|vivj∈

},重新定義流f={

fij}為其它情況不變.如果Wf大于或等于預(yù)定的流量值,則適當(dāng)減少值,使Wf等于預(yù)定的流量值,那么f是所求的最小費用流,停止;

否則轉(zhuǎn)向①.第五十八頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍59下面介紹求解有向賦權(quán)圖G=(V,E,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的最短路長度的上界.若不存在負長回路,則從v1到vi的最短路長度是

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

-1次迭代后

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

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

第五十九頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍607、關(guān)鍵路徑問題（拓撲排序）一項工程任務(wù),大到建造一座大壩,一座體育中心,小至組裝一臺機床,一架電視機,都要包括許多工序.這些工序相互約束,只有在某些工序完成之后,一個工序才能開始.即它們之間存在完成的先后次序關(guān)系,一般認為這些關(guān)系是預(yù)知的,而且也能夠預(yù)計完成每個工序所需要的時間.

這時工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時間才能夠完成整個工程項目,影響工程進度的要害工序是哪幾個？第六十頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍61PT(Potentialtaskgraph)圖在PT(Potentialtaskgraph)圖中,用結(jié)點表示工序,如果工序

i完成之后工序

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

i所需的時間.這種圖必定不存在有向回路,否則某些工序?qū)⒃谧陨硗瓿芍蟛拍荛_始,這顯然不符合實際情況.

在PT圖中增加兩個虛擬結(jié)點v0和vn,使所有僅為始點的結(jié)點都直接與v0聯(lián)結(jié),v0為新增邊的始點,這些新增邊的權(quán)都設(shè)為0;

使所有僅為終點的結(jié)點都直接與vn聯(lián)結(jié),vn為新增邊的終點.這樣得到的圖G仍然不存在有向回路.第六十一頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍62例一項工程由13道工序組成,所需時間(單位：天)及先行工序如下表所示(P172).工序序號ABCDEFGHI所需時間263243842先行工序—AABC,DDDDG,H工序序號JKLM所需時間3856先行工序GH,EJK試問這項工程至少需要多少天才能完成?那些工程不能延誤?那些工程可以延誤?最多可延誤多少天?第六十二頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍63先作出該工程的PT圖.由于除了工序A外，均有先行工序,因此不必虛設(shè)虛擬結(jié)點v0.AB22C6D3E2F2G2H2K4N3I8J8442L3M856

在PT圖中,容易看出各工序先后完成的順序及時間.虛擬結(jié)點第六十三頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍64AB22C6D3E2F2G2H2K4N3I8J8442L3M856這項工程至少需要多少天才能完成?就是要求A到N的最長路,此路徑稱為關(guān)鍵路徑.那些工程不能延誤?那些工程可以延誤?最多可延誤多少天?

關(guān)鍵路徑上的那些工程不能延誤.第六十四頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍65關(guān)鍵路徑(最長路徑)算法

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

j.各工序最早啟動時間算法步驟：

①根據(jù)定理對結(jié)點重新編號為u1,u2,…,un.②賦初值(u1)=0.③依次更新(uj),j=2,3,…,n.(uj)=max{(ui)+

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

uj最早啟動時間,而(un)即(vn)是整個工程完工所需的最短時間.第六十五頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍66AB22C6D3E2F2G2H2K4N3I8J8442L3M856此例不必重新編號，只要按字母順序即可.(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)鍵路徑?第六十六頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍67通過以上計算表明：這項工程至少需要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)鍵路徑上的工序,是否允許延誤？如果允許,最多能夠延誤多長時間呢？各工序允許延誤時間t(uj)等于各工序最晚啟動時間(uj)減去各工序最早啟動時間(uj).即

t(uj)=(uj)-(uj).第六十七頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍68最晚啟動時間算法步驟(已知結(jié)點重新編號)：

①賦初值(un)=(un).②更新(uj),j=n-1,n-2,…,1.(uj)=min{(ui)-

(ui,uj)|uiuj∈E(G)}.③結(jié)束.順便提一句,根據(jù)工序uj允許延誤時間t(uj)是否為0,可判斷該工序是否在關(guān)鍵路徑上.第六十八頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍69AB22C6D3E2F2G2H2K4N3I8J8442L3M856(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.第六十九頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍70各工序允許延誤時間如下：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.第七十頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍71PERT圖

在PERT(Programmeevaluationandreviewtechnique)圖中,采用有向邊表示工序,其權(quán)值表示該工序所需時間.如果工序ei完成后ej才能開始,則令vk是ei的終點,ej的始點.

根據(jù)這種約定,前例的PERT圖如下：

ABCEFDDGGHHIJKLM

對于PERT圖,一些算法與PT圖類似.第七十一頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍72

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

)/2vivj⑴(i

)+tvivj⑵bjv0vj⑶⑴

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

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

之后工序vj才能開始,其中v0表示虛擬結(jié)點.第七十二頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍738、系統(tǒng)監(jiān)控模型

定義1設(shè)圖G=(V,E),KV如果圖G的每條邊都至少有一個頂點在K中,則稱K是G的一個點覆蓋.

若G的一個點覆蓋中任意去掉一個點后不再是點覆蓋,則稱此點覆蓋是G的一個極小點覆蓋.

頂點數(shù)最少的點覆蓋,稱為G的最小點覆蓋.例如,右圖中,{v0,v2,v3,v5,v6}等都是極小點覆蓋.{v0,v1,v3,v5},{v0,v2,v4,v6}都是最小點覆蓋.第七十三頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍74系統(tǒng)監(jiān)控問題之一

假設(shè)v1,v2,…,v7是7個哨所,監(jiān)視著11條路段(如下圖所示),為節(jié)省人力,問至少需要在幾個哨所派人站崗,就可以監(jiān)視全部路段?

這就是要求最小點覆蓋問題.v2v1v3v7v6v5v4{v1,v3,v5,v6}和{v1,v3,v5,v7}都是最小點覆蓋,所以至少需要在4個哨所派人站崗來監(jiān)視全部路段.到目前為止,還沒有找到求最小點覆蓋的有效算法,即多項式時間算法(算法步數(shù)不超過nc,n為G的頂點數(shù),c為常數(shù)).有一些啟發(fā)式近似算法.第七十四頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍75最大獨立點集

定義2設(shè)圖G=(V,E),IV如果I中任意兩個頂點在G中都不相鄰,則稱I是G的一個獨立點集.

若G的一個獨立點集中,任意添加一個點后不再是獨立點集,則稱此獨立點集是G的一個極大獨立點集.

頂點數(shù)最多的獨立點集,稱為G的最大獨立點集.例如,右圖中,

{v1,v4}等都是極大獨立點集.{v1,v3,v5},{v2,v2,v6}

是最大獨立點集.第七十五頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍76最小控制集

定義3設(shè)圖G=(V,E),DV如果v∈V,要么v∈D,要么v與D的某個點相鄰,則稱D是G的一個控制集.

若G的一個控制集中任意去掉一個點后不再是控制集,則稱此控制集是G的一個極小控制集.

頂點數(shù)最少的控制集,稱為G的最小控制集.例如,右圖中,{v1,v3,v5}是極小控制集,{v0}是最小控制集.第七十六頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍77系統(tǒng)監(jiān)控問題之二假設(shè)下圖代表一指揮系統(tǒng),頂點v1,v2,…,v7表示被指揮的單位,邊表示可以直接下達命令的通信線路.欲在某些單位建立指揮站,以便可以通過指揮站直接給各單位下達命令,問至少需要建立幾個指揮站?

這就是要求最小控制集問題.v2v1v3v7v6v5v4

{v1,v3},{v3,v5}等都是最小控制集,所以至少需要在2個單位建立指揮站.到目前為止,還沒有找到求最小控制集的有效算法..第七十七頁，共八十五頁，編輯于2023年，星期三2023/6/10南京信息工程大學(xué)數(shù)理學(xué)院費文龍78最小點覆蓋、最大獨立點集和最小控制集的關(guān)系

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