數學建模圖論課件

數學建模

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

我的一位學生今天請我解釋一個我過去不知道，現在仍不甚了了的事實。他說如果任意劃分一個圖形并給各部分著上顏色，使任何具有公共邊界的部分顏色不同，那么需要且僅需要四種顏色就夠了。下圖是需要四種顏色的例子（圖1）?！瓐D論的基本概念華中農業(yè)大學數學建?；貑栴}3:四色問題對任何一張地圖進行著色，兩個共同7問題4(關鍵路徑問題):

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

這時工程領導人員迫切希望了解最少需要多少時間才能夠完成整個工程項目,影響工程進度的要害工序是哪幾個？圖論的基本概念華中農業(yè)大學數學建?；貑栴}4(關鍵路徑問題):圖論的基本概念www.shumo.c8定義1一個有序二元組(V,E)稱為一個圖,記為G=(V,E),其中①V或V(G)稱為G的頂點集,V≠Φ,其元素稱為頂點或結點,簡稱點;②

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

=vivj).圖論的基本概念華中農業(yè)大學數學建?；厝绻鸙={v1,v2,…,vn}是有限非空點集,10對于一個圖G=(V,E),人們常用圖形來表示它,稱其為圖解.凡是有向邊,在圖解上都用箭頭標明其方向.稱點vi,vj為邊vivj的端點.有邊聯結的兩個點稱為相鄰頂點,有一個公共端點的邊稱為相鄰邊.邊和它的端點稱為互相關聯.有向圖中的關聯又分出關聯和入關聯。圖論的基本概念華中農業(yè)大學數學建?；貙τ谝粋€圖G=(V,E),人們常用圖形來表示它,11常用d(v)表示圖G中與頂點v關聯的邊的數目,

d(v)稱為頂點v的度數.與頂點v出關聯的邊的數目稱為出度，記作d

+(v),與頂點v入關聯的邊的數目稱為入度，記作d

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

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

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

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

鄰接矩陣

A=(aij)n×n,例4：寫出右圖的鄰接矩陣：解：圖的矩陣表示華中農業(yè)大學數學建?；丌培徑泳仃嘇=(aij)n×n,例4：寫出右圖22⑵權矩陣A=(aij)n×n例5：寫出右圖的權矩陣：解：圖的矩陣表示華中農業(yè)大學數學建?；丌茩嗑仃嘇=(aij)n×n例5：寫出右圖的權矩23⑶

關聯矩陣A=(aij)n×m

有向圖：無向圖：圖的矩陣表示華中農業(yè)大學數學建模基地⑶關聯矩陣A=(aij)n×m

有向圖：無向圖：24例6：寫出右圖與其基本圖的關聯矩陣解：分別為：圖的矩陣表示華中農業(yè)大學數學建?；乩?：寫出右圖與其基本圖解：分別為：圖的矩陣表示www.sh25定義1

設

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

若P0(u,v)是G

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

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

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

中連接u,v的最短路.最短路華中農業(yè)大學數學建?；囟x1設P(u,v)是賦權圖G=(V,E26重要性質：若v0v1…

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

vk必為G中從v0到vk的最短路.即：最短路是一條路，且最短路的任一段也是最短路。最短路華中農業(yè)大學數學建模基地重要性質：若v0v1…vm是G中從v0到vm的最短路27例7對下面的有向圖求頂點v0到其余頂點的最短路。1445642537最短路華中農業(yè)大學數學建?；乩?對下面的有向圖求頂點v0到其余頂點的1445642528Dijkstra算法：求某一頂點到其余頂點的最短路最短路華中農業(yè)大學數學建?；谼ijkstra算法：求某一頂點到其余頂點的最短路最短路ww2968－523－374例8：求下列任意兩點的最短路和距離。最短路華中農業(yè)大學數學建?；?8－523－374例8：求下列任意兩點的最短路和距離。最短30Floyd算法:求任意兩頂點的最短路設A=(aij)n×n為賦權圖G=(V,E,F)的權矩陣,dij表示從vi到vj點的距離,rij表示從vi到vj點的最短路中一個點的編號.

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

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

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

最短路線可由rij得到.最短路華中農業(yè)大學數學建?；谾loyd算法:求任意兩頂點的最短路設A=(ai31求非負賦權圖G中某一點到其它各點最短路，一般用Dijkstra標號算法；

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

已知設備在每年年初的購買費分別為11,11,12,12,13.使用不同時間設備所需的維修費分別為5,6,8,11,18.最小生成樹華中農業(yè)大學數學建模基地例10(設備更新問題)某企業(yè)使用一臺設備,每年年初35

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

而這兩條路都是v1到v6的最短路.最小生成樹華中農業(yè)大學數學建?；赜蓪嶋H問題可知,設備使用三年后應當更新,因此刪除該圖37例11多階段存儲問題某公司根據市場情況，預計某商品今后六個月的需要量，進貨單價與存儲單價如下月份123456需要（件）607070504540單價（元）800780860860760810存儲月份1~22~33~44~55~6存儲單價4035352540若當月訂購當月所需商品不附加存儲費，問如何進貨使總費用最小。最小生成樹華中農業(yè)大學數學建?；乩?1多階段存儲問題某公司根據市場情況，預計某商品今后六38稱G=(X,Y,E)為二部圖.如果X中的每個點都與Y中的每個點鄰接,則稱G=(X,Y,E)為完備二部圖.若

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

設X,Y都是非空有限頂點集,且X∩Y=Φ,二部圖的匹配及其應用華中農業(yè)大學數學建?；胤QG=(X,Y,E)為二部圖.如果X中的每個點39定義3

若匹配M的某條邊與點v關聯,則稱M飽和點v,并且稱v是M的飽和點,否則稱v是M的非飽和點.定義4

設M是圖G的一個匹配,如果G的每一個點都是M的飽和點,則稱M是完美匹配；如果G中沒有另外的匹配M0,使

|M0|＞|M|,則稱M是最大匹配.每個完美匹配都是最大匹配,反之不一定成立.二部圖的匹配及其應用華中農業(yè)大學數學建?；囟x3若匹配M的某條邊與點v關聯,則稱M飽和定義4設M40例16：判斷下圖的匹配最大匹配非完美匹配完美匹配二部圖的匹配及其應用華中農業(yè)大學數學建模基地例16：判斷下圖的匹配最大匹配完美匹配二部圖的匹配及其應用41定義5

設M是圖G的的一個匹配,其邊在E\M和M

中交錯出現的路,稱為G的一條M–交錯路.起點和終點都不是M的飽和點的M–交錯路,稱為M–增廣路.定理1

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

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

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

|N(S)|≥|S|.二部圖的匹配及其應用華中農業(yè)大學數學建?；囟ɡ?設G=(X,Y,E)為二部圖,則①G43工作安排問題之一給n個工作人員x1,x2,…,xn安排n項工作y1,y2,…,yn.n個工作人員中每個人能勝任一項或幾項工作,但并不是所有工作人員都能從事任何一項工作.比如x1能做y1,y2工作,x2能做y2,y3,y4工作等.

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

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

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

|X|=|Y|,所以完美匹配即為最大匹配.二部圖的匹配及其應用華中農業(yè)大學數學建?；匚覀儤嬙煲粋€二部圖G=(X,Y,E),45例17：求下圖完美匹配Hungarian算法：二部圖的匹配及其應用華中農業(yè)大學數學建模基地例17：求下圖完美匹配Hungarian算法：二部圖的匹配及46例18：求下圖的最大匹配。匈亞利算法：解①取初始匹配M0={x2

y2,x3

y3,x5

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

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

因為y2,y3都是M0的兩個飽和點,所以將它們在M0中鄰接的兩個點x2,x3都給以相應的標號和標記*.**11*23*二部圖的匹配及其應用華中農業(yè)大學數學建模基地例18：求下圖的最大匹配。匈亞利算法：00③去掉x48例18：求下圖的最大匹配。匈亞利算法：00*11*23*④

去掉x2的標記*,將與x2鄰接且尚未給標號的三個點y1,y4,y5都給以標號2.

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

因為y1是M0的非飽和點,逆向返回,直到x1為0為止.于是得到M0的增廣路x1y2x2y1,記P={x1y2,y2x2,x2y1}.取M1=M0⊕P={x1y2,x2y1,x3

y3,x5

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

再給X中M1的非飽和點x4給以標號0和標記*,然后去掉x4的標記*,將與x4鄰接的兩個點y2,y3都給以標號4.44二部圖的匹配及其應用華中農業(yè)大學數學建?；乩?8：求下圖的最大匹配。匈亞利算法：0*⑥再給X51例18：求下圖的最大匹配。匈亞利算法：044因為y2,y3都是M1的兩個飽和點,所以將它們在M1中鄰接的兩個點x1,x3都給以相應的標號和標記*.**23二部圖的匹配及其應用華中農業(yè)大學數學建?；乩?8：求下圖的最大匹配。匈亞利算法：044因為y252例18：求下圖的最大匹配。匈亞利算法：044**23⑦

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

設G=(X,Y,E,F)為完備的二部賦權圖,若L：X∪Y→R+滿足：對任意x∈X,y∈Y,L(x)+L(y)≥F(xy),則稱L為G的一個可行點標記,記相應的生成子圖為GL=(X,Y,EL

,F),這里EL

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

設L是完備的二部賦權圖G=(X,Y,E,F)的可行點標記,若M*是GL的完美匹配,則M*是G的最佳匹配.(權數最大的匹配)二部圖的匹配及其應用華中農業(yè)大學數學建模基地定義6設G=(X,Y,E,F)為完備的二部55工作安排問題之二給n個工作人員x1,x2,…,xn安排n項工作y1,y2,…,yn.如果每個工作人員工作效率不同,要求工作分配的同時考慮總效率最高.二部圖的匹配及其應用華中農業(yè)大學數學建?；毓ぷ靼才艈栴}之二二部圖的匹配及其應用56我們構造一個二部賦權圖G=(X,Y,E,F),這里X={x1,x2,…,xn},Y={y1,y2,…,yn},F(xi

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

則問題轉化為：求二部賦權圖G的最佳匹配.

在求G

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

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

轉化為完備二部賦權圖,而且不會影響結果.二部圖的匹配及其應用華中農業(yè)大學數學建?；匚覀儤嬙煲粋€二部賦權圖G=(X,Y,E,57例19：求賦權矩陣為的完備二部賦權圖G=(X,Y,E,F)的最佳匹配?？尚许旤c標號法：矩陣覆蓋法：分枝定界法：二部圖的匹配及其應用華中農業(yè)大學數學建?；乩?9：求賦權矩陣為的完備二部賦權圖G=(X,Y,E,F)的58矩陣覆蓋法：STEP1：求等價分配矩陣。STEP2：求獨立零元，畫上框。（非同列同行的零）STEP3：最優(yōu)判別：達到n個獨立零元。停。STEP4：求覆蓋線：

1）封鎖沒有畫框零元的行，封鎖就打√；

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

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

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

設G=(V,E)為有向圖,在V中指定一點稱為發(fā)點(記為vs),和另一點稱為收點(記為vt),其余點叫做中間點.對每一條邊vivj∈E,對應一個非負實數Cij,稱為它的容量.這樣的G稱為容量網絡,簡稱網絡,記作G=(V,E,C).G中任一邊vivj有流量fij,稱集合f={fij}為網絡G上的一個流.網絡流問題華中農業(yè)大學數學建?；囟x1設G=(V,E)為有向圖60定義2

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

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

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

f={fij},當

fij=Cij時,則稱流

f對邊vivj是飽和的;當fij＜Cij時,則稱流

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

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

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

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

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

容量網絡G=(V,E,C),若點集V被剖分為兩個非空集合S,Sc=V\S,vs,vt分屬于S,Sc.則把邊集

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

.若把一割集的邊從網絡中去掉,則從vs到vt便不在相通,所以割集是從vs到vt的必經之路.割集(S,Sc)中所有邊的容量之和,稱為這個割集的容量,記為C(S,Sc).最大流問題華中農業(yè)大學數學建模基地定義4容量網絡G=(V,E,C),若點集V被64定理1

設

f

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

,vt

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

f和割集

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

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

(S,Sc)必定是G中所有割集中容量小的一個,即最小割集.例20：給出網絡的割。2343125最大流問題華中農業(yè)大學數學建模基地定理1設f為網絡G=(V,E,C)的任一65定理2(最大流——最小割定理)任一個網絡中G中,從vs到vt的最大流的流量等于分割vs,vt的最小割的容量.推論

可行流f是最大流的充要條件是不存在從vs到vt的(關于f的)可增廣鏈.最大流問題華中農業(yè)大學數學建模基地定理2(最大流——最小割定理)任一個網絡中G中,從vs66實際問題中,一個網絡會出現下面兩種情況：⑴發(fā)點和收點都不止一個.

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

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

)=Cv.最大流問題華中農業(yè)大學數學建?；貙嶋H問題中,一個網絡會出現下面兩種情況：最大流問題w67例21：求網絡的最大流。３５３５４探索：單向調整法：雙向調整法：Ford-Fulkerson算法最大流問題華中農業(yè)大學數學建?；乩?1：求網絡的最大流。３５３５４探索：單向調整法：雙向調整68例22：

圖6-24表明一個網絡及初始可行流,每條邊上的有序數表示

(Cij,fij

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

最小費用流問題華中農業(yè)大學數學建?；匾话闾岱ǎ寒斠骹為最大流時,此問題即為最小費用最大流問題70例23：求下列網絡的最小費用流。3,14,23,65,24,2負回路算法：迭加算法：最小費用流問題華中農業(yè)大學數學建?；乩?3：求下列網絡的最小費用流。3,14,23,65,24,71

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

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

A

B

C,D

D

D

D

G,H

G

H,E

J

K

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

2632438423256先行工序

-A

A

B

C,D

D

D

D

G,H

G

H,E

J

K

先作出該工程的PT圖.AB22C6D3E2F2G2H2K4N3I8J8442L3M256虛擬結點PT圖華中農業(yè)大學數學建?；毓ば蛐蛱朅BCDEFGHIJ74這項工程至少需要多少天才能完成?就是要求A到N的最長路,此路徑稱為關鍵路徑.

那些工程不能延誤?那些工程可以延誤?最多可延誤多少天?關鍵路徑上的那些工程不能延誤.PT圖華中農業(yè)大學數學建?；剡@項工程至少需就是要求A到N的最長路,此路徑稱為關鍵路徑.75

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

j.關鍵路徑--最長路算法各工序最早啟動時間算法步驟：

①

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

(ui,uj)|uiuj∈E(G)}.④結束.PT圖華中農業(yè)大學數學建模基地定理若有向圖G中不存在有向回路,則可以將G的結點76此例不必重新編號，只要按字母順序即可.(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.最早啟動時間:PT圖華中農業(yè)大學數學建?；卮死槐刂匦戮幪?，只要按字母順序即可.(A)=0,(F)77這項工程至少需要28天才能完成.關鍵路徑(最長路徑):A→B→D→E→K→M→NA→B→D→H→K→M→N工序A,B,D,E,H,K,M不能延誤.各工序允許延誤時間t(uj)等于各工序最晚啟動時間(uj)減去各工序最早啟動時間(uj).

即

t(uj)=(uj)-(uj).PT圖華中農業(yè)大學數學建?；剡@項工程至少需要28天才能完成.工序A,B,D,E,78最晚啟動時間算法步驟(已知結點重新編號)：

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

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

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

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

我的一位學生今天請我解釋一個我過去不知道，現在仍不甚了了的事實。他說如果任意劃分一個圖形并給各部分著上顏色，使任何具有公共邊界的部分顏色不同，那么需要且僅需要四種顏色就夠了。下圖是需要四種顏色的例子（圖1）。……圖論的基本概念華中農業(yè)大學數學建?；貑栴}3:四色問題對任何一張地圖進行著色，兩個共同104問題4(關鍵路徑問題):

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

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

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

=vivj).圖論的基本概念華中農業(yè)大學數學建模基地如果V={v1,v2,…,vn}是有限非空點集,107對于一個圖G=(V,E),人們常用圖形來表示它,稱其為圖解.凡是有向邊,在圖解上都用箭頭標明其方向.稱點vi,vj為邊vivj的端點.有邊聯結的兩個點稱為相鄰頂點,有一個公共端點的邊稱為相鄰邊.邊和它的端點稱為互相關聯.有向圖中的關聯又分出關聯和入關聯。圖論的基本概念華中農業(yè)大學數學建模基地對于一個圖G=(V,E),人們常用圖形來表示它,108常用d(v)表示圖G中與頂點v關聯的邊的數目,

d(v)稱為頂點v的度數.與頂點v出關聯的邊的數目稱為出度，記作d

+(v),與頂點v入關聯的邊的數目稱為入度，記作d

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

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

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

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

鄰接矩陣

A=(aij)n×n,例4：寫出右圖的鄰接矩陣：解：圖的矩陣表示華中農業(yè)大學數學建?；丌培徑泳仃嘇=(aij)n×n,例4：寫出右圖119⑵權矩陣A=(aij)n×n例5：寫出右圖的權矩陣：解：圖的矩陣表示華中農業(yè)大學數學建?；丌茩嗑仃嘇=(aij)n×n例5：寫出右圖的權矩120⑶

關聯矩陣A=(aij)n×m

有向圖：無向圖：圖的矩陣表示華中農業(yè)大學數學建?；丌顷P聯矩陣A=(aij)n×m

有向圖：無向圖：121例6：寫出右圖與其基本圖的關聯矩陣解：分別為：圖的矩陣表示華中農業(yè)大學數學建?；乩?：寫出右圖與其基本圖解：分別為：圖的矩陣表示www.sh122定義1

設

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

若P0(u,v)是G

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

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

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

中連接u,v的最短路.最短路華中農業(yè)大學數學建模基地定義1設P(u,v)是賦權圖G=(V,E123重要性質：若v0v1…

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

vk必為G中從v0到vk的最短路.即：最短路是一條路，且最短路的任一段也是最短路。最短路華中農業(yè)大學數學建?；刂匾再|：若v0v1…vm是G中從v0到vm的最短路124例7對下面的有向圖求頂點v0到其余頂點的最短路。1445642537最短路華中農業(yè)大學數學建?；乩?對下面的有向圖求頂點v0到其余頂點ijkstra算法：求某一頂點到其余頂點的最短路最短路華中農業(yè)大學數學建?；谼ijkstra算法：求某一頂點到其余頂點的最短路最短路ww12668－523－374例8：求下列任意兩點的最短路和距離。最短路華中農業(yè)大學數學建?；?8－523－374例8：求下列任意兩點的最短路和距離。最短127Floyd算法:求任意兩頂點的最短路設A=(aij)n×n為賦權圖G=(V,E,F)的權矩陣,dij表示從vi到vj點的距離,rij表示從vi到vj點的最短路中一個點的編號.

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

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

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

最短路線可由rij得到.最短路華中農業(yè)大學數學建?；谾loyd算法:求任意兩頂點的最短路設A=(ai128求非負賦權圖G中某一點到其它各點最短路，一般用Dijkstra標號算法；

Dijkstra標號算法只適用于全部權為非負情況。求非負賦權圖上任意兩點間的最短路，一般用Floyd算法.Floyd算法可以適用于有負權的情況，還能判斷是否有負回路。這兩種算法均適用