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

數(shù)學(xué)建模

圖論方法專題數(shù)學(xué)建模圖論方法專題專題板塊系列概率統(tǒng)計(jì)專題1優(yōu)化專題2模糊方法及微分方程專題3圖論方法專題4華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；貙ｎ}板塊系列概率統(tǒng)計(jì)專題1優(yōu)化專題2模糊方法及微分方程專題32圖論方法專題一圖論的基本概念二最短路與最小生成樹(shù)三二部圖的匹配四網(wǎng)絡(luò)流華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地圖論方法專題一圖論的基本概念二最短路與最小生成樹(shù)三二部圖的匹3ABCD哥尼斯堡七橋示意圖問(wèn)題1:七橋問(wèn)題能否從任一陸地出發(fā)通過(guò)每座橋恰好一次而回到出發(fā)點(diǎn)？圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；谹BCD哥尼斯堡七橋示意圖問(wèn)題1:七橋問(wèn)題圖論的基本概念ww4七橋問(wèn)題模擬圖:ABDC歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過(guò)每座橋恰好一次而回到出發(fā)地。圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地七橋問(wèn)題模擬圖:ABDC歐拉指出：如果每塊陸地所連接的橋都是5問(wèn)題2:哈密頓圈（環(huán)球旅行游戲）十二面體的20個(gè)頂點(diǎn)代表世界上20個(gè)城市，能否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過(guò)每個(gè)城市恰好一次最后回到出發(fā)點(diǎn)？圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；貑?wèn)題2:哈密頓圈（環(huán)球旅行游戲）圖論的基本概念www.shu6問(wèn)題3:四色問(wèn)題對(duì)任何一張地圖進(jìn)行著色，兩個(gè)共同邊界的國(guó)家染不同的顏色，則只需要四種顏色就夠了。德·摩爾根致哈密頓的信（1852年10月23日）

我的一位學(xué)生今天請(qǐng)我解釋一個(gè)我過(guò)去不知道，現(xiàn)在仍不甚了了的事實(shí)。他說(shuō)如果任意劃分一個(gè)圖形并給各部分著上顏色，使任何具有公共邊界的部分顏色不同，那么需要且僅需要四種顏色就夠了。下圖是需要四種顏色的例子（圖1）。……圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地問(wèn)題3:四色問(wèn)題對(duì)任何一張地圖進(jìn)行著色，兩個(gè)共同7問(wèn)題4(關(guān)鍵路徑問(wèn)題):

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

這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間才能夠完成整個(gè)工程項(xiàng)目,影響工程進(jìn)度的要害工序是哪幾個(gè)？圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地問(wèn)題4(關(guān)鍵路徑問(wèn)題):圖論的基本概念www.shumo.c8定義1一個(gè)有序二元組(V,E)稱為一個(gè)圖,記為G=(V,E),其中①V或V(G)稱為G的頂點(diǎn)集,V≠Φ,其元素稱為頂點(diǎn)或結(jié)點(diǎn),簡(jiǎn)稱點(diǎn);②

E或E(G)稱為G的邊集,其元素稱為邊,它聯(lián)結(jié)V中的兩個(gè)點(diǎn),如果這兩個(gè)點(diǎn)是無(wú)序的,則稱該邊為無(wú)向邊,否則,稱為有向邊.圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟x1一個(gè)有序二元組(V,E)稱為一個(gè)圖,記為圖9如果V={v1,v2,…,vn}是有限非空點(diǎn)集,則稱G為有限圖或n階圖.如果E的每一條邊都是無(wú)向邊,則稱G為無(wú)向圖;如果E的每一條邊都是有向邊,則稱G為有向圖;否則,稱G為混合圖.記E={e1,e2,…,em}(ek

=vivj).圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地如果V={v1,v2,…,vn}是有限非空點(diǎn)集,10對(duì)于一個(gè)圖G=(V,E),人們常用圖形來(lái)表示它,稱其為圖解.凡是有向邊,在圖解上都用箭頭標(biāo)明其方向.稱點(diǎn)vi,vj為邊vivj的端點(diǎn).有邊聯(lián)結(jié)的兩個(gè)點(diǎn)稱為相鄰頂點(diǎn),有一個(gè)公共端點(diǎn)的邊稱為相鄰邊.邊和它的端點(diǎn)稱為互相關(guān)聯(lián).有向圖中的關(guān)聯(lián)又分出關(guān)聯(lián)和入關(guān)聯(lián)。圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；貙?duì)于一個(gè)圖G=(V,E),人們常用圖形來(lái)表示它,11常用d(v)表示圖G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目,

d(v)稱為頂點(diǎn)v的度數(shù).與頂點(diǎn)v出關(guān)聯(lián)的邊的數(shù)目稱為出度，記作d

+(v),與頂點(diǎn)v入關(guān)聯(lián)的邊的數(shù)目稱為入度，記作d

-(v)。用N(v)表示圖G中所有與頂點(diǎn)v相鄰的頂點(diǎn)的集合.圖論的基本概念任意兩頂點(diǎn)都相臨的簡(jiǎn)單圖稱為完全圖.有n個(gè)頂點(diǎn)的完全圖記為K

n。華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；爻Ｓ胐(v)表示圖G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目,用N(v12幾個(gè)基本定理：圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；貛讉€(gè)基本定理：圖論的基本概念華中農(nóng)業(yè)13用圖論思想求解以下各題例1、一擺渡人欲將一只狼，一頭羊，一籃菜從河西渡過(guò)河到河?xùn)|，由于船小，一次只能帶一物過(guò)河，并且，狼與羊，羊與菜不能獨(dú)處，給出渡河方法。圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；赜脠D論思想求解以下各題例1、一擺渡人欲將一只狼，一頭羊，一籃14解：用四維0-1向量表示（人，狼，羊，菜）的在西岸狀態(tài)，（在西岸則分量取1，否則取0.）共24=16種狀態(tài)，由題設(shè)，狀態(tài)（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允許的，從而對(duì)應(yīng)狀態(tài)（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允許的，圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；亟猓河盟木S0-1向量表示（人，狼，羊，菜）的在西岸共24=115人在河西：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,1,1）（1,0,1,0）（0,1,0,1）（0,1,0,0）（0,0,1,0）（0,0,0,1）（0,0,0,0）人在河?xùn)|：以十個(gè)向量作為頂點(diǎn)，將可能互相轉(zhuǎn)移的狀態(tài)連線，則得10個(gè)頂點(diǎn)的偶圖。問(wèn)題：如何從狀態(tài)（1,1,1,1）轉(zhuǎn)移到（0,0,0,0）？方法：從（1,1,1,1）開(kāi)始，沿關(guān)聯(lián)邊到達(dá)沒(méi)有到達(dá)的相鄰頂點(diǎn)，到（0,0,0,0）終止，得到有向圖即是。圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；厝嗽诤游鳎海?,1,1,1）（1,1,1,0）（1,1,0,16例2、考慮中國(guó)象棋的如下問(wèn)題：（1）下過(guò)奇數(shù)盤棋的人數(shù)是偶數(shù)個(gè)。（2）馬有多少種跳法？（3）馬跳出后又跳回起點(diǎn)，證明馬跳了偶數(shù)步。（4）紅方的馬能不能在自己一方的棋盤上不重復(fù)的跳遍每一點(diǎn)，最后跳回起點(diǎn)？圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?、考慮中國(guó)象棋的如下問(wèn)題：圖論的基本概念www.shum17例3、證明：在任意6人的集會(huì)上，總有3人互相認(rèn)識(shí)，或總有3人互相不認(rèn)識(shí)。解：以頂點(diǎn)表示人，以邊表示認(rèn)識(shí)，得6個(gè)頂點(diǎn)的簡(jiǎn)單圖G。問(wèn)題：3人互相認(rèn)識(shí)即G包含K3為子圖，3人互相不認(rèn)識(shí)即G包含（3,0）圖為子圖。圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?、證明：在任意6人的集會(huì)上，總有3人互相認(rèn)解：以頂點(diǎn)表示18圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；貓D論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基19定義2若將圖G的每一條邊e都對(duì)應(yīng)一個(gè)實(shí)數(shù)F(e),則稱F(e)為該邊的權(quán),并稱圖G為賦權(quán)圖(網(wǎng)絡(luò)),記為G=(V,E,F).定義3設(shè)G=(V,E)是一個(gè)圖,v0,v1,…,vk∈V,且“1≤i≤k,vi－1vi∈E,則稱v0v1…

vk是G的一條通路.圖論的基本概念

如果通路中沒(méi)有相同的頂點(diǎn),則稱此通路為路徑,簡(jiǎn)稱路.始點(diǎn)和終點(diǎn)相同的路稱為圈或回路.華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟x2若將圖G的每一條邊e都對(duì)應(yīng)一個(gè)實(shí)數(shù)F(e),則稱20定義4頂點(diǎn)u與v稱為連通的，如果存在u-v通路，任二頂點(diǎn)都連通的圖稱為連通圖，否則，稱為不連通圖。極大連通子圖稱為連通支。圖論的基本概念定義5連通而無(wú)圈的圖稱為樹(shù),常用T表示樹(shù).樹(shù)中最長(zhǎng)路的長(zhǎng)稱為樹(shù)的高。樹(shù)的度為1的頂點(diǎn)稱為樹(shù)葉。其余的頂點(diǎn)稱為分枝點(diǎn)。樹(shù)的邊稱為樹(shù)枝。設(shè)G是有向圖，如果G的基礎(chǔ)圖是樹(shù)，則稱G是有向樹(shù)，也簡(jiǎn)稱樹(shù)。華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地定義4頂點(diǎn)u與v稱為連通的，如果存在u-v通路，任二頂點(diǎn)都21⑴

鄰接矩陣

A=(aij)n×n,例4：寫出右圖的鄰接矩陣：解：圖的矩陣表示華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地⑴鄰接矩陣A=(aij)n×n,例4：寫出右圖22⑵權(quán)矩陣A=(aij)n×n例5：寫出右圖的權(quán)矩陣：解：圖的矩陣表示華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；丌茩?quán)矩陣A=(aij)n×n例5：寫出右圖的權(quán)矩23⑶

關(guān)聯(lián)矩陣A=(aij)n×m

有向圖：無(wú)向圖：圖的矩陣表示華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地⑶關(guān)聯(lián)矩陣A=(aij)n×m

有向圖：無(wú)向圖：24例6：寫出右圖與其基本圖的關(guān)聯(lián)矩陣解：分別為：圖的矩陣表示華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?：寫出右圖與其基本圖解：分別為：圖的矩陣表示www.sh25定義1

設(shè)

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

若P0(u,v)是G

中連接u,v的路徑,且對(duì)任意在G

中連接u,v的路徑P(u,v)都有F(P0

)≤F(P),則稱P0(u,v)是G

中連接u,v的最短路.最短路華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地定義1設(shè)P(u,v)是賦權(quán)圖G=(V,E26重要性質(zhì)：若v0v1…

vm是G中從v0到vm的最短路,則對(duì)1≤k≤m,v0v1…

vk必為G中從v0到vk的最短路.即：最短路是一條路，且最短路的任一段也是最短路。最短路華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地重要性質(zhì)：若v0v1…vm是G中從v0到vm的最短路27例7對(duì)下面的有向圖求頂點(diǎn)v0到其余頂點(diǎn)的最短路。1445642537最短路華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地例7對(duì)下面的有向圖求頂點(diǎn)v0到其余頂點(diǎn)的1445642528Dijkstra算法：求某一頂點(diǎn)到其余頂點(diǎn)的最短路最短路華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；谼ijkstra算法：求某一頂點(diǎn)到其余頂點(diǎn)的最短路最短路ww2968－523－374例8：求下列任意兩點(diǎn)的最短路和距離。最短路華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；?8－523－374例8：求下列任意兩點(diǎn)的最短路和距離。最短30Floyd算法:求任意兩頂點(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)的編號(hào).

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

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

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

最短路線可由rij得到.最短路華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；谾loyd算法:求任意兩頂點(diǎn)的最短路設(shè)A=(ai31求非負(fù)賦權(quán)圖G中某一點(diǎn)到其它各點(diǎn)最短路，一般用Dijkstra標(biāo)號(hào)算法；

Dijkstra標(biāo)號(hào)算法只適用于全部權(quán)為非負(fù)情況。求非負(fù)賦權(quán)圖上任意兩點(diǎn)間的最短路，一般用Floyd算法.Floyd算法可以適用于有負(fù)權(quán)的情況，還能判斷是否有負(fù)回路。這兩種算法均適用于有向賦權(quán)圖.最短路華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地求非負(fù)賦權(quán)圖G中某一點(diǎn)到其它各點(diǎn)最短路，一般最短32由樹(shù)的定義不難知道,任意一個(gè)連通的(p,q)圖G適當(dāng)去掉q-p+1條邊后,都可以變成樹(shù),這棵樹(shù)稱為圖G的生成樹(shù).設(shè)T是圖G的一棵生成樹(shù),用F(T)表示樹(shù)T中所有邊的權(quán)數(shù)之和,F(T)稱為樹(shù)T的權(quán).一個(gè)連通圖G的生成樹(shù)一般不止一棵,圖G的所有生成樹(shù)中權(quán)數(shù)最小的生成樹(shù)稱為圖G的最小生成樹(shù).最小生成樹(shù)華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；赜蓸?shù)的定義不難知道,任意一個(gè)連通的(p,q)設(shè)T是圖G的3364686865505061456054例9：如下圖G，求最小生成樹(shù)：Kruskal算法：從最小邊開(kāi)始按最小權(quán)加邊，有圈去掉。最小生成樹(shù)華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地64686865505061456054例9：如下圖G，求最34例10(設(shè)備更新問(wèn)題)某企業(yè)使用一臺(tái)設(shè)備,每年年初,企業(yè)都要作出決定,如果繼續(xù)使用舊的,要付維修費(fèi)；若購(gòu)買一臺(tái)新設(shè)備,要付購(gòu)買費(fèi).試制定一個(gè)5年更新計(jì)劃,使總支出最少.

已知設(shè)備在每年年初的購(gòu)買費(fèi)分別為11,11,12,12,13.使用不同時(shí)間設(shè)備所需的維修費(fèi)分別為5,6,8,11,18.最小生成樹(shù)華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?0(設(shè)備更新問(wèn)題)某企業(yè)使用一臺(tái)設(shè)備,每年年初35

解設(shè)bi表示設(shè)備在第i年年初的購(gòu)買費(fèi),ci表示設(shè)備使用i年后的維修費(fèi),V={v1,v2,…,v6},點(diǎn)vi表示第i年年初購(gòu)進(jìn)一臺(tái)新設(shè)備,虛設(shè)一個(gè)點(diǎn)v6表示第5年年底.E={vivj|1≤i＜j≤6}.求v1到v6的最短路問(wèn)題.最小生成樹(shù)華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地解設(shè)bi表示設(shè)備在第i年年初的購(gòu)買費(fèi),ci表36由實(shí)際問(wèn)題可知,設(shè)備使用三年后應(yīng)當(dāng)更新,因此刪除該圖中v1到v5,v1到v6,v2到v6的連線；又設(shè)備使用一年后就更新則不劃算,因此再刪除該圖中v1v2,v2v3,v3v4,v4v5,v5v6五條連線后得到從上圖中容易得到v1到v6只有兩條路：v1v3v6和v1v4v6.

而這兩條路都是v1到v6的最短路.最小生成樹(shù)華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地由實(shí)際問(wèn)題可知,設(shè)備使用三年后應(yīng)當(dāng)更新,因此刪除該圖37例11多階段存儲(chǔ)問(wèn)題某公司根據(jù)市場(chǎng)情況，預(yù)計(jì)某商品今后六個(gè)月的需要量，進(jìn)貨單價(jià)與存儲(chǔ)單價(jià)如下月份123456需要（件）607070504540單價(jià)（元）800780860860760810存儲(chǔ)月份1~22~33~44~55~6存儲(chǔ)單價(jià)4035352540若當(dāng)月訂購(gòu)當(dāng)月所需商品不附加存儲(chǔ)費(fèi)，問(wèn)如何進(jìn)貨使總費(fèi)用最小。最小生成樹(shù)華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地例11多階段存儲(chǔ)問(wèn)題某公司根據(jù)市場(chǎng)情況，預(yù)計(jì)某商品今后六38稱G=(X,Y,E)為二部圖.如果X中的每個(gè)點(diǎn)都與Y中的每個(gè)點(diǎn)鄰接,則稱G=(X,Y,E)為完備二部圖.若

F：E→R+,則稱G=(X,Y,E,F)為二部賦權(quán)圖.定義1

設(shè)X,Y都是非空有限頂點(diǎn)集,且X∩Y=Φ,二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地稱G=(X,Y,E)為二部圖.如果X中的每個(gè)點(diǎn)39定義3

若匹配M的某條邊與點(diǎn)v關(guān)聯(lián),則稱M飽和點(diǎn)v,并且稱v是M的飽和點(diǎn),否則稱v是M的非飽和點(diǎn).定義4

設(shè)M是圖G的一個(gè)匹配,如果G的每一個(gè)點(diǎn)都是M的飽和點(diǎn),則稱M是完美匹配；如果G中沒(méi)有另外的匹配M0,使

|M0|＞|M|,則稱M是最大匹配.每個(gè)完美匹配都是最大匹配,反之不一定成立.二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地定義3若匹配M的某條邊與點(diǎn)v關(guān)聯(lián),則稱M飽和定義4設(shè)M40例16：判斷下圖的匹配最大匹配非完美匹配完美匹配二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?6：判斷下圖的匹配最大匹配完美匹配二部圖的匹配及其應(yīng)用41定義5

設(shè)M是圖G的的一個(gè)匹配,其邊在E\M和M

中交錯(cuò)出現(xiàn)的路,稱為G的一條M–交錯(cuò)路.起點(diǎn)和終點(diǎn)都不是M的飽和點(diǎn)的M–交錯(cuò)路,稱為M–增廣路.定理1

G的一個(gè)匹配M是最大匹配的充要條件是G不包含M–增廣路.二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟x5設(shè)M是圖G的的一個(gè)匹配,其邊在E\M和M定理142定理2

設(shè)G=(X,Y,E)為二部圖,則①G存在飽和X的每個(gè)點(diǎn)的匹配的充要條件是對(duì)任意S

,有|N(S)|≥|S|.其中,N(S)={v|u∈S,v與u相鄰}.②G存在完美匹配的充要條件是對(duì)任意S或S有

|N(S)|≥|S|.二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟ɡ?設(shè)G=(X,Y,E)為二部圖,則①G43工作安排問(wèn)題之一給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è)問(wèn)題,對(duì)所有的工作人員能不能都分配一件他所能勝任的工作？

二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；毓ぷ靼才艈?wèn)題之一二部圖的匹配及其應(yīng)用44我們構(gòu)造一個(gè)二部圖G=(X,Y,E),這里X={x1,x2,…,xn},Y={y1,y2,…,yn},并且當(dāng)且僅當(dāng)工作人員xi勝任工作yj時(shí),xi與yj才相鄰.

于是,問(wèn)題轉(zhuǎn)化為求二部圖的一個(gè)完美匹配.因?yàn)?/p>

|X|=|Y|,所以完美匹配即為最大匹配.二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；匚覀儤?gòu)造一個(gè)二部圖G=(X,Y,E),45例17：求下圖完美匹配Hungarian算法：二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地例17：求下圖完美匹配Hungarian算法：二部圖的匹配及46例18：求下圖的最大匹配。匈亞利算法：解①取初始匹配M0={x2

y2,x3

y3,x5

y5}②給X中M0的兩個(gè)非飽和點(diǎn)x1,x4都給以標(biāo)號(hào)0和標(biāo)記*(如下圖所示).00**二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地例18：求下圖的最大匹配。匈亞利算法：解①取初始47例18：求下圖的最大匹配。匈亞利算法：00③

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

因?yàn)閥2,y3都是M0的兩個(gè)飽和點(diǎn),所以將它們?cè)贛0中鄰接的兩個(gè)點(diǎn)x2,x3都給以相應(yīng)的標(biāo)號(hào)和標(biāo)記*.**11*23*二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?8：求下圖的最大匹配。匈亞利算法：00③去掉x48例18：求下圖的最大匹配。匈亞利算法：00*11*23*④

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

222二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?8：求下圖的最大匹配。匈亞利算法：00*11*23*49例18：求下圖的最大匹配。匈亞利算法：00*1123*222⑤

因?yàn)閥1是M0的非飽和點(diǎn),逆向返回,直到x1為0為止.于是得到M0的增廣路x1y2x2y1,記P={x1y2,y2x2,x2y1}.取M1=M0⊕P={x1y2,x2y1,x3

y3,x5

y5},則M1是比M多一邊的匹配.二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?8：求下圖的最大匹配。匈亞利算法：00*1123*22250例18：求下圖的最大匹配。匈亞利算法：0*⑥

再給X中M1的非飽和點(diǎn)x4給以標(biāo)號(hào)0和標(biāo)記*,然后去掉x4的標(biāo)記*,將與x4鄰接的兩個(gè)點(diǎn)y2,y3都給以標(biāo)號(hào)4.44二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地例18：求下圖的最大匹配。匈亞利算法：0*⑥再給X51例18：求下圖的最大匹配。匈亞利算法：044因?yàn)閥2,y3都是M1的兩個(gè)飽和點(diǎn),所以將它們?cè)贛1中鄰接的兩個(gè)點(diǎn)x1,x3都給以相應(yīng)的標(biāo)號(hào)和標(biāo)記*.**23二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?8：求下圖的最大匹配。匈亞利算法：044因?yàn)閥252例18：求下圖的最大匹配。匈亞利算法：044**23⑦

去掉x1的標(biāo)記*,因?yàn)榕cx1鄰接的兩個(gè)點(diǎn)y2,y3都有標(biāo)號(hào)4,所以去掉x3的標(biāo)記*.而與x3鄰接的兩個(gè)點(diǎn)y2,y3也都有標(biāo)號(hào)4,此時(shí)X中所有有標(biāo)號(hào)的點(diǎn)都已去掉了標(biāo)記*(如下圖所示),因此M1是G的最大匹配.沒(méi)有完美匹配。二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?8：求下圖的最大匹配。匈亞利算法：044**2353例18：求下圖的最大匹配。匈亞利算法：注意到S={x1,x3,x4}時(shí)，N(S)={y1,y3,}所以沒(méi)有完美匹配。二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?8：求下圖的最大匹配。匈亞利算法：注意到S={x1,x354定義6

設(shè)G=(X,Y,E,F)為完備的二部賦權(quán)圖,若L：X∪Y→R+滿足：對(duì)任意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)}.定理3

設(shè)L是完備的二部賦權(quán)圖G=(X,Y,E,F)的可行點(diǎn)標(biāo)記,若M*是GL的完美匹配,則M*是G的最佳匹配.(權(quán)數(shù)最大的匹配)二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟x6設(shè)G=(X,Y,E,F)為完備的二部55工作安排問(wèn)題之二給n個(gè)工作人員x1,x2,…,xn安排n項(xiàng)工作y1,y2,…,yn.如果每個(gè)工作人員工作效率不同,要求工作分配的同時(shí)考慮總效率最高.二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；毓ぷ靼才艈?wèn)題之二二部圖的匹配及其應(yīng)用56我們構(gòu)造一個(gè)二部賦權(quán)圖G=(X,Y,E,F),這里X={x1,x2,…,xn},Y={y1,y2,…,yn},F(xi

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

則問(wèn)題轉(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é)果.二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；匚覀儤?gòu)造一個(gè)二部賦權(quán)圖G=(X,Y,E,57例19：求賦權(quán)矩陣為的完備二部賦權(quán)圖G=(X,Y,E,F)的最佳匹配?？尚许旤c(diǎn)標(biāo)號(hào)法：矩陣覆蓋法：分枝定界法：二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?9：求賦權(quán)矩陣為的完備二部賦權(quán)圖G=(X,Y,E,F)的58矩陣覆蓋法：STEP1：求等價(jià)分配矩陣。STEP2：求獨(dú)立零元，畫上框。（非同列同行的零）STEP3：最優(yōu)判別：達(dá)到n個(gè)獨(dú)立零元。停。STEP4：求覆蓋線：

1）封鎖沒(méi)有畫框零元的行，封鎖就打√；

2）在封鎖行中未畫框零元的列也封鎖；

3）在封鎖列中畫框零元的行也封鎖；

4）未封鎖行與封鎖列畫上覆蓋線。STEP5：調(diào)節(jié)分配矩陣：在未覆蓋元中選取最大元k，未覆蓋行加∣k∣，覆蓋列減∣k∣。轉(zhuǎn)STEP2.二部圖的匹配及其應(yīng)用華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地矩陣覆蓋法：STEP1：求等價(jià)分配矩陣。STEP2：求獨(dú)立零59定義1

設(shè)G=(V,E)為有向圖,在V中指定一點(diǎn)稱為發(fā)點(diǎn)(記為vs),和另一點(diǎn)稱為收點(diǎn)(記為vt),其余點(diǎn)叫做中間點(diǎn).對(duì)每一條邊vivj∈E,對(duì)應(yīng)一個(gè)非負(fù)實(shí)數(shù)Cij,稱為它的容量.這樣的G稱為容量網(wǎng)絡(luò),簡(jiǎn)稱網(wǎng)絡(luò),記作G=(V,E,C).G中任一邊vivj有流量fij,稱集合f={fij}為網(wǎng)絡(luò)G上的一個(gè)流.網(wǎng)絡(luò)流問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地定義1設(shè)G=(V,E)為有向圖60定義2

滿足下述條件的流f稱為可行流：①(容量限制條件)對(duì)每一邊vivj,有0≤fij≤Cij;②(平衡條件)對(duì)于中間點(diǎn)vk有∑fik

=∑fkj,即中間點(diǎn)vk的輸入量=輸出量.如果f是可行流,則對(duì)收、發(fā)點(diǎn)vt、vs有∑fsi

=∑fjt=Wf,即從vs點(diǎn)發(fā)出的物質(zhì)總量=vt點(diǎn)輸入的量.Wf稱為網(wǎng)絡(luò)流f的總流量.網(wǎng)絡(luò)流問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟x2滿足下述條件的流f稱為可行流：如果f是可行流,61一個(gè)可行流

f={fij},當(dāng)

fij=Cij時(shí),則稱流

f對(duì)邊vivj是飽和的;當(dāng)fij＜Cij時(shí),則稱流

f對(duì)邊是非飽和的.把fij=0的邊稱為零流邊,fij＞0的邊稱為非零流邊.若

μ為網(wǎng)絡(luò)中從vs到vt的一條鏈(有向圖中的路),定義鏈的方向是從vs到vt,邊的方向與鏈的方向相同稱為前向邊,前向邊的全體記為

μ+;邊的方向與鏈的方向相反稱為后向邊,后向邊的全體記為μˉ.最大流問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地一個(gè)可行流f={fij},當(dāng)fij=C62定義3

設(shè)f是一個(gè)可行流,μ是從vs到vt一條鏈.如果滿足①當(dāng)vivj∈μ+時(shí),0≤fij＜Cij,即μ+中的每一條邊都非飽和邊;②當(dāng)vivj∈μˉ時(shí),0＜fij≤Cij,即μˉ中的每一條邊都非零邊.則稱μ為從vs到vt的關(guān)于f

的可增廣鏈.最大流問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟x3設(shè)f是一個(gè)可行流,μ是從vs到vt一條鏈.最大流63定義4

容量網(wǎng)絡(luò)G=(V,E,C),若點(diǎn)集V被剖分為兩個(gè)非空集合S,Sc=V\S,vs,vt分屬于S,Sc.則把邊集

(S,Sc)={vivj|vivj∈E,vi∈S,vj∈Sc}稱為G的割集

.若把一割集的邊從網(wǎng)絡(luò)中去掉,則從vs到vt便不在相通,所以割集是從vs到vt的必經(jīng)之路.割集(S,Sc)中所有邊的容量之和,稱為這個(gè)割集的容量,記為C(S,Sc).最大流問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟x4容量網(wǎng)絡(luò)G=(V,E,C),若點(diǎn)集V被64定理1

設(shè)

f

為網(wǎng)絡(luò)G=(V,E,C)的任一可行流,(S,Sc)是剖分vs

,vt

的任一割集,則有Wf≤C(S,Sc).若有可行流

f和割集

(S,Sc),使得Wf=C(S,

Sc),則f一定是G的最大流,而

(S,Sc)必定是G中所有割集中容量小的一個(gè),即最小割集.例20：給出網(wǎng)絡(luò)的割。2343125最大流問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟ɡ?設(shè)f為網(wǎng)絡(luò)G=(V,E,C)的任一65定理2(最大流——最小割定理)任一個(gè)網(wǎng)絡(luò)中G中,從vs到vt的最大流的流量等于分割vs,vt的最小割的容量.推論

可行流f是最大流的充要條件是不存在從vs到vt的(關(guān)于f的)可增廣鏈.最大流問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟ɡ?(最大流——最小割定理)任一個(gè)網(wǎng)絡(luò)中G中,從vs66實(shí)際問(wèn)題中,一個(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è)為無(wú)窮大,所有原收點(diǎn)到收點(diǎn)vt邊的容量都設(shè)為無(wú)窮大.⑵網(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.最大流問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；貙?shí)際問(wèn)題中,一個(gè)網(wǎng)絡(luò)會(huì)出現(xiàn)下面兩種情況：最大流問(wèn)題w67例21：求網(wǎng)絡(luò)的最大流。３５３５４探索：?jiǎn)蜗蛘{(diào)整法：雙向調(diào)整法：Ford-Fulkerson算法最大流問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地例21：求網(wǎng)絡(luò)的最大流。３５３５４探索：?jiǎn)蜗蛘{(diào)整法：雙向調(diào)整68例22：

圖6-24表明一個(gè)網(wǎng)絡(luò)及初始可行流,每條邊上的有序數(shù)表示

(Cij,fij

).求這個(gè)網(wǎng)絡(luò)的最大流.標(biāo)號(hào)算法：最大流問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?2：圖6-24表明一個(gè)網(wǎng)絡(luò)及初始可行流,每條標(biāo)號(hào)算法69一般提法：已知網(wǎng)絡(luò)G=(V,E,C),每條邊vivj∈E除了已給容量Cij外,還給出了單位流量的費(fèi)用bij(≥0).所謂最小費(fèi)用流問(wèn)題就是求一個(gè)總流量已知的可行流f={fij}使得總費(fèi)用最小.當(dāng)要求f為最大流時(shí),此問(wèn)題即為最小費(fèi)用最大流問(wèn)題.

最小費(fèi)用流問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；匾话闾岱ǎ寒?dāng)要求f為最大流時(shí),此問(wèn)題即為最小費(fèi)用最大流問(wèn)題70例23：求下列網(wǎng)絡(luò)的最小費(fèi)用流。3,14,23,65,24,2負(fù)回路算法：迭加算法：最小費(fèi)用流問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?3：求下列網(wǎng)絡(luò)的最小費(fèi)用流。3,14,23,65,24,71

定義：一個(gè)工程由若干相互獨(dú)立的活動(dòng)組成，每個(gè)活動(dòng)稱為工序，我們用頂點(diǎn)表示工序，如果工序i完成之后工序j才能啟動(dòng),則圖中有一條有向邊(i,j),其權(quán)wi

表示工序i所需的時(shí)間。這樣得到的賦權(quán)有向圖G=（V,E）稱為PT圖。PT圖必定不存在有向回路。在PT圖中，當(dāng)起點(diǎn)與終點(diǎn)不唯一時(shí)，可增加兩個(gè)虛擬結(jié)點(diǎn)v0和vn作為新的起點(diǎn)與終點(diǎn)，v0和vn表示虛工序，與v0連接的邊的權(quán)為0，與vn連接的邊的權(quán)為原終點(diǎn)工序所需時(shí)間。PT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟x：一個(gè)工程由若干相互獨(dú)立的活動(dòng)組成，每個(gè)72例24一項(xiàng)工程由13道工序組成,所需時(shí)間(單位：天)及先行工序如下表所示(P172).工序序號(hào)ABCDEFGHIJKLM所需時(shí)間2632438423256先行工序-A

A

B

C,D

D

D

D

G,H

G

H,E

J

K

試問(wèn)這項(xiàng)工程至少需要多少天才能完成?那些工程不能延誤?那些工程可以延誤?最多可延誤多少天?PT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?4一項(xiàng)工程由13道工序組成,所需時(shí)間(單位：73工序序號(hào)ABCDEFGHIJKLM所需時(shí)間

2632438423256先行工序

-A

A

B

C,D

D

D

D

G,H

G

H,E

J

K

先作出該工程的PT圖.AB22C6D3E2F2G2H2K4N3I8J8442L3M256虛擬結(jié)點(diǎn)PT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地工序序號(hào)ABCDEFGHIJ74這項(xiàng)工程至少需要多少天才能完成?就是要求A到N的最長(zhǎng)路,此路徑稱為關(guān)鍵路徑.

那些工程不能延誤?那些工程可以延誤?最多可延誤多少天?關(guān)鍵路徑上的那些工程不能延誤.PT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地這項(xiàng)工程至少需就是要求A到N的最長(zhǎng)路,此路徑稱為關(guān)鍵路徑.75

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

j.關(guān)鍵路徑--最長(zhǎng)路算法各工序最早啟動(dòng)時(shí)間算法步驟：

①

對(duì)結(jié)點(diǎn)重新編號(hào)為u1,u2,…,un.②賦初值(u1)=0.③依次更新(uj),j=2,3,…,n.(uj)=max{(ui)+

(ui,uj)|uiuj∈E(G)}.④結(jié)束.PT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟ɡ砣粲邢驁DG中不存在有向回路,則可以將G的結(jié)點(diǎn)76此例不必重新編號(hào)，只要按字母順序即可.(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.最早啟動(dòng)時(shí)間:PT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；卮死槐刂匦戮幪?hào)，只要按字母順序即可.(A)=0,(F)77這項(xiàng)工程至少需要28天才能完成.關(guān)鍵路徑(最長(zhǎng)路徑):A→B→D→E→K→M→NA→B→D→H→K→M→N工序A,B,D,E,H,K,M不能延誤.各工序允許延誤時(shí)間t(uj)等于各工序最晚啟動(dòng)時(shí)間(uj)減去各工序最早啟動(dòng)時(shí)間(uj).

即

t(uj)=(uj)-(uj).PT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；剡@項(xiàng)工程至少需要28天才能完成.工序A,B,D,E,78最晚啟動(dòng)時(shí)間算法步驟(已知結(jié)點(diǎn)重新編號(hào))：

①賦初值(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)鍵路徑上.PT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；刈钔韱?dòng)時(shí)間算法步驟(已知結(jié)點(diǎn)重新編號(hào))：①賦初值79(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.最晚啟動(dòng)時(shí)間:PT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地(N)=28,(K)=(M)-8=14,(J)=(80各工序允許延誤時(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.PT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；馗鞴ば蛟试S延誤時(shí)間如下：t(A)=t(B)=t(D)=t(E81定義：一個(gè)工程由若干相互獨(dú)立的活動(dòng)組成，每個(gè)活動(dòng)稱為工序，相鄰兩個(gè)工序在時(shí)間上的分界點(diǎn)稱為事項(xiàng)，它表示緊前工序的結(jié)束和緊后工序的開(kāi)始，我們用頂點(diǎn)表示事項(xiàng)，用有向邊表示工序。邊的起點(diǎn)稱為該工序的開(kāi)工事項(xiàng)，終點(diǎn)稱為完工事項(xiàng)，用一個(gè)頂點(diǎn)表示整個(gè)工程計(jì)劃的開(kāi)始，稱為起點(diǎn)事項(xiàng)，用另一個(gè)頂點(diǎn)表示整個(gè)工程計(jì)劃的結(jié)束，稱為終點(diǎn)事項(xiàng)。這樣得到的賦權(quán)有向圖G=（V,E）稱為PERT圖。PERT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟x：一個(gè)工程由若干相互獨(dú)立的活動(dòng)組成，每PERT圖www.82圖中不能有有向圈與平行邊?？梢霗?quán)為零的虛工序表示工序的銜接關(guān)系。(3)可引入起點(diǎn)事項(xiàng)和終點(diǎn)事項(xiàng)與相應(yīng)的虛工序。ABCA1B1A2B2(1)A,B完成后C才能開(kāi)始(2)工序B在工序A部分完工后即可開(kāi)工(分解為幾個(gè)子工序)PERT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；貓D中不能有有向圈與平行邊?？梢霗?quán)為零的虛工序表示工序的銜接83事項(xiàng)vk的最早啟動(dòng)時(shí)間：表示在整個(gè)工程開(kāi)始后，在以vk為完工事項(xiàng)的所有工序如期完成的條件下，事項(xiàng)vk的最早執(zhí)行時(shí)間。事項(xiàng)vk的最遲啟動(dòng)時(shí)間：表示在不誤總工期的條件下，以vk為開(kāi)工事項(xiàng)所有工序如期開(kāi)工，事項(xiàng)vk的最遲執(zhí)行時(shí)間，PERT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；厥马?xiàng)vk的最早啟動(dòng)時(shí)間：表示在整個(gè)工程開(kāi)始后，在以vk為完工84事項(xiàng)最早最遲時(shí)間遞推公式：PERT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；厥马?xiàng)最早最遲時(shí)間遞推公式：PERT圖85例25：已知工序，工序時(shí)間與緊前工序如表，畫出工程網(wǎng)絡(luò)圖，并求事項(xiàng)的最早時(shí)間與最遲時(shí)間。工序ABCDEFGHIJK工序時(shí)間247310243232緊前工序/AAABC,D,KE,FDHG,IBPERT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地例25：已知工序，工序時(shí)間與緊前工序如表，畫工序ABCDEF86STEP1:給工序分級(jí),逐步去掉緊前工序后沒(méi)有緊前工序的作為1級(jí).級(jí)123456工序AB,C,DE,H,KF,IGJSTEP2:按工序級(jí)別從左到右排列按工序順序畫網(wǎng)絡(luò)圖.STEP3:從左到右對(duì)事項(xiàng)進(jìn)行編號(hào).PERT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；豐TEP1:給工序分級(jí),逐步去掉緊前工序后沒(méi)有緊前級(jí)123487123456789A2B4C7D3K2E10F23HG42IJ3PERT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；?23456789A2B4C7D3K2E10F23HG42I88工序的最早開(kāi)始時(shí)間：工序的最早結(jié)束時(shí)間：工序的最遲開(kāi)始時(shí)間：工序的最遲結(jié)束時(shí)間：PERT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地工序的最早開(kāi)始時(shí)間：工序的最早結(jié)束時(shí)間：工序的最遲開(kāi)始時(shí)間：89工序允許延誤時(shí)間：總時(shí)差：是在不誤總工期的條件下，工序的開(kāi)工時(shí)間可以推遲的最長(zhǎng)時(shí)間。局部時(shí)差：是在不誤所有緊后工序的最早開(kāi)工時(shí)間條件下，工序的開(kāi)工時(shí)間可以推遲的最長(zhǎng)時(shí)間。PERT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地工序允許延誤時(shí)間：總時(shí)差：是在不誤總工期的條件下，工序的開(kāi)工90關(guān)鍵路徑：從起點(diǎn)事項(xiàng)到終點(diǎn)事項(xiàng)的最長(zhǎng)路。關(guān)鍵路徑可能不止一條。PERT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；仃P(guān)鍵路徑：從起點(diǎn)事項(xiàng)到終點(diǎn)事項(xiàng)的最長(zhǎng)路。關(guān)鍵路徑可能不止一條91例26：求出上題的一些基本參數(shù)，并確定關(guān)鍵路徑。265916820232320181614146200PERT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?6：求出上題的一些基本參數(shù)，并確定關(guān)鍵26591682092工序的最早開(kāi)始時(shí)間：工序的最早結(jié)束時(shí)間：工序的最遲開(kāi)始時(shí)間：工序的最遲結(jié)束時(shí)間：總時(shí)差:局部時(shí)差：事項(xiàng)最早最遲時(shí)間:PERT圖華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地工序的最早開(kāi)始時(shí)間：工序的最早結(jié)束時(shí)間：工序的最遲開(kāi)始時(shí)間：93①若E=?,停.否則取u∈V,使d(u)=max{d(v)|v∈V}例26：假設(shè)v1,v2,…,v7是7個(gè)哨所,監(jiān)視著11條路段(如圖所示),為節(jié)省人力,問(wèn)至少需要在幾個(gè)哨所派人站崗,就可以監(jiān)視全部路段?啟發(fā)式算法：②令K=K∪{u},G=G\{u},轉(zhuǎn)向①系統(tǒng)監(jiān)控問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；丌偃鬍=?,停.否則取u∈V,例26：假設(shè)v1,94例27：假設(shè)下圖代表一指揮系統(tǒng),頂點(diǎn)v1,v2,…,

v7表示被指揮的單位,邊表示可以直接下達(dá)命令的通信線路.欲在某些單位建立指揮站,以便可以通過(guò)指揮站直接給各單位下達(dá)命令,問(wèn)至少需要建立幾個(gè)指揮站?啟發(fā)式算法：①若V=f,停.否則取u∈V,使d(u)=max{d(v)|v∈V}②令D=D∪{u},G=G\{u,N(u)},轉(zhuǎn)向①.系統(tǒng)監(jiān)控問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?7：假設(shè)下圖代表一指揮系統(tǒng),頂點(diǎn)v1,v2,…,95例28給相鄰頂點(diǎn)著上不同的顏色.要求顏色數(shù)目最小.定理:色數(shù)≤maxd(v)+1近似算法:著色問(wèn)題華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地例28給相鄰頂點(diǎn)著上不同定理:色數(shù)≤maxd(v)+196ThankYou!ThankYou!數(shù)學(xué)建模

圖論方法專題數(shù)學(xué)建模圖論方法專題專題板塊系列概率統(tǒng)計(jì)專題1優(yōu)化專題2模糊方法及微分方程專題3圖論方法專題4華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；貙ｎ}板塊系列概率統(tǒng)計(jì)專題1優(yōu)化專題2模糊方法及微分方程專題399圖論方法專題一圖論的基本概念二最短路與最小生成樹(shù)三二部圖的匹配四網(wǎng)絡(luò)流華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地圖論方法專題一圖論的基本概念二最短路與最小生成樹(shù)三二部圖的匹100ABCD哥尼斯堡七橋示意圖問(wèn)題1:七橋問(wèn)題能否從任一陸地出發(fā)通過(guò)每座橋恰好一次而回到出發(fā)點(diǎn)？圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；谹BCD哥尼斯堡七橋示意圖問(wèn)題1:七橋問(wèn)題圖論的基本概念ww101七橋問(wèn)題模擬圖:ABDC歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過(guò)每座橋恰好一次而回到出發(fā)地。圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；仄邩騿?wèn)題模擬圖:ABDC歐拉指出：如果每塊陸地所連接的橋都是102問(wèn)題2:哈密頓圈（環(huán)球旅行游戲）十二面體的20個(gè)頂點(diǎn)代表世界上20個(gè)城市，能否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過(guò)每個(gè)城市恰好一次最后回到出發(fā)點(diǎn)？圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地問(wèn)題2:哈密頓圈（環(huán)球旅行游戲）圖論的基本概念www.shu103問(wèn)題3:四色問(wèn)題對(duì)任何一張地圖進(jìn)行著色，兩個(gè)共同邊界的國(guó)家染不同的顏色，則只需要四種顏色就夠了。德·摩爾根致哈密頓的信（1852年10月23日）

我的一位學(xué)生今天請(qǐng)我解釋一個(gè)我過(guò)去不知道，現(xiàn)在仍不甚了了的事實(shí)。他說(shuō)如果任意劃分一個(gè)圖形并給各部分著上顏色，使任何具有公共邊界的部分顏色不同，那么需要且僅需要四種顏色就夠了。下圖是需要四種顏色的例子（圖1）?！瓐D論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地問(wèn)題3:四色問(wèn)題對(duì)任何一張地圖進(jìn)行著色，兩個(gè)共同104問(wèn)題4(關(guān)鍵路徑問(wèn)題):

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

這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間才能夠完成整個(gè)工程項(xiàng)目,影響工程進(jìn)度的要害工序是哪幾個(gè)？圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；貑?wèn)題4(關(guān)鍵路徑問(wèn)題):圖論的基本概念www.shumo.c105定義1一個(gè)有序二元組(V,E)稱為一個(gè)圖,記為G=(V,E),其中①V或V(G)稱為G的頂點(diǎn)集,V≠Φ,其元素稱為頂點(diǎn)或結(jié)點(diǎn),簡(jiǎn)稱點(diǎn);②

E或E(G)稱為G的邊集,其元素稱為邊,它聯(lián)結(jié)V中的兩個(gè)點(diǎn),如果這兩個(gè)點(diǎn)是無(wú)序的,則稱該邊為無(wú)向邊,否則,稱為有向邊.圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地定義1一個(gè)有序二元組(V,E)稱為一個(gè)圖,記為圖106如果V={v1,v2,…,vn}是有限非空點(diǎn)集,則稱G為有限圖或n階圖.如果E的每一條邊都是無(wú)向邊,則稱G為無(wú)向圖;如果E的每一條邊都是有向邊,則稱G為有向圖;否則,稱G為混合圖.記E={e1,e2,…,em}(ek

=vivj).圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；厝绻鸙={v1,v2,…,vn}是有限非空點(diǎn)集,107對(duì)于一個(gè)圖G=(V,E),人們常用圖形來(lái)表示它,稱其為圖解.凡是有向邊,在圖解上都用箭頭標(biāo)明其方向.稱點(diǎn)vi,vj為邊vivj的端點(diǎn).有邊聯(lián)結(jié)的兩個(gè)點(diǎn)稱為相鄰頂點(diǎn),有一個(gè)公共端點(diǎn)的邊稱為相鄰邊.邊和它的端點(diǎn)稱為互相關(guān)聯(lián).有向圖中的關(guān)聯(lián)又分出關(guān)聯(lián)和入關(guān)聯(lián)。圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；貙?duì)于一個(gè)圖G=(V,E),人們常用圖形來(lái)表示它,108常用d(v)表示圖G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目,

d(v)稱為頂點(diǎn)v的度數(shù).與頂點(diǎn)v出關(guān)聯(lián)的邊的數(shù)目稱為出度，記作d

+(v),與頂點(diǎn)v入關(guān)聯(lián)的邊的數(shù)目稱為入度，記作d

-(v)。用N(v)表示圖G中所有與頂點(diǎn)v相鄰的頂點(diǎn)的集合.圖論的基本概念任意兩頂點(diǎn)都相臨的簡(jiǎn)單圖稱為完全圖.有n個(gè)頂點(diǎn)的完全圖記為K

n。華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；爻Ｓ胐(v)表示圖G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目,用N(v109幾個(gè)基本定理：圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；貛讉€(gè)基本定理：圖論的基本概念華中農(nóng)業(yè)110用圖論思想求解以下各題例1、一擺渡人欲將一只狼，一頭羊，一籃菜從河西渡過(guò)河到河?xùn)|，由于船小，一次只能帶一物過(guò)河，并且，狼與羊，羊與菜不能獨(dú)處，給出渡河方法。圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；赜脠D論思想求解以下各題例1、一擺渡人欲將一只狼，一頭羊，一籃111解：用四維0-1向量表示（人，狼，羊，菜）的在西岸狀態(tài)，（在西岸則分量取1，否則取0.）共24=16種狀態(tài)，由題設(shè)，狀態(tài)（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允許的，從而對(duì)應(yīng)狀態(tài)（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允許的，圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；亟猓河盟木S0-1向量表示（人，狼，羊，菜）的在西岸共24=1112人在河西：（1,1,1,1）（1,1,1,0）（1,1,0,1）（1,0,1,1）（1,0,1,0）（0,1,0,1）（0,1,0,0）（0,0,1,0）（0,0,0,1）（0,0,0,0）人在河?xùn)|：以十個(gè)向量作為頂點(diǎn)，將可能互相轉(zhuǎn)移的狀態(tài)連線，則得10個(gè)頂點(diǎn)的偶圖。問(wèn)題：如何從狀態(tài)（1,1,1,1）轉(zhuǎn)移到（0,0,0,0）？方法：從（1,1,1,1）開(kāi)始，沿關(guān)聯(lián)邊到達(dá)沒(méi)有到達(dá)的相鄰頂點(diǎn)，到（0,0,0,0）終止，得到有向圖即是。圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；厝嗽诤游鳎海?,1,1,1）（1,1,1,0）（1,1,0,113例2、考慮中國(guó)象棋的如下問(wèn)題：（1）下過(guò)奇數(shù)盤棋的人數(shù)是偶數(shù)個(gè)。（2）馬有多少種跳法？（3）馬跳出后又跳回起點(diǎn)，證明馬跳了偶數(shù)步。（4）紅方的馬能不能在自己一方的棋盤上不重復(fù)的跳遍每一點(diǎn)，最后跳回起點(diǎn)？圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?、考慮中國(guó)象棋的如下問(wèn)題：圖論的基本概念www.shum114例3、證明：在任意6人的集會(huì)上，總有3人互相認(rèn)識(shí)，或總有3人互相不認(rèn)識(shí)。解：以頂點(diǎn)表示人，以邊表示認(rèn)識(shí)，得6個(gè)頂點(diǎn)的簡(jiǎn)單圖G。問(wèn)題：3人互相認(rèn)識(shí)即G包含K3為子圖，3人互相不認(rèn)識(shí)即G包含（3,0）圖為子圖。圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?、證明：在任意6人的集會(huì)上，總有3人互相認(rèn)解：以頂點(diǎn)表示115圖論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；貓D論的基本概念華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基116定義2若將圖G的每一條邊e都對(duì)應(yīng)一個(gè)實(shí)數(shù)F(e),則稱F(e)為該邊的權(quán),并稱圖G為賦權(quán)圖(網(wǎng)絡(luò)),記為G=(V,E,F).定義3設(shè)G=(V,E)是一個(gè)圖,v0,v1,…,vk∈V,且“1≤i≤k,vi－1vi∈E,則稱v0v1…

vk是G的一條通路.圖論的基本概念

如果通路中沒(méi)有相同的頂點(diǎn),則稱此通路為路徑,簡(jiǎn)稱路.始點(diǎn)和終點(diǎn)相同的路稱為圈或回路.華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟x2若將圖G的每一條邊e都對(duì)應(yīng)一個(gè)實(shí)數(shù)F(e),則稱117定義4頂點(diǎn)u與v稱為連通的，如果存在u-v通路，任二頂點(diǎn)都連通的圖稱為連通圖，否則，稱為不連通圖。極大連通子圖稱為連通支。圖論的基本概念定義5連通而無(wú)圈的圖稱為樹(shù),常用T表示樹(shù).樹(shù)中最長(zhǎng)路的長(zhǎng)稱為樹(shù)的高。樹(shù)的度為1的頂點(diǎn)稱為樹(shù)葉。其余的頂點(diǎn)稱為分枝點(diǎn)。樹(shù)的邊稱為樹(shù)枝。設(shè)G是有向圖，如果G的基礎(chǔ)圖是樹(shù)，則稱G是有向樹(shù)，也簡(jiǎn)稱樹(shù)。華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟x4頂點(diǎn)u與v稱為連通的，如果存在u-v通路，任二頂點(diǎn)都118⑴

鄰接矩陣

A=(aij)n×n,例4：寫出右圖的鄰接矩陣：解：圖的矩陣表示華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地⑴鄰接矩陣A=(aij)n×n,例4：寫出右圖119⑵權(quán)矩陣A=(aij)n×n例5：寫出右圖的權(quán)矩陣：解：圖的矩陣表示華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；丌茩?quán)矩陣A=(aij)n×n例5：寫出右圖的權(quán)矩120⑶

關(guān)聯(lián)矩陣A=(aij)n×m

有向圖：無(wú)向圖：圖的矩陣表示華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地⑶關(guān)聯(lián)矩陣A=(aij)n×m

有向圖：無(wú)向圖：121例6：寫出右圖與其基本圖的關(guān)聯(lián)矩陣解：分別為：圖的矩陣表示華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?：寫出右圖與其基本圖解：分別為：圖的矩陣表示www.sh122定義1

設(shè)

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

若P0(u,v)是G

中連接u,v的路徑,且對(duì)任意在G

中連接u,v的路徑P(u,v)都有F(P0

)≤F(P),則稱P0(u,v)是G

中連接u,v的最短路.最短路華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；囟x1設(shè)P(u,v)是賦權(quán)圖G=(V,E123重要性質(zhì)：若v0v1…

vm是G中從v0到vm的最短路,則對(duì)1≤k≤m,v0v1…

vk必為G中從v0到vk的最短路.即：最短路是一條路，且最短路的任一段也是最短路。最短路華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建模基地重要性質(zhì)：若v0v1…vm是G中從v0到vm的最短路124例7對(duì)下面的有向圖求頂點(diǎn)v0到其余頂點(diǎn)的最短路。1445642537最短路華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；乩?對(duì)下面的有向圖求頂點(diǎn)v0到其余頂點(diǎn)ijkstra算法：求某一頂點(diǎn)到其余頂點(diǎn)的最短路最短路華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；谼ijkstra算法：求某一頂點(diǎn)到其余頂點(diǎn)的最短路最短路ww12668－523－374例8：求下列任意兩點(diǎn)的最短路和距離。最短路華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；?8－523－374例8：求下列任意兩點(diǎn)的最短路和距離。最短127Floyd算法:求任意兩頂點(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)的編號(hào).

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

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

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

最短路線可由rij得到.最短路華中農(nóng)業(yè)大學(xué)數(shù)學(xué)建?；谾loyd算法:求任意兩頂點(diǎn)的最短路設(shè)A=(ai128求非負(fù)賦權(quán)圖G中某一點(diǎn)到其它各點(diǎn)最短路，一般用Dijkstra標(biāo)號(hào)算法；

Dijkstra標(biāo)號(hào)算法只適用于全部權(quán)為非負(fù)情況。求非負(fù)賦權(quán)圖上任意兩點(diǎn)間的最短路，一般用Floyd算法.Floyd算法可以適用于有負(fù)權(quán)的情況，還能判斷是否有負(fù)回路。這兩種算法均適用