數(shù)學(xué)建模圖論模型

1、圖論模型,2,圖論模型,圖論基本概念 最短路徑算法 最小生成樹算法 遍歷性問題 二分圖與匹配,網(wǎng)絡(luò)流問題 關(guān)鍵路徑問題 系統(tǒng)監(jiān)控模型 著色模型,3,1、圖論的基本概念,問題1(哥尼斯堡七橋問題): 能否從任一陸地出發(fā)通過每座橋恰好一次而回到出發(fā)點(diǎn)？,4,歐拉指出： 如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地.,5,問題2(哈密頓環(huán)球旅行問題): 十二面體的20個頂點(diǎn)代表世界上20個城市，能否從某個城市出發(fā)在十二面體上依次經(jīng)過每個城市恰好一次最后回到出發(fā)點(diǎn)？,歐拉問題是“邊遍歷”，哈密爾頓問題是“點(diǎn)遍歷”,6,問題3(四色問題): 對任何一張地圖進(jìn)行著

2、色，兩個共同邊界的國家染不同的顏色，則只需要四種顏色就夠了.,問題4(關(guān)鍵路徑問題): 一項(xiàng)工程任務(wù),大到建造一座大壩,一座體育中心,小至組裝一臺機(jī)床,一架電視機(jī), 都要包括許多工序.這些工序相互約束,只有在某些工序完成之后, 一個工序才能開始. 即它們之間存在完成的先后次序關(guān)系,一般認(rèn)為這些關(guān)系是預(yù)知的, 而且也能夠預(yù)計(jì)完成每個工序所需要的時間. 這時工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時間才能夠完成整個工程項(xiàng)目, 影響工程進(jìn)度的要害工序是哪幾個？,圖的定義,圖論中的“圖”并不是通常意義下的幾何圖形或物體的形狀圖, 而是以一種抽象的形式來表達(dá)一些確定的事物之間的聯(lián)系的一個數(shù)學(xué)系統(tǒng).,定義1

3、一個有序二元組(v, e ) 稱為一個圖, 記為g = (v, e ), 其中, v稱為g的頂點(diǎn)集, v, 其元素稱為頂點(diǎn)或結(jié)點(diǎn), 簡稱點(diǎn); e稱為g的邊集, 其元素稱為邊, 它聯(lián)結(jié)v 中的兩個點(diǎn), 如果這兩個點(diǎn)是無序的, 則稱該邊為無向邊, 否則, 稱為有向邊. 如果v = v1, v2, , vn是有限非空點(diǎn)集, 則稱g為有限圖或n階圖.,8,如果e的每一條邊都是無向邊, 則稱g為無向圖(如圖1); 如果e的每一條邊都是有向邊, 則稱g為有向圖(如圖2); 否則, 稱g為混合圖.,圖1 圖2,并且常記:,v = v1, v2, , vn, |v | = n ; e = e1, e2, ,

4、em(ek=vivj ) , |e | = m.,稱點(diǎn)vi , vj為邊vivj的端點(diǎn). 在有向圖中, 稱點(diǎn)vi , vj分別為邊vivj的始點(diǎn)和終點(diǎn). 該圖稱為(n,m)圖,9,對于一個圖g = (v, e ), 人們常用圖形來表示它, 稱其為圖解. 凡是有向邊, 在圖解上都用箭頭標(biāo)明其方向.,例如, 設(shè)v = v1 , v2 , v3 , v4, e = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, 則g = (v, e ) 是一個有4個頂點(diǎn)和6條邊的圖, g的圖解如下圖所示.,10,一個圖會有許多外形不同的圖解, 下面兩個圖表示同一個圖g = (v,

5、e )的圖解.這兩個圖互為同構(gòu)圖,今后將不計(jì)較這種外形上的差別,而用一個容易理解的、確定的圖解去表示一個圖.,11,有邊聯(lián)結(jié)的兩個點(diǎn)稱為相鄰的點(diǎn), 有一個公共端點(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,dout(v1)= dout (v3)= dout (v4)=2, dout(v2)=1 din(v1)= din(v3)= din(v4)=2, din(v2)=1,

6、12,握手定理,握手定理：無向圖中，所有結(jié)點(diǎn)的度數(shù)之和等于2m。 右圖： 推論1：無向圖中必有偶數(shù)個度數(shù)為奇數(shù)的結(jié)點(diǎn)。 推論2：有向圖中所有結(jié)點(diǎn)的出度之和等于入度之和。,d(v1)= d(v3)= d(v4)=4, d(v2)=2,我們今后只討論有限簡單圖：,(1) 頂點(diǎn)個數(shù)是有限的; (2) 任意一條邊有且只有兩個不同的點(diǎn)與它相互關(guān)聯(lián); (3) 若是無向圖, 則任意兩個頂點(diǎn)最多只有一條邊與之相聯(lián)結(jié); (4) 若是有向圖, 則任意兩個頂點(diǎn)最多只有兩條邊與之相聯(lián)結(jié). 當(dāng)兩個頂點(diǎn)有兩條邊與之相聯(lián)結(jié)時，這兩條邊的方向相反. 如果某個有限圖不滿足(2)(3)(4),可在某條邊上增設(shè)頂點(diǎn)使之滿足.,14

7、,定義2 若將圖g的每一條邊e都對應(yīng)一個實(shí)數(shù)f (e), 則稱f (e)為該邊的權(quán), 并稱圖g為賦權(quán)圖(網(wǎng)絡(luò)), 記為g = (v, e , f ).,定義3 任意兩點(diǎn)均有通路的圖稱為連通圖. 定義4 連通而無圈的圖稱為樹, 常用t表示樹.,常用的圖,給定圖g= 和 g = 是兩個圖，如果有 v v 和 e e,則稱圖g是圖 g 的子圖。若v =v 稱圖g是圖 g 的生成子圖； 若將圖g的每一條邊e都對應(yīng)一個實(shí)數(shù)f(e)，則稱f(e)為該邊的權(quán)，并稱圖g為賦權(quán)圖(網(wǎng)絡(luò)), 記為g = 。 任意兩點(diǎn)均有通路的圖稱為連通圖。 連通而無圈的圖稱為樹，常用t=表示樹。 若圖g是圖 g 的生成子圖，且g

8、又是一棵樹，則稱g是圖g 的生成樹。,例 ramsey問題,問題：任何6個人的聚會，其中總會有3個互相認(rèn)識或3人互相不認(rèn)識。 圖論模型：用紅、藍(lán)兩種顏色對6個頂點(diǎn)的完全圖k6的邊進(jìn)行任意著色，則不論如何著色必然都存在一個紅色的k3或一個藍(lán)色的k3 。 對應(yīng)關(guān)系：每個人即為一個結(jié)點(diǎn)；人與人之間的關(guān)系即為一條邊,例 ramsey問題,圖論證明： 用紅、藍(lán)兩種顏色對k6的邊進(jìn)行著色， k6的任意一個頂點(diǎn)均有5條邊與之相連接，這5條邊必有3條邊的顏色是相同的，不妨設(shè)為藍(lán)色（如圖） 與這3條邊相關(guān)聯(lián)的另外3個節(jié)點(diǎn)之間的3條邊，若都為紅色，則形成紅色的k3； 若另外3個節(jié)點(diǎn)之間的3條邊有一條為藍(lán)色，則與上

9、面的藍(lán)色邊形成藍(lán)色的k3； 因此必然存在一個紅色的k3或一個藍(lán)色的k3 。,18,例 ramsey問題,ramsey數(shù)：r（3,3）=6；r（3,4）=9；。,例 過河問題,問題：一擺渡人欲將一只狼、一頭羊、一籃菜從河西渡過河到河?xùn)|。由于船小，一次只能帶一物過河，并且狼與羊，羊與菜不能獨(dú)處，給出渡河方法。 這里顯然不能用一個節(jié)點(diǎn)表示一個物體。一個物體可能在河?xùn)|，也可能在河西，也可能在船上，狀態(tài)表示不清楚。 另外，問題也可以分成幾個小問題，如：問題是否能解？有幾種不同的解法？最快的解決方案是什么？,例 過河問題,解：用四維0-1向量表示(人,狼,羊,菜)在河西岸的狀態(tài)(在河西岸則分量取1，否則取

10、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)向量作為頂點(diǎn)，將可能互相轉(zhuǎn)移的狀態(tài)用邊連接起來構(gòu)成一個圖。 利用圖論的相關(guān)知識即可回答原問題。,例 過河問題,(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)

11、(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個頂點(diǎn)分別記為a1, a2, , a10 , 從圖中易得到兩條路： a1 a6 a3 a7 a2 a8 a5 a10; a1 a6 a3 a9 a4 a8 a5 a10.,問題的轉(zhuǎn)換： 過河問題是否能解？即：圖中a1到a10是否連通？ 有幾種不同的解法？即： a1到a10之間有多少條不同的路徑？ 最快的解決方案是什么？即： a1到a10最短路徑有哪些？,22,圖的矩陣表示, 鄰接

12、矩陣：鄰接矩陣表示了點(diǎn)與點(diǎn)之間的鄰接關(guān)系.一個n階圖g的鄰接矩陣a = (aij )nn , 其中,23,無向圖g的鄰接矩陣a是一個對稱矩陣., 權(quán)矩陣 一個n階賦權(quán)圖g = (v, e, f)的權(quán)矩陣a = (aij ) nn , 其中,有限簡單圖基本上可用權(quán)矩陣來表示.,24,無向圖g的權(quán)矩陣a是一個對稱矩陣.,25, 關(guān)聯(lián)矩陣：一個有m條邊的n階有向圖g的關(guān)聯(lián)矩陣a = (aij )nm , 其中,若vi是ej的始點(diǎn); 若vi是ej的終點(diǎn); 若vi與ej不關(guān)聯(lián).,有向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有一個1,有且僅有一個 - 1.,26,一個有m條邊的n階無向圖g的關(guān)聯(lián)矩陣a = (aij

13、 )nm , 其中,若vi與ej關(guān)聯(lián); 若vi與ej不關(guān)聯(lián).,無向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有兩個1.,2、最短路徑算法,定義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的最短路.,28,重要性質(zhì)：,若v0 v1 vm 是圖g中從v0到vm的最短路, 則1km

14、, 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)圖. 下面分別介紹兩種算法的基本過程.,29,dijkstra算法,指標(biāo)（a為起點(diǎn)） 設(shè)t為v的子集，p=v-t且at，對所有tt，設(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)?/p>

15、最短路徑中可能包含t中其他的節(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), 即: (3)令p=p ux,t=t-x,l(t)表示t中結(jié)點(diǎn)t關(guān)于p的指標(biāo),則,30,dijkstra算法（求a點(diǎn)到其他點(diǎn)的最短路徑）,1、初始化，p=a，t=v-a，對每個結(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) (tt)

16、, 3、若t=,則算法結(jié)束; 否則,令p=p ux,t=t-x 按照公式l(t)=minl(t),l(x)+w(x,t), 計(jì)算t中每一個結(jié)點(diǎn)t關(guān)于p的指標(biāo). 4、p代替p,t代替t,重復(fù)步驟2,3 （ 其中：w(x,y)為圖的權(quán)矩陣）,31,改進(jìn)dijkstra算法（求a點(diǎn)到其他點(diǎn)的最短路徑）,1、初始化，p=a，t=v-a，對每個結(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) (tt); 3、若t=,則算法結(jié)束; 否則,令p=p ux,t=t-x 按照公式l(t)=minl(t),l(x)+w(x,t),

17、計(jì)算t中每一個結(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)矩陣）,32,例 求下圖中a點(diǎn)到其他點(diǎn)的最短路.,floyd算法（求任意兩點(diǎn)的最短路徑）,設(shè)a = (aij )nn為賦權(quán)圖g = (v, e, f)的權(quán)矩陣, dij表示從vi到vj點(diǎn)的距離, rij表示從vi到vj點(diǎn)的最短路中前一個點(diǎn)的編號. 賦初值. 對所有i, j, dij = aij, rij = j. k = 1. 轉(zhuǎn)向. 更新dij , rij . 對所有i, j, 若dik + dk jdij , 則令dij =

18、dik + dkj , rij = k, 轉(zhuǎn)向; 終止判斷. 若k = n終止; 否則令k = k + 1, 轉(zhuǎn)向. 最短路線可由rij得到.,34,例 求下圖中任意兩點(diǎn)間的最短路.,例 設(shè)備更新問題,某企業(yè)每年年初,都要作出決定,如果繼續(xù)使用舊設(shè)備,要付維修費(fèi)；若購買一臺新設(shè)備,要付購買費(fèi).試制定一個5年更新計(jì)劃,使總支出最少. 已知設(shè)備在每年年初的購買費(fèi)分別為11,11, 12,12,13. 使用不同時間設(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)一

19、臺新設(shè)備,虛設(shè)一個點(diǎn)v6表示第5年年底. e =vivj | 1ij6,每條邊vivj表一臺設(shè)備，從第i年年初購買使用到第j年年初報廢.,36,這樣上述設(shè)備更新問題就變?yōu)椋涸谟邢蛸x權(quán)圖g = (v, e, f )(圖解如下)中求v1到v6的最短路問題.,37,由實(shí)際問題可知,設(shè)備使用三年后應(yīng)當(dāng)更新,因此刪除該圖中v1到v5 ,v1到v6 ,v2到v6的連線；又設(shè)備使用一年后就更新則不劃算,因此再刪除該圖中v1v2 ,v2v3 ,v3v4 ,v4v5 ,v5v6 五條連線后得到,從上圖中容易得到v1到v6只有兩條路：,v1v3v6和v1v4v6.,而這兩條路都是v1到v6的最短路.,3、最小生成

20、樹,由樹的定義不難知道, 任意一個連通的(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的最小生成樹-minimum-cost spanning tree (mst). 求最小生成樹問題有很廣泛的實(shí)際應(yīng)用. 例如, 把n個鄉(xiāng)鎮(zhèn)用高壓電纜連接起來建立一個電網(wǎng), 使所用的電纜長度之和最短, 即費(fèi)用最小, 就是一個求最小生成樹問題.,39,kruskal算法,從未選入樹中的邊中選取權(quán)重最小的且

21、不構(gòu)成回路的邊加入到樹中.（判斷回路比較麻煩）,算法過程： 1.將各邊按權(quán)值從小到大進(jìn)行排序 2.找出權(quán)值最小且不與已加入最小生成樹集合的邊構(gòu)成回路的邊。若符合條件，則加入最小生成樹的集合中。不符合條件則繼續(xù)遍歷圖，尋找下一個最小權(quán)值的邊。 3.遞歸重復(fù)步驟1，直到找出n-1條邊為止，得到最小生成樹。,時間復(fù)雜度只和邊有關(guān)，可以證明其時間復(fù)雜度為o(mlogm),40,求最小生成樹,41,prim算法,把結(jié)點(diǎn)分成兩個集合，已加入樹中的(p)和未加入樹中的(q)，然后每次選擇一個點(diǎn)在p中一個點(diǎn)在q中的權(quán)重最小的邊，加入樹中，并把相應(yīng)點(diǎn)加入p中。,類似地,可定義連通圖g 的最大生成樹.,算法過程：

22、 1：初始化：任取一個節(jié)點(diǎn)u加入生成樹,p=u0, q=v-u0, 生成樹的邊集te=。 2：在所有up,vq的邊(u,v) （稱為可選邊集）中，找一條權(quán)重最小的邊(u1,v1)，將此邊加進(jìn)集合te中，并將v加入p中。同時對與v關(guān)聯(lián)的邊，若另一個端點(diǎn)已經(jīng)在p中，則從可選邊集中刪除，否則加入可選邊集。 3：如果p=v，則算法結(jié)束；否則重復(fù)步驟2。 我們可以算出當(dāng)u=v時，步驟2共執(zhí)行了n1次，te中也增加了n1條邊，這n1條邊就是需要求出的最小生成樹的邊。,例 選址問題,現(xiàn)準(zhǔn)備在 n 個居民點(diǎn)v1, v2, , vn中設(shè)置一銀行.問設(shè)在哪個點(diǎn),可使最大服務(wù)距離最小? 若設(shè)置兩個銀行,問設(shè)在哪兩個

23、點(diǎn)? 模型假設(shè) 假設(shè)各個居民點(diǎn)都有條件設(shè)置銀行,并有路相連,且路長已知. 模型建立與求解 用floyd算法求出任意兩個居民點(diǎn)vi , vj 之間的最短距離,并用dij 表示., 設(shè)置一個銀行,銀行設(shè)在 vi 點(diǎn)的最大服務(wù)距離為,43,求k,使,即若設(shè)置一個銀行,則銀行設(shè)在 vk 點(diǎn),可使最大服務(wù)距離最小. 設(shè)置兩個銀行,假設(shè)銀行設(shè)在vs , vt 點(diǎn)使最大服務(wù)距離最小.,記,則s,t 滿足：,進(jìn)一步,若設(shè)置多個銀行呢？,44,4、遍歷性問題,一、歐拉圖 g=(v,e)為一連通無向圖 經(jīng)過g中每條邊至少一次的回路稱為巡回； 經(jīng)過g中每條邊正好一次的巡回稱為歐拉巡回； 存在歐拉巡回的圖稱為歐拉圖。

24、 二、中國郵遞員問題（cppchinese postman problem） 一名郵遞員負(fù)責(zé)投遞某個街區(qū)的郵件。如何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？ 這一問題是我國管梅谷教授1962年首先提出，國際上稱之為中國郵遞員問題。,45,解法： 若本身就是歐拉圖，則直接可以找到一條歐拉巡回就是本問題的解。 若不是歐拉圖，必定有偶數(shù)個奇度數(shù)結(jié)點(diǎn)，在這些奇度數(shù)點(diǎn)之間添加一些邊，使之變成歐拉圖，再找出一個歐拉巡回。 具體解法：fleury算法+edmonds最小對集算法,46,三、哈密爾頓圖 g=(v,e)為一連通無向圖 經(jīng)過g中每點(diǎn)一次且正好一次

25、的路徑稱為哈密爾頓路徑； 經(jīng)過g中每點(diǎn)一次且正好一次的回路稱為哈密爾頓回路； 存在哈密爾頓回路的圖稱為哈密爾頓圖。 四、旅行商問題（tsptraveling salesman problem） 一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計(jì)一條最短的旅行路線？ 即：從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地（最小哈密爾頓回路） 對于n個節(jié)點(diǎn)的旅行商問題，n個節(jié)點(diǎn)的任意一個全排列都是問題的一個可能解（假設(shè)任意兩個點(diǎn)之間都有邊）。g個節(jié)點(diǎn)的全排列有(n-1)!個，因此間題歸結(jié)為在(n-1)!個回路中選取最小回路。 tsp問題的解法屬于np完全問題，一般只研究其近似解法,47,最鄰近算法

26、 (1) 選取任意一個點(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)元方法， 遺傳算法等等,5、二分圖與匹配,定義1 設(shè)x,y 都是非空有限集,且xy = , e xy|xx,yy, 稱g =(x, y, e)為二部圖. 二部圖可認(rèn)為是有限簡單無向圖. 如果x中的每個點(diǎn)都與y中的每個點(diǎn)鄰接,則稱g =(x, y, e)為完備二部圖.

27、若f：er +,則稱g =(x, y, e, f )為二部賦權(quán)圖. 二部賦權(quán)圖的權(quán)矩陣一般記作 a=(aij )|x|y | , 其中aij = f (xi yj ).,49,定義2 設(shè)g =(x, y, e)為二部圖,且m e.若m中任意兩條邊在g中均不鄰接,則稱m是二部圖g的一個匹配.,定義3 設(shè)m是二部圖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的最佳匹配. 顯然,每個完美匹配都是最大匹配,反之

28、不一定成立.,50,工作安排問題之一,給n個工作人員x1, x2, , xn安排n項(xiàng)工作y1, y2, , yn. n個工作人員中每個人能勝任一項(xiàng)或幾項(xiàng)工作, 但并不是所有工作人員都能從事任何一項(xiàng)工作. 比如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)化為求二部圖的一個完美匹配. 因?yàn)?|x|=|y|

29、, 所以完美匹配即為最大匹配.,51,求二部圖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中一個既有標(biāo)號又有標(biāo)記*的點(diǎn)xi , 去掉xi的標(biāo)記*, 轉(zhuǎn)向. 找出在g中所有與xi鄰接的點(diǎn)yj , 若所有這樣的yj都已有標(biāo)號, 則轉(zhuǎn)向, 否則轉(zhuǎn)向.,52, 對與xi鄰接且尚未給標(biāo)號的yj都給定標(biāo)號i.,若所有的 yj 都是m的飽和點(diǎn),則轉(zhuǎn)向,否則逆向返回. 即由其中m的任一個非

30、飽和點(diǎn) yj 的標(biāo)號i 找到xi ,再由 xi 的標(biāo)號k 找到 yk ,最后由 yt 的標(biāo)號s找到標(biāo)號為0的xs時結(jié)束,獲得m-增廣路xs yt xi yj , 記p =xs yt , , xi yj ,重新記m為mp,轉(zhuǎn)向. 不必理會m-增廣路的定義. mp = mp mp, 是對稱差. 將yj在m中與之鄰接的點(diǎn)xk ,給以標(biāo)號 j 和標(biāo)記*, 轉(zhuǎn)向.,53,例 求下圖所示二部圖g的最大匹配,解 取初始匹配m0 =x2 y2 , x3 y3 , x5 y5 (上圖粗線所示). 給x中m0的兩個非飽和點(diǎn)x1,x4都給以標(biāo)號0和標(biāo)記* (如下圖所示)., 去掉x1的標(biāo)記*, 將與x1鄰接的兩個點(diǎn)

31、y2, y3都給以標(biāo)號1. 因?yàn)閥2, y3都是m0的兩個飽和點(diǎn),所以將它們在m0中鄰接的兩個點(diǎn)x2, x3都給以相應(yīng)的標(biāo)號和標(biāo)記* (如下圖所示).,54, 去掉x2的標(biāo)記*, 將與x2鄰接且尚未給標(biāo)號的三個點(diǎn)y1, y4, y5都給以標(biāo)號2 (如下圖所示)., 因?yàn)閥1是m0的非飽和點(diǎn), 所以順著標(biāo)號逆向返回依次得到x2, y2, 直到x1為0為止.于是得到m0的增廣路x1 y2x2 y1, 記p = x1 y2 , y2x2 , x2 y1. 取m1 = m0p = x1 y2 , x2 y1 , x3 y3 , x5 y5, 則m1是比m多一邊的匹配(如下圖所示).,55, 再給x中m

32、1的非飽和點(diǎn)x4給以標(biāo)號0和標(biāo)記*, 然后去掉x4的標(biāo)記*, 將與x4鄰接的兩個點(diǎn)y2, y3都給以標(biāo)號4.,因?yàn)閥2, y3都是m1的兩個飽和點(diǎn), 所以將它們在m1中鄰接的兩個點(diǎn)x1, x3都給以相應(yīng)的標(biāo)號和標(biāo)記* (如下圖所示)., 去掉x1的標(biāo)記*, 因?yàn)榕cx1鄰接的兩個點(diǎn)y2, y3都有標(biāo)號4, 所以去掉x3的標(biāo)記*.,而與x3鄰接的兩個點(diǎn)y2, y3也都有標(biāo)號4, 此時x中所有有標(biāo)號的點(diǎn)都已去掉了標(biāo)記*(如下圖所示), 因此m1是g的最大匹配.,g不存在飽和x的每個點(diǎn)的匹配, 當(dāng)然也不存在完美匹配.,56,工作安排問題之二,給n個工作人員x1, x2, , xn安排n項(xiàng)工作y1, y

33、2, , 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è)點(diǎn)x或y,使|x|=|y|.如此就將g 轉(zhuǎn)化為完備二部賦權(quán)圖,而且不會影響結(jié)果.,57,定義 設(shè)g =(x, y, e, f)為完備的二部賦權(quán)圖, 若

34、l：x y r + 滿足： xx, yy, l(x) + l(y)f(xy), 則稱l為g的一個可行點(diǎn)標(biāo)記,記相應(yīng)的生成子圖為gl =(x, y, el , f),這里 el =xye|l(x) + l (y) = f (xy).,求完備二部賦權(quán)圖g = (x, y, e, f )的最佳匹配算法迭代步驟： 設(shè)g =(x, y, e, f)為完備的二部賦權(quán)圖,l是其一個初始可行點(diǎn)標(biāo)記,通常取 l(x) = max f (x y) | yy, xx, l(y) = 0, yy.,58,m是gl的一個匹配., 若x的每個點(diǎn)都是飽和的,則m是最佳匹配.否則取m的非飽和點(diǎn)ux,令s =u, t =,轉(zhuǎn)向

35、. 記nl(s)=v|us,uvgl. 若nl(s)= t, 則gl沒有完美匹配, 轉(zhuǎn)向. 否則轉(zhuǎn)向. 調(diào)整標(biāo)記, 計(jì)算 al=minl(x) + l (y) - f (xy)|xs, yyt. 由此得新的可行點(diǎn)標(biāo)記,令l = h, gl = gh , 重新給出gl的一個匹配m, 轉(zhuǎn)向., 取ynl (s)t , 若y是m的飽和點(diǎn), 轉(zhuǎn)向. 否則, 轉(zhuǎn)向., 設(shè)x ym, 則令s = s x , t = t y , 轉(zhuǎn)向., 在gl中的u - y路是m- 增廣路, 設(shè)為p, 并令 m = mp, 轉(zhuǎn)向.,59,6、網(wǎng)絡(luò)流問題,定義1 設(shè)g =(v, e )為有向圖,在v中指定一點(diǎn)稱為發(fā)點(diǎn)(記為

36、vs ),和另一點(diǎn)稱為收點(diǎn)(記為vt ), 其余點(diǎn)叫做中間點(diǎn). 對每一條邊vivje,對應(yīng)一個非負(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上的一個流. 滿足下述條件的流 f 稱為可行流： (限制條件)對每一邊vivj ,有0 fij cij ; (平衡條件)對于中間點(diǎn)vk有fik =fkj , 即中間點(diǎn)vk的輸入量 = 輸出量.,60,如果 f 是可行流,則對收、發(fā)點(diǎn)vt、vs有 fsi =fjt =wf , 即從vs點(diǎn)發(fā)出的物質(zhì)總

37、量 = vt點(diǎn)輸入的量. wf 稱為網(wǎng)絡(luò)流 f 的總流量.,上述概念可以這樣來理解,如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就是一個可行流(稱為零流).,61,所謂最大流問題就是在容量網(wǎng)絡(luò)中,尋找流量最大的可行流.,實(shí)際問題中,一個網(wǎng)絡(luò)會出現(xiàn)下面兩種情況： 發(fā)點(diǎn)和收點(diǎn)都不止一個. 解決的方法是再虛設(shè)一個發(fā)點(diǎn)vs和一個收點(diǎn)vt ,發(fā)點(diǎn)vs到所有原發(fā)點(diǎn)邊的容量都設(shè)為無窮大, 所有原收點(diǎn)到收點(diǎn)

38、vt 邊的容量都設(shè)為無窮大. 網(wǎng)絡(luò)中除了邊有容量外,點(diǎn)也有容量. 解決的方法是將所有有容量的點(diǎn)分成兩個點(diǎn),如點(diǎn)v有容量cv ,將點(diǎn)v分成兩個點(diǎn)v和v,令 c(vv ) = cv .,62,最小費(fèi)用流問題,這里我們要進(jìn)一步探討不僅要使網(wǎng)上的流達(dá)到最大,或者達(dá)到要求的預(yù)定值,而且還要使運(yùn)輸流的費(fèi)用是最小的,這就是最小費(fèi)用流問題.,最小費(fèi)用流問題的一般提法： 已知網(wǎng)絡(luò)g = (v, e, c ),每條邊vivje 除了已給容量cij外,還給出了單位流量的費(fèi)用bij(0). 所謂最小費(fèi)用流問題就是求一個總流量已知的可行流 f = f ij 使得總費(fèi)用,最小.,63,特別地,當(dāng)要求 f 為最大流時, 即

39、為最小費(fèi)用最大流問題.,設(shè)網(wǎng)絡(luò)g = (v, e, c), 取初始可行流 f 為零流, 求解最小費(fèi)用流問題的迭代步驟： 構(gòu)造有向賦權(quán)圖gf =(v, ef , f),對于任意的vivje,ef ,f 的定義如下： 當(dāng) f ij = 0時,vivjef ,f(vivj )= bij ; 當(dāng) f ij = cij時,vjvief ,f(vjvi )= - bij ; 當(dāng)0 f ijcij時,vivjef ,f(vivj )= bij ,vjvief , f(vjvi ) = - bij . 然后轉(zhuǎn)向.,64, 求出含有負(fù)權(quán)的有向賦權(quán)圖gf =(v, ef , f)中發(fā)點(diǎn)vs到收點(diǎn)vt的最短路 ,若

40、最短路 存在轉(zhuǎn)向; 否則f是所求的最小費(fèi)用最大流,停止., 增流.,vivj與相同, vivj與相反.,令 = min ij|vivj , 重新定義流 f = f ij為,其它情況不變.,如果wf 大于或等于預(yù)定的流量值,則適當(dāng)減少 值,使wf 等于預(yù)定的流量值,那么 f 是所求的最小費(fèi)用流, 停止; 否則轉(zhuǎn)向.,65,下面介紹求解有向賦權(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,

41、, n . (i )= min (i ),min ( j ) + wji | ji . 若所有的 (i )都無變化,停止;否則轉(zhuǎn)向. 在算法的每一步, (i )都是從v1到vi的最短路長度的上界. 若不存在負(fù)長回路,則從v1到vi的最短路長度是 (i )的下界,經(jīng)過n - 1次迭代后 (i )將保持不變. 若在第n次迭代后 (i )仍在變化時, 說明存在負(fù)長回路.,66,7、關(guān)鍵路徑問題（拓?fù)渑判颍?一項(xiàng)工程任務(wù),大到建造一座大壩,一座體育中心,小至組裝一臺機(jī)床,一架電視機(jī), 都要包括許多工序.這些工序相互約束,只有在某些工序完成之后, 一個工序才能開始. 即它們之間存在完成的先后次序關(guān)系,一

42、般認(rèn)為這些關(guān)系是預(yù)知的, 而且也能夠預(yù)計(jì)完成每個工序所需要的時間. 這時工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時間才能夠完成整個工程項(xiàng)目, 影響工程進(jìn)度的要害工序是哪幾個？,67,pt(potentialtask graph)圖,在pt(potentialtask graph)圖中,用結(jié)點(diǎn)表示工序,如果工序 i 完成之后工序 j 才能啟動,則圖中有一條有向邊(i , j ),其長度wi 表示工序 i 所需的時間.,這種圖必定不存在有向回路,否則某些工序?qū)⒃谧陨硗瓿芍蟛拍荛_始,這顯然不符合實(shí)際情況. 在pt圖中增加兩個虛擬結(jié)點(diǎn)v0和vn ,使所有僅為始點(diǎn)的結(jié)點(diǎn)都直接與v0聯(lián)結(jié),v0為新增邊的始點(diǎn)

43、,這些新增邊的權(quán)都設(shè)為0; 使所有僅為終點(diǎn)的結(jié)點(diǎn)都直接與vn聯(lián)結(jié),vn為新增邊的終點(diǎn). 這樣得到的圖g仍然不存在有向回路.,68,例 一項(xiàng)工程由13道工序組成, 所需時間(單位：天)及先行工序如下表所示(p172). 工序序號 a b c d e f g h i 所需時間 2 6 3 2 4 3 8 4 2 先行工序 a a b c,d d d d g,h 工序序號 j k l m 所需時間 3 8 5 6 先行工序 g h,e j k,試問這項(xiàng)工程至少需要多少天才能完成? 那些工程不能延誤? 那些工程可以延誤? 最多可延誤多少天?,69,先作出該工程的pt圖.由于除了工序a外，均有先行工序,

44、因此不必虛設(shè)虛擬結(jié)點(diǎn)v0.,在pt圖中,容易看出各工序先后完成的順序及時間.,虛擬結(jié)點(diǎn),70,這項(xiàng)工程至少需要多少天才能完成?,就是要求a到n的最長路,此路徑稱為關(guān)鍵路徑.,那些工程不能延誤? 那些工程可以延誤? 最多可延誤多少天? 關(guān)鍵路徑上的那些工程不能延誤.,71,關(guān)鍵路徑(最長路徑)算法,定理 若有向圖g中不存在有向回路,則可以將g 的結(jié)點(diǎn)重新編號為u1, u2, , un,使得對任意的邊ui uje(g),都有i j .,各工序最早啟動時間算法步驟： 根據(jù)定理對結(jié)點(diǎn)重新編號為u1, u2, , un . 賦初值 (u1)= 0. 依次更新 (uj ),j = 2, 3, , n .

45、(uj )= max(ui )+ (ui ,uj )|uiuje(g). 結(jié)束. 其中(uj )表示工序 uj 最早啟動時間,而(un)即(vn)是整個工程完工所需的最短時間.,72,此例不必重新編號，只要按字母順序即可.,(a)=0, (b)=(c)=2, (d)=8, (e)=max2+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)鍵路徑

46、?,73,通過以上計(jì)算表明：,這項(xiàng)工程至少需要28天才能完成. 關(guān)鍵路徑(最長路徑): abdekmn abdhkmn,工序a,b,d,e,h,k,m不能延誤,否則將影響工程的完成.,但是對于不在關(guān)鍵路徑上的工序, 是否允許延誤？如果允許, 最多能夠延誤多長時間呢？ 各工序允許延誤時間t(uj )等于各工序最晚啟動時間(uj )減去各工序最早啟動時間(uj ). 即 t(uj )=(uj )-(uj ).,74,最晚啟動時間算法步驟(已知結(jié)點(diǎn)重新編號)：, 賦初值 (un )=(un). 更新 (uj ),j = n - 1, n - 2, , 1. (uj )= min(ui )- (ui

47、,uj )|uiuje(g). 結(jié)束.,順便提一句,根據(jù)工序uj允許延誤時間t(uj )是否為0,可判斷該工序是否在關(guān)鍵路徑上.,75,(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.,76,各工序允許延誤時間如下：,t(a)=t(b)

48、=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.,77,pert圖,在pert(programme evaluation and review technique)圖中, 采用有向邊表示工序, 其權(quán)值表示該工序所需時間. 如果工序ei完成后ej才能開始, 則令vk 是ei的終點(diǎn), ej 的始點(diǎn). 根據(jù)這種約定, 前例的pert圖如下：,對于pert圖,一些算法與pt圖類似.,78,pt圖要比pert圖好一些. pt圖的結(jié)點(diǎn)數(shù)基本上是固定的,這是最重要的一點(diǎn),容易編程計(jì)算.,另外pt圖比pert圖更

49、加靈活,它能適應(yīng)一些額外的約束. 例如下圖中, 表示工序vi完成一半之后vj就可以開始., 表示工序vi完成后經(jīng)過t 時刻vj才開始., 表示在時間bj 之后工序vj才能開始,其中v0表示虛擬結(jié)點(diǎn).,79,8、系統(tǒng)監(jiān)控模型,定義1 設(shè)圖g = (v, e), kv如果圖g的每條邊都至少有一個頂點(diǎn)在k中,則稱k是g的一個點(diǎn)覆蓋. 若g的一個點(diǎn)覆蓋中任意去掉一個點(diǎn)后不再是點(diǎn)覆蓋, 則稱此點(diǎn)覆蓋是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 都是最小

50、點(diǎn)覆蓋.,80,系統(tǒng)監(jiān)控問題之一,假設(shè)v1, v2, , v7是7個哨所,監(jiān)視著11條路段(如下圖所示),為節(jié)省人力,問至少需要在幾個哨所派人站崗,就可以監(jiān)視全部路段? 這就是要求最小點(diǎn)覆蓋問題.,v1, v3, v5, v6和v1, v3, v5, v7都是最小點(diǎn)覆蓋, 所以至少需要在4個哨所派人站崗來監(jiān)視全部路段.,到目前為止,還沒有找到求最小點(diǎn)覆蓋的有效算法,即多項(xiàng)式時間算法(算法步數(shù)不超過nc,n為g的頂點(diǎn)數(shù),c為常數(shù)).有一些啟發(fā)式近似算法.,81,最大獨(dú)立點(diǎn)集,定義2 設(shè)圖g = (v, e ),i v如果i中任意兩個頂點(diǎn)在g中都不相鄰, 則稱i是g的一個獨(dú)立點(diǎn)集. 若g的一個獨(dú)立

51、點(diǎn)集中,任意添加一個點(diǎn)后不再是獨(dú)立點(diǎn)集,則稱此獨(dú)立點(diǎn)集是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)集.,82,最小控制集,定義3 設(shè)圖g = (v, e ), d v如果vv, 要么vd, 要么v與d的某個點(diǎn)相鄰, 則稱d是g的一個控制集. 若g 的一個控制集中任意去掉一個點(diǎn)后不再是控制集,則稱此控制集是g的一個極小控制集. 頂點(diǎn)數(shù)最少的控制集,稱為g的最小控制集.,例如, 右圖中,v1, v3, v5是極小控制集, v0是最小控制集.,83,系統(tǒng)監(jiān)控問題之二,假設(shè)下圖代表一指揮系統(tǒng),頂點(diǎn)v1, v2, , v7表示被指揮的單位,邊表示可以直接下達(dá)命令的通信線路. 欲在某些單位建立指揮站,以便可以通過指揮站直接給各單位下達(dá)命令,問至少需要建立幾個指揮站? 這就是要求最小控制集問題.,v1, v3,v3, v5等都是最小控制集,