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

1、圖論方法專題圖的基本概念圖的基本概念最短路問題及其算法最短路問題及其算法最小生成樹問題最小生成樹問題E圖與圖與H圖圖圖的矩陣表示圖的矩陣表示第1頁/共86頁 22022年年2月月3日日 一、圖的基本概念一、圖的基本概念第2頁/共86頁32022年年2月月3日日 一、圖的基本概念一、圖的基本概念第3頁/共86頁 一、圖的基本概念一、圖的基本概念次數(shù)為奇數(shù)頂點(diǎn)稱為次數(shù)為奇數(shù)頂點(diǎn)稱為奇點(diǎn)奇點(diǎn)，否則稱為否則稱為偶點(diǎn)偶點(diǎn)。42022年年2月月3日日第4頁/共86頁常用常用d d( (v v) )表示圖表示圖G G中與頂點(diǎn)中與頂點(diǎn)v v關(guān)聯(lián)的邊的數(shù)目關(guān)聯(lián)的邊的數(shù)目, , d d( (v v) )稱為頂點(diǎn)稱

2、為頂點(diǎn)v v的度數(shù)的度數(shù). .與頂點(diǎn)與頂點(diǎn)v v出關(guān)聯(lián)的邊的數(shù)目稱為出關(guān)聯(lián)的邊的數(shù)目稱為出度出度，記作，記作d d + +( (v v) )，與頂點(diǎn)與頂點(diǎn)v v入關(guān)聯(lián)的邊的數(shù)目稱為入關(guān)聯(lián)的邊的數(shù)目稱為入度入度，記作，記作d d - -( (v v) )。用用N N( (v v) )表示圖表示圖G G中所有與頂點(diǎn)中所有與頂點(diǎn)v v相鄰的頂點(diǎn)的集合相鄰的頂點(diǎn)的集合. 任意兩頂點(diǎn)都相鄰的簡單圖稱為任意兩頂點(diǎn)都相鄰的簡單圖稱為完全圖完全圖. .有有n n個頂點(diǎn)的完全圖記為個頂點(diǎn)的完全圖記為K Kn n 。 一、圖的基本概念一、圖的基本概念第5頁/共86頁幾個基本定理：幾個基本定理： .21EvdEVG

3、Vv，有，、對圖數(shù)個。、度為奇數(shù)的頂點(diǎn)有偶2 . 3EvdvdEVGVvVv則是有向圖，、設(shè) 一、圖的基本概念一、圖的基本概念第6頁/共86頁 若將圖若將圖G G的每一條邊的每一條邊e e都對應(yīng)一個實(shí)數(shù)都對應(yīng)一個實(shí)數(shù)F F( (e e) ), , 則稱則稱F F( (e e) )為該邊的為該邊的權(quán)權(quán), , 并稱圖并稱圖G G為為賦權(quán)圖賦權(quán)圖, , 記為記為G G = ( = (V V, , E E , , F F ) ). . 設(shè)設(shè)G G = ( = (V V, , E E ) )是一個圖是一個圖, , v v0 0, , v v1 1, , , , v vk kV V, , 且且“11i i

4、k k, , v vi i1 1 v vi iE E, , 則稱則稱v v0 0 v v1 1 v vk k是是G G的一條的一條通路通路. . 如果通路中沒有相同的頂點(diǎn)如果通路中沒有相同的頂點(diǎn), , 則稱此通路為則稱此通路為路徑路徑, , 簡稱簡稱路路. . 始點(diǎn)和終點(diǎn)相同的路稱為始點(diǎn)和終點(diǎn)相同的路稱為圈圈或或回路回路. . 一、圖的基本概念一、圖的基本概念第7頁/共86頁 頂點(diǎn)頂點(diǎn)u u與與v v稱為稱為連通連通的，如果存在的，如果存在u u到到v v通路，任二頂通路，任二頂點(diǎn)都連通的圖稱為點(diǎn)都連通的圖稱為連通圖連通圖，否則，稱為，否則，稱為非連通圖非連通圖。極大。極大連通子圖稱為連通子圖

5、稱為連通分圖連通分圖。 連通而無圈的圖稱為連通而無圈的圖稱為樹樹, , 常用常用T T 表示樹表示樹. . 樹中最長路的邊數(shù)稱為樹的樹中最長路的邊數(shù)稱為樹的高，高，度數(shù)為度數(shù)為1 1的頂點(diǎn)的頂點(diǎn)稱為稱為樹葉樹葉。其余的頂點(diǎn)稱為。其余的頂點(diǎn)稱為分枝點(diǎn)分枝點(diǎn)。樹的邊稱為。樹的邊稱為樹樹枝枝。 設(shè)設(shè)G G是有向圖，如果是有向圖，如果G G的底圖是樹，則稱的底圖是樹，則稱G G是是有向樹有向樹，也簡稱，也簡稱樹樹。 一、圖的基本概念一、圖的基本概念第8頁/共86頁鄰接矩陣（結(jié)點(diǎn)與結(jié)點(diǎn)的關(guān)系）鄰接矩陣（結(jié)點(diǎn)與結(jié)點(diǎn)的關(guān)系）關(guān)聯(lián)矩陣（結(jié)點(diǎn)與邊的關(guān)系）關(guān)聯(lián)矩陣（結(jié)點(diǎn)與邊的關(guān)系）路徑矩陣（任意兩結(jié)點(diǎn)之間是否有路

6、徑）路徑矩陣（任意兩結(jié)點(diǎn)之間是否有路徑）可達(dá)性矩陣可達(dá)性矩陣直達(dá)矩陣直達(dá)矩陣 等等等等二、圖的矩陣表示二、圖的矩陣表示第9頁/共86頁1 1 有向圖的鄰接矩陣有向圖的鄰接矩陣 A = (aij )nn （n為結(jié)點(diǎn)數(shù)）EvvEvvajijiij, 0, 1 例例1 1：寫出右圖的鄰接矩陣：寫出右圖的鄰接矩陣：0101100101001010A解：二、圖的矩陣表示二、圖的矩陣表示第10頁/共86頁2 2 有向圖的權(quán)矩陣有向圖的權(quán)矩陣A = (aij ) nn （n為結(jié)點(diǎn)數(shù)） EvvjiEvvvvFajijijiij , , 0 ,例2：寫出右圖的權(quán)矩陣：05420370860A解：二、圖的矩陣表示

7、二、圖的矩陣表示第11頁/共86頁3 有向圖的有向圖的關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣A A =(aij )nm （n為結(jié)點(diǎn)數(shù)m為邊數(shù)） 不關(guān)聯(lián)與若的終點(diǎn)是若的始點(diǎn)是若iiiiiiijeveveva, 0, 1, 1有向圖：有向圖： 無向圖：無向圖：不關(guān)聯(lián)與若關(guān)聯(lián)與若jijiijvvvva, 0 , 1 二、圖的矩陣表示二、圖的矩陣表示第12頁/共86頁例3：分別寫出右邊兩圖的關(guān)聯(lián)矩陣解：分別為：1101100011011000000111011001A 二、圖的矩陣表示二、圖的矩陣表示eabcd1e2e3e4e5e0001101001111000011010000A第13頁/共86頁 二、圖的矩陣表示4 4

8、 應(yīng)用實(shí)例應(yīng)用實(shí)例 某廠生產(chǎn)一種彈子鎖具，每個鎖具的鑰匙有5個槽，每個槽的高度從1，2，3，4，5，6)中任取一數(shù)由于工藝及其它原因，制造鎖具時(shí)對5個槽的高度有兩個限制：(1)至少有3個不同的數(shù)；(2)相鄰兩槽的高度之差不能為5 滿足以上條件制造出來的所有互不相同的鎖具稱為一批我們的問題是如何確定每一批鎖具的個數(shù)?19941994年全國大學(xué)生數(shù)學(xué)建模競賽年全國大學(xué)生數(shù)學(xué)建模競賽B B題題( (鎖具裝箱鎖具裝箱) )中關(guān)于中關(guān)于鎖具總數(shù)的問題可敘述如下：鎖具總數(shù)的問題可敘述如下：第14頁/共86頁 該問題用圖論中的鄰接矩陣解決較為簡單該問題用圖論中的鄰接矩陣解決較為簡單易見，易見， x=t-sx

9、=t-s，其中，其中，t t代表相鄰兩槽高度之差不為代表相鄰兩槽高度之差不為5 5的鎖具數(shù)，即：滿足限制條件的鎖具數(shù)，即：滿足限制條件(2)(2)的鎖具數(shù)，的鎖具數(shù)，s s代表相代表相鄰兩槽高度之差不為鄰兩槽高度之差不為5 5且槽高僅有且槽高僅有1 1個或個或2 2個的鎖具數(shù)，個的鎖具數(shù)，即：滿足限制條件即：滿足限制條件(2)(2)但不滿足限制條件但不滿足限制條件(1)(1)的鎖具的鎖具數(shù)數(shù) 我們用圖論方法計(jì)算我們用圖論方法計(jì)算t t和和s.s. 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）第15頁/共86頁,1,2,3,4,5,6,5GVEVEij i jVij，且 在在G G中中t t每一條長度

10、為每一條長度為4 4的道路對應(yīng)于一個相的道路對應(yīng)于一個相鄰兩槽鄰兩槽高度之差不超過高度之差不超過5 5的鎖具，即滿足限制條件（的鎖具，即滿足限制條件（2 2）的鎖）的鎖具，反之亦然，于是可以通過具，反之亦然，于是可以通過G G的鄰接矩陣的鄰接矩陣A A來計(jì)算來計(jì)算t t的的值，具體步驟如下：值，具體步驟如下： 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）構(gòu)造無向圖構(gòu)造無向圖 124356第16頁/共86頁111110111111111111111111111111011111A5555545555555555555555555555554555552A141165165165165140165194

11、1941941941651651941941941941651651941941941941651651941941941941651401651651651651414A.63066161)4(ijijat因此，因此， 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）第17頁/共86頁又令又令 ,654321yyyyyys其中其中y yi i表示滿足限制條件表示滿足限制條件(2)(2)但不滿足限制條件但不滿足限制條件(1)(1)且且首位為首位為i i的鎖具數(shù)的鎖具數(shù), ,（i=1,2,3,4,5,6),i=1,2,3,4,5,6),顯然顯然y y1 1=y=y6 6, , y y2=2=y y4 4=

12、y=y3 3=y=y5 5, ,于是我們只需要計(jì)算于是我們只需要計(jì)算y y1 1和和y y2.2. 計(jì)算計(jì)算y y1 1可分別考慮槽高只有可分別考慮槽高只有1 1，1212，1313，1414，1515的的情形若只有情形若只有1 1，這樣的鎖具效只有，這樣的鎖具效只有1 1個，個，若只有若只有1 1和和i(i=2,3,4,5)i(i=2,3,4,5)，這樣的鎖具數(shù)，這樣的鎖具數(shù)=G=G中以中以1 1和和i i為為頂點(diǎn)，長度為頂點(diǎn)，長度為3 3的道路數(shù)，此數(shù)可通過的道路數(shù)，此數(shù)可通過A A的子矩陣的子矩陣A A1i1i計(jì)計(jì)算得到算得到 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）124356第18頁/

13、共86頁 二、圖的矩陣表示（應(yīng)用實(shí)例解法分析）事實(shí)上，因?yàn)槭聦?shí)上，因?yàn)?444422221111i131211iiiAAA，行第行第其中其中i=2,3,4,5,i=2,3,4,5,顯然顯然y y1 1=1+(4+4+4+4-1)=1+(4+4+4+4-1) 4=61.4=61. 同理，計(jì)算同理，計(jì)算y y2 2時(shí)應(yīng)考慮槽高只有時(shí)應(yīng)考慮槽高只有2,21,23,24,25,2,21,23,24,25,2626時(shí)的情形，類似計(jì)算可得時(shí)的情形，類似計(jì)算可得 y y2 2=1+(4+4+4+4-1)=1+(4+4+4+4-1)5=765=76 于是，于是，s=61s=612+762+764=4264=4

14、26，x=6306-426=5880.x=6306-426=5880. 該算法既易理解又易操作并且又可擴(kuò)展該算法既易理解又易操作并且又可擴(kuò)展第19頁/共86頁 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）公交線路選擇問題：公交線路選擇問題：在給定某城市公交線路的公交網(wǎng)信息后，在給定某城市公交線路的公交網(wǎng)信息后，求任意兩個站點(diǎn)之間的最佳出行路線，包括換乘次數(shù)最少、出行求任意兩個站點(diǎn)之間的最佳出行路線，包括換乘次數(shù)最少、出行時(shí)間最短、出行費(fèi)用最低等。以下圖的簡化公交網(wǎng)為例來說明。時(shí)間最短、出行費(fèi)用最低等。以下圖的簡化公交網(wǎng)為例來說明。 12345 圖中由兩條公交線路組成，實(shí)線表示第圖中由兩條公交線路組成

15、，實(shí)線表示第一條線路，依次經(jīng)過站點(diǎn)一條線路，依次經(jīng)過站點(diǎn)1,3,4,51,3,4,5，虛線表，虛線表示第二條線路，依次經(jīng)過站點(diǎn)示第二條線路，依次經(jīng)過站點(diǎn)2,3,52,3,5。 首先考慮換乘次數(shù)最少的線路選擇模型，首首先考慮換乘次數(shù)最少的線路選擇模型，首先建立直達(dá)矩陣如下：先建立直達(dá)矩陣如下：第20頁/共86頁 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）0111110101110111010011100A12345計(jì)算計(jì)算A A2 2得到：得到：42312232223241212122222232A 由于由于A A2 2為非零矩陣，所以任意兩站點(diǎn)經(jīng)為非零矩陣，所以任意兩站點(diǎn)經(jīng)過換乘一次都可到達(dá)，由于

16、問題較簡單，結(jié)過換乘一次都可到達(dá)，由于問題較簡單，結(jié)果顯然正確。果顯然正確。 一般地，比較一般地，比較A=(aA=(aijij),A),A2 2=(a=(a(2)(2)ijij),), , A Ak k=(a=(a(k)(k)ijij) )中的中的(i,j)(i,j)元夠成的向量中第一個元夠成的向量中第一個非零向量的上標(biāo)即為出行換乘的最少次數(shù)。非零向量的上標(biāo)即為出行換乘的最少次數(shù)。第21頁/共86頁 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）011231012110112103210T12345接下來考慮出行時(shí)間最短的接下來考慮出行時(shí)間最短的模型，建立直達(dá)距離矩陣：模型，建立直達(dá)距離矩陣： 下面利

17、用下面利用FloydFloyd矩陣算法可計(jì)算出出行時(shí)矩陣算法可計(jì)算出出行時(shí)間最短的路線。定義間最短的路線。定義T T* *T=(tT=(t(2)(2)ijij), ), t t(2)(2)ijij=minmin=minmin1=k=51=k=5ttikik+t+tkjkj,t,tijij, , t(2)ij表示表示從站點(diǎn)從站點(diǎn)i i到站點(diǎn)到站點(diǎn)j j的至多換乘一次的最短時(shí)間。的至多換乘一次的最短時(shí)間。 站點(diǎn)不可直達(dá)站點(diǎn)與，站的距離站點(diǎn)共有站點(diǎn)jinjintij,第22頁/共86頁 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）41235利用利用matlabmatlab編寫程序如下：編寫程序如下：T=0

18、 inf 1 2 3;inf 0 1 inf 2; 1 1 0 1 1; 2 inf 1 0 1; 3 2 1 1 0; n=length(T);T2=zeros(n);for i=1:n for j=1:n T2(i,j)=min(min(T(i,:)+T(:,j),T(i,j); endendT2計(jì)算結(jié)果為：計(jì)算結(jié)果為：T2 = 0 2 1 2 2 2 0 1 2 2 1 1 0 1 1 2 2 1 0 1 2 2 1 1 0 第23頁/共86頁 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）12345 類似可計(jì)算出類似可計(jì)算出T T3 3，T T4 4，實(shí)際上實(shí)際上T T2 2的值已為的值已為出

19、行路線的最短時(shí)間，例如出行路線的最短時(shí)間，例如T T2 2（2,52,5）=2=2，說明站點(diǎn)說明站點(diǎn)2 2到站點(diǎn)到站點(diǎn)5 5的最短時(shí)間為的最短時(shí)間為2 2站路時(shí)間。站路時(shí)間。思考：思考：最省乘車費(fèi)用的最佳出行路線該如何考最省乘車費(fèi)用的最佳出行路線該如何考慮呢？（分情況討論）慮呢？（分情況討論）（1 1）按路程收費(fèi)；（）按路程收費(fèi)；（出行時(shí)間最短出行時(shí)間最短）（2 2）按換乘次數(shù)收費(fèi)）按換乘次數(shù)收費(fèi)。（。（最少換乘次數(shù)最少換乘次數(shù)） 第24頁/共86頁 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）商人過河問題：商人過河問題：假如有三個商人各帶一名隨從要過河，只有一假如有三個商人各帶一名隨從要過河，只有

20、一條船，每次最多只能坐兩個人。為安全起見，商人數(shù)不能少于隨條船，每次最多只能坐兩個人。為安全起見，商人數(shù)不能少于隨從數(shù)，否則隨從會殺人越貨。船過一次河需要從數(shù)，否則隨從會殺人越貨。船過一次河需要5 5分鐘，問最短幾分鐘，問最短幾分鐘能使他們都過去？分鐘能使他們都過去？用鄰接矩陣來解決：用鄰接矩陣來解決：設(shè)設(shè)(m,n,(m,n,l) )表示左岸商人表示左岸商人m m人，隨從人，隨從n n人；設(shè)人；設(shè)(m,n,r)(m,n,r)表示右岸有商人表示右岸有商人m m人，隨從人，隨從n n人。從左岸到右岸去，所有可人。從左岸到右岸去，所有可能的狀態(tài)為：能的狀態(tài)為：v v1 1=(3,3,=(3,3,l)

21、, v), v2 2=(3,2,=(3,2,l), v), v3 3=(3,1,=(3,1,l), v), v4 4=(3,0, =(3,0, l), v), v5 5=(2,2,=(2,2,l), ), v v6 6=(1,1,=(1,1,l), v), v7 7=(0,3,=(0,3,l), v), v8 8=(0,2,=(0,2,l), v), v9 9=(0,1,=(0,1,l), v), v1010=(3,3,r), =(3,3,r), v v1111=(3,2,r), v=(3,2,r), v1212=(3,1,r), v=(3,1,r), v1313=(3,0,r), v=(3,

22、0,r), v1414=(2,2,r), =(2,2,r), v v1515=(1,1,r),=(1,1,r), v v1616=(0,3,r), =(0,3,r), v v1717=(0,2,r=(0,2,r), ), v v1818=(0,1,r).=(0,1,r).第25頁/共86頁 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）)(00對稱陣BBAV10 v11 v12 v13 v14 v15 v16 v17 v18v1 v2 v3 v4 v5 v6 v7 v8 v9 渡河可以理解為上面狀態(tài)的轉(zhuǎn)移，例如狀態(tài)渡河可以理解為上面狀態(tài)的轉(zhuǎn)移，例如狀態(tài)v v1 1渡河一次可渡河一次可以轉(zhuǎn)化為其他狀態(tài)以

23、轉(zhuǎn)化為其他狀態(tài)v v1515 v v1717 v v1818，其他狀態(tài)也易列出。以其他狀態(tài)也易列出。以V=vV=v1 1, , v v2 2,. v,. v1818 為頂點(diǎn)集，當(dāng)兩種狀態(tài)可以互相轉(zhuǎn)化時(shí)，就在相應(yīng)為頂點(diǎn)集，當(dāng)兩種狀態(tài)可以互相轉(zhuǎn)化時(shí)，就在相應(yīng)的來那個頂點(diǎn)間連一邊，從而建立一個二分圖的來那個頂點(diǎn)間連一邊，從而建立一個二分圖G=G=，如右，如右圖所示。圖所示。G=G=的鄰接矩陣為：的鄰接矩陣為：第26頁/共86頁 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）00000000100000001100000011000000001100001010000000000000101000001110

24、0000110100000BV10 v11 v12 v13 v14 v15 v16 v17 v18v1 v2 v3 v4 v5 v6 v7 v8 v9其中，矩陣其中，矩陣B B為：為：記記a a(k)(k)ijij為為A Ak k中的（中的（i,ji,j）元，目標(biāo)是使）元，目標(biāo)是使a(k)1,10不等于不等于0 0的最小的的最小的自然數(shù)自然數(shù)k.k. 利用利用matlabmatlab容易計(jì)算出容易計(jì)算出k=11k=11，且，且a(11)1,10 =4,=4,即小船至少即小船至少1111次才次才能把所有人全部運(yùn)到右岸，說明共有能把所有人全部運(yùn)到右岸，說明共有4 4種不同的過河方案。繼續(xù)計(jì)種不同的

25、過河方案。繼續(xù)計(jì)算可得出算可得出a a(19)(19)1,10 1,10 =45060=45060，如果允許小船過河，如果允許小船過河1919次的話，共有次的話，共有4506045060中不同的方案。中不同的方案。第27頁/共86頁 若將圖若將圖G G的每一條邊的每一條邊e e都對應(yīng)一個實(shí)數(shù)都對應(yīng)一個實(shí)數(shù)F F( (e e) ), , 則稱則稱F F( (e e) )為該邊的為該邊的權(quán)權(quán), , 并稱圖并稱圖G G為為賦權(quán)圖賦權(quán)圖, , 記為記為G G = ( = (V V, , E E , , F F ) ). . 設(shè)設(shè)G G = ( = (V V, , E E ) )是一個圖是一個圖, ,

26、v v0 0, , v v1 1, , , , v vk kV V, , 且且“11i ik k, , v vi i1 1 v vi iE E, , 則稱則稱v v0 0 v v1 1 v vk k是是G G的一條的一條通路通路. .如果通路中沒有相同的頂點(diǎn)如果通路中沒有相同的頂點(diǎn), , 則稱此通路為則稱此通路為路徑路徑, ,簡稱簡稱路路. .對于賦權(quán)圖，對于賦權(quán)圖，路的長度（即路的權(quán)）路的長度（即路的權(quán)）通常指路上所有邊通常指路上所有邊的權(quán)之和。的權(quán)之和。最短路問題最短路問題：求賦權(quán)圖上指定點(diǎn)之間的權(quán)最小的路。：求賦權(quán)圖上指定點(diǎn)之間的權(quán)最小的路。 三、最短路問題及其算法三、最短路問題及其算法

27、第28頁/共86頁重要性質(zhì)：重要性質(zhì)：若若v v0 0 v v1 1 v vm m 是是G G 中從中從v v0 0到到v vm m的最短路的最短路, , 則則對對11k km m, , v v0 0v v1 1 v vk k 必為必為G G 中從中從v v0 0到到v vk k的的最短路最短路. . 即：最短路是一條路，且最短路的任一段即：最短路是一條路，且最短路的任一段也是最短路。也是最短路。 三、最短路問題及其算法三、最短路問題及其算法第29頁/共86頁 設(shè)有給定連接若干城市的公路網(wǎng)，尋求從指定城設(shè)有給定連接若干城市的公路網(wǎng)，尋求從指定城市到各城市的最短路線。市到各城市的最短路線。 2、

28、應(yīng)用實(shí)例：最短路問題、應(yīng)用實(shí)例：最短路問題 問題的數(shù)學(xué)模型問題的數(shù)學(xué)模型: : 三、最短路問題及其算法三、最短路問題及其算法302022年年2月月3日日第30頁/共86頁312022年年2月月3日日 三、最短路問題及其算法三、最短路問題及其算法0v 3v 1v2v 4v 5v6v7v8v254647109137106648第31頁/共86頁322022年年2月月3日日 三、最短路問題及其算法三、最短路問題及其算法第32頁/共86頁332022年年2月月3日日 三、最短路問題及其算法三、最短路問題及其算法第33頁/共86頁342022年年2月月3日日 三、最短路問題及其算法三、最短路問題及其算法

29、第34頁/共86頁352022年年2月月3日日 三、最短路問題及其算法三、最短路問題及其算法0v 3v 1v2v 4v 5v6v7v8v254647109137106648第35頁/共86頁362022年年2月月3日日 三、最短路問題及其算法三、最短路問題及其算法第36頁/共86頁372022年年2月月3日日 三、最短路問題及其算法三、最短路問題及其算法第37頁/共86頁382022年年2月月3日日 三、最短路問題及其算法三、最短路問題及其算法第38頁/共86頁392022年年2月月3日日 三、最短路問題及其算法三、最短路問題及其算法0v 3v 1v2v 4v5v6v7v8v254647109

30、137106648第39頁/共86頁402022年年2月月3日日 三、最短路問題及其算法三、最短路問題及其算法第40頁/共86頁412022年年2月月3日日 三、最短路問題及其算法三、最短路問題及其算法第41頁/共86頁422022年年2月月3日日 三、最短路問題及其算法三、最短路問題及其算法0v 3v 1v2v 4v 5v6v7v8v254647109137106648第42頁/共86頁432022年年2月月3日日 三、最短路問題及其算法三、最短路問題及其算法第43頁/共86頁442022年年2月月3日日 三、最短路問題及其算法三、最短路問題及其算法第44頁/共86頁452022年年2月月3

31、日日ijkkijicbvvF1)(求求v v1 1到到v v6 6的最短路問題的最短路問題. . 三、最短路問題及其算法三、最短路問題及其算法4 11411()11 568kkF vvbc 第45頁/共86頁462022年年2月月3日日從上圖中容易得到從上圖中容易得到v v1 1到到v v6 6只有兩條路只有兩條路：v v1 1v v3 3v v6 6和和v v1 1v v4 4v v6 6. . 而這兩條路都是而這兩條路都是v v1 1到到v v6 6的最短路的最短路. . 三、最短路問題及其算法三、最短路問題及其算法第46頁/共86頁472022年年2月月3日日 三、最短路問題及其算法三、

32、最短路問題及其算法第47頁/共86頁 頂點(diǎn)頂點(diǎn)u u與與v v稱為稱為連通連通的，如果存在的，如果存在u-vu-v通路，任二頂點(diǎn)通路，任二頂點(diǎn)都連通的圖稱為都連通的圖稱為連通圖連通圖，否則，稱為，否則，稱為不連通圖不連通圖。極大連。極大連通子圖稱為通子圖稱為連通分圖連通分圖。 連通而無圈的圖稱為連通而無圈的圖稱為樹樹, , 常用常用T T 表示樹表示樹. . 樹中最長路的邊數(shù)稱為樹的樹中最長路的邊數(shù)稱為樹的高高的度為的度為1 1的頂點(diǎn)稱的頂點(diǎn)稱為為樹葉樹葉。其余的頂點(diǎn)稱為。其余的頂點(diǎn)稱為分枝點(diǎn)分枝點(diǎn)。樹的邊稱為。樹的邊稱為樹枝樹枝。 設(shè)設(shè)G G是有向圖，如果是有向圖，如果G G的底圖是樹，則稱

33、的底圖是樹，則稱G G是是有向樹有向樹，也簡稱，也簡稱樹樹。 四、最小生成樹問題及其算法四、最小生成樹問題及其算法第48頁/共86頁若 任 意 一 個 連 通 的 圖若 任 意 一 個 連 通 的 圖 G = G = 的 生 成 子 圖的 生 成 子 圖T=VT=(V(V=V,E=V,E為為E E的子集的子集) )為樹為樹, , 這棵樹這棵樹T T稱為稱為圖圖G G的生成樹的生成樹. . 設(shè)設(shè)T T是圖是圖G G的一棵生成樹的一棵生成樹, , 用用F F ( (T T) )表示樹表示樹T T中所有邊中所有邊的權(quán)數(shù)之和的權(quán)數(shù)之和, , F F( (T T) )稱為樹稱為樹T T的的權(quán)權(quán). .一個

34、連通圖一個連通圖G G的生成樹一般不止一棵的生成樹一般不止一棵, , 圖圖G G的所有生成樹中權(quán)數(shù)最小的生成樹稱為的所有生成樹中權(quán)數(shù)最小的生成樹稱為圖圖G G的的最小生成樹最小生成樹. . 四、最小生成樹問題及其算法四、最小生成樹問題及其算法第49頁/共86頁 怎樣找出最小生成樹？怎樣找出最小生成樹？G T1 T2 T3 T4 T5 T6 T7 T8 T T1 1至至T T8 8是是 圖圖G G的生的生成樹成樹 四、最小生成樹問題及其算法四、最小生成樹問題及其算法第50頁/共86頁Kruskal 算法算法 思想：在不形成圈得條件下，優(yōu)先挑選權(quán)小的邊形成生成思想：在不形成圈得條件下，優(yōu)先挑選權(quán)小

35、的邊形成生成樹。樹。76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v7 四、最小生成樹問題及其算法四、最小生成樹問題及其算法第51頁/共86頁。，取取，成成的的邊邊按按權(quán)權(quán)非非減減次次序序排排列列將將圖圖1|)| , 2 , 1()(,)1(1|21 kVjjvlEeeeGjiiiE 。；否否，取取，轉(zhuǎn)轉(zhuǎn)是是，取取是是否否相相等等？、的的標(biāo)標(biāo)號號、連連結(jié)結(jié)的的二二點(diǎn)點(diǎn)邊邊)2(1)()()2(11kkiieEEkkvlulvue 。，令令的的對對一一切切滿滿足足)(, )(min)()(, )(max)()3(vlulvlvvlulvljjj 。，轉(zhuǎn)轉(zhuǎn)取

36、取算算法法終終止止；否否是是)2(1,?1|)4(1 kkVE注：算法構(gòu)造的最小生成樹的邊集為注：算法構(gòu)造的最小生成樹的邊集為 E E1 1；標(biāo)號；標(biāo)號 l l 具有性質(zhì)：具有性質(zhì)：當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) u u、v v 之間有一條僅由之間有一條僅由 E E1 1 中的邊形成的路時(shí)，中的邊形成的路時(shí)，l l( (u u) ) = = l l( (v v) )，因此在步驟，因此在步驟 (2) (2) 發(fā)現(xiàn)發(fā)現(xiàn) l l( (u u) =) = l l( (v v) ) 時(shí)，時(shí)，( (u u, , v v) ) 不不能放入能放入 E E1 1，否則會形成一個圈。，否則會形成一個圈。 四、最小生成樹問題及其

37、算法四、最小生成樹問題及其算法第52頁/共86頁532022年年2月月3日日 四、最小生成樹問題及其算法四、最小生成樹問題及其算法第53頁/共86頁542022年年2月月3日日 四、最小生成樹問題及其算法四、最小生成樹問題及其算法第54頁/共86頁552022年年2月月3日日 四、最小生成樹問題及其算法四、最小生成樹問題及其算法運(yùn)行結(jié)果如下：運(yùn)行結(jié)果如下：T = 1 3 5 1 6 3 2 6 6 6 7 4c = 26上述例題的上述例題的matlab程序如下：程序如下：b=1 1 2 2 3 3 3 4 5 5 6;2 6 3 6 4 6 7 7 6 7 7;2 4 4 5 8 3 7 8

38、3 7 6;Krusf(b,1);112233345562636467767724458378376b76788334245v1v2v3v4v5v6v7683324v1v2v3v4v5v6v7第55頁/共86頁562022年年2月月3日日 四、最小生成樹問題及其算法四、最小生成樹問題及其算法 第56頁/共86頁572022年年2月月3日日 四、最小生成樹問題及其算法四、最小生成樹問題及其算法第57頁/共86頁582022年年2月月3日日 四、最小生成樹問題及其算法四、最小生成樹問題及其算法第58頁/共86頁592022年年2月月3日日 四、最小生成樹問題及其算法四、最小生成樹問題及其算法 運(yùn)行

39、結(jié)果如下：運(yùn)行結(jié)果如下：T = 1 1 6 6 6 3 2 6 3 5 7 4c = 2 4 3 3 6 806787603354730808738045402420A76788334245v1v2v3v4v5v6v7第59頁/共86頁1v2v3v4v5v64686865505061456054例：分別利用例：分別利用KruskalKruskal算法和算法和PrimPrim算法如圖算法如圖G G的最小生的最小生成樹：成樹： 四、最小生成樹問題及其算法四、最小生成樹問題及其算法第60頁/共86頁稱經(jīng)過圖稱經(jīng)過圖 G G = ( = (V V , , E E ) ) 的每條邊恰好一次的路為的每條邊

40、恰好一次的路為 EulerEuler路路徑徑，經(jīng)過，經(jīng)過G G 的每條邊恰好一次的回路為的每條邊恰好一次的回路為 EulerEuler回路回路。稱有。稱有 Euler Euler 回路的圖為回路的圖為 EulerEuler圖圖 五、五、E圖與圖與H圖問題圖問題命題：命題：G G 是是 Euler Euler 圖當(dāng)且當(dāng)圖當(dāng)且當(dāng)G G 連連通且沒有度數(shù)為奇數(shù)的點(diǎn)；通且沒有度數(shù)為奇數(shù)的點(diǎn)； G G 有有 Euler Euler 路徑當(dāng)且僅當(dāng)路徑當(dāng)且僅當(dāng) G G 連通且沒有或只有二個度數(shù)為基連通且沒有或只有二個度數(shù)為基數(shù)的點(diǎn)。數(shù)的點(diǎn)。ABCD4 個點(diǎn)的度數(shù)皆為奇?zhèn)€點(diǎn)的度數(shù)皆為奇數(shù)，不存在數(shù)，不存在 E

41、uler 路路第61頁/共86頁中國郵遞員問題：中國郵遞員問題： 一個郵遞員從郵局取出郵件后，需要到他管轄區(qū)域內(nèi)的每條街一個郵遞員從郵局取出郵件后，需要到他管轄區(qū)域內(nèi)的每條街道進(jìn)行投遞，送完郵件后返回郵局，問如何選擇一條總路程最道進(jìn)行投遞，送完郵件后返回郵局，問如何選擇一條總路程最短的投遞路線？短的投遞路線？以街道為邊，街道的交叉口或端點(diǎn)為點(diǎn)，街道的長度為權(quán)，構(gòu)以街道為邊，街道的交叉口或端點(diǎn)為點(diǎn)，街道的長度為權(quán)，構(gòu)造賦權(quán)圖造賦權(quán)圖G G =( =(V V, ,E,wE,w) )。投遞路線應(yīng)是一條經(jīng)過。投遞路線應(yīng)是一條經(jīng)過G G的每條邊至少的每條邊至少一次的回路。一次的回路。 五、五、E圖與圖與

42、H圖問題圖問題第62頁/共86頁將將G G的度數(shù)為奇數(shù)的點(diǎn)（必的度數(shù)為奇數(shù)的點(diǎn)（必為偶數(shù)個）兩個一組、兩為偶數(shù)個）兩個一組、兩個一組用最短路連結(jié)起來。個一組用最短路連結(jié)起來。4 3 3 34 3 3 3a 2 b 2 c 2 de 3 f 2 g 2 hi 4 j 2 k 2 l 24 322 如何分組可以使得如何分組可以使得重復(fù)路徑的總長度最短重復(fù)路徑的總長度最短？ 23 2 22 五、五、E圖與圖與H圖問題圖問題第63頁/共86頁 五、五、E圖與圖與H圖問題圖問題若若G G是是EulerEuler圖，則任何一條圖，則任何一條EulerEuler回路是最短投遞路線回路是最短投遞路線, ,都滿

43、足都滿足條件，針對這種情況，條件，針對這種情況，F(xiàn)leuryFleury提出一種算法，能夠在提出一種算法，能夠在EulerEuler圖圖中找出中找出EulerEuler路徑，解決了郵遞員問題；路徑，解決了郵遞員問題；若若G G 不是不是EulerEuler圖，則投遞路圖，則投遞路線將重復(fù)經(jīng)過某些街道，最線將重復(fù)經(jīng)過某些街道，最優(yōu)投遞路線應(yīng)使得重復(fù)經(jīng)過優(yōu)投遞路線應(yīng)使得重復(fù)經(jīng)過的街道的總長度最短。的街道的總長度最短。例如，確定右圖是否例如，確定右圖是否EulerEuler圖，若是，圖，若是，找出圖中的找出圖中的EulerEuler回路回路。2 3 6 5 4 1第64頁/共86頁652022年年2

44、月月3日日 五、五、E圖與圖與H圖問題圖問題第65頁/共86頁662022年年2月月3日日 五、五、E圖與圖與H圖問題圖問題第66頁/共86頁672022年年2月月3日日 五、五、E圖與圖與H圖問題圖問題第67頁/共86頁682022年年2月月3日日 五、五、E圖與圖與H圖問題圖問題第68頁/共86頁692022年年2月月3日日 五、五、E圖與圖與H圖問題圖問題第69頁/共86頁702022年年2月月3日日 五、五、E圖與圖與H圖問題圖問題上述例題的上述例題的MatlabMatlab程序如下：程序如下：cleard=0 1 1 1 1 1 ;1 0 1 1 1 1;1 1 0 1 1 1;1

45、1 1 0 1 1;1 1 1 1 0 1;1 1 1 1 1 0;T=Fleuf1(d); 2 3 6 5 4 1第70頁/共86頁1v2v3v4v5v例：確定所示的賦權(quán)圖是否例：確定所示的賦權(quán)圖是否EulerEuler圖，圖，若是，找出圖中的若是，找出圖中的EulerEuler回路?；芈?。 五、五、E圖與圖與H圖問題圖問題第71頁/共86頁722022年年2月月3日日 五、五、E圖與圖與H圖問題圖問題運(yùn)行結(jié)果如下：運(yùn)行結(jié)果如下：T = 1 5 4 3 5 5 4 3 2 1c = 5d = 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 02

46、v3v4v5v1v第72頁/共86頁稱經(jīng)過圖稱經(jīng)過圖 G G =( =(V V, ,E E) )的每個點(diǎn)恰好一次的路為的每個點(diǎn)恰好一次的路為HamiltonHamilton路路，經(jīng)過，經(jīng)過G G的每個點(diǎn)恰好一次的回路為的每個點(diǎn)恰好一次的回路為HamiltonHamilton回路回路。稱有。稱有HamiltonHamilton回路的回路的圖為圖為HamiltonHamilton圖圖。1112345678910121314151617181920十二面體的平面嵌入十二面體的平面嵌入為為 Hamilton 圖圖 Hamilton 圖與圖與 Euler 圖圖在定義上很相似，但判在定義上很相似，但判斷一

47、個圖是否斷一個圖是否 Hamilton 圖較判斷它是否圖較判斷它是否 Euler 圖圖要困難得多，目前還沒要困難得多，目前還沒有易驗(yàn)證的充要條件。有易驗(yàn)證的充要條件。 五、五、E圖與圖與H圖問題圖問題第73頁/共86頁在國際象棋中，馬跳動一次只能沿著一個在國際象棋中，馬跳動一次只能沿著一個 2 23 3 的長方形的對角的長方形的對角線從一個角跳到另一個角，問是否存在一串符合規(guī)定的著法使得線從一個角跳到另一個角，問是否存在一串符合規(guī)定的著法使得馬可以從任一格子出發(fā)跳遍馬可以從任一格子出發(fā)跳遍 8 88 8 的整個棋盤，并只到達(dá)每個格的整個棋盤，并只到達(dá)每個格子一次？子一次？ 5641583550

48、3960334744554059345138425746493653326145484354316237522053063221116132964214171425106192278231215128718326924* 五、五、E圖與圖與H圖問題圖問題第74頁/共86頁旅行推銷員問題旅行推銷員問題 （貨郎擔(dān)問題）（貨郎擔(dān)問題） 一個推銷員要去一些城市訪問他的客戶然后返回出發(fā)城市，一個推銷員要去一些城市訪問他的客戶然后返回出發(fā)城市，問如何選擇旅行路線可以使得總路程最短？問如何選擇旅行路線可以使得總路程最短？ 以城市為點(diǎn)，以兩個城市之間的旅行距離為權(quán)，構(gòu)造一個以城市為點(diǎn)，以兩個城市之間的旅行距離

49、為權(quán)，構(gòu)造一個賦權(quán)完全圖賦權(quán)完全圖 G G = ( = (V V , ,E ,wE ,w) ) 。 推銷員的旅行路線應(yīng)是推銷員的旅行路線應(yīng)是G G 的一條經(jīng)過每個點(diǎn)至少一次的回路，的一條經(jīng)過每個點(diǎn)至少一次的回路，且回路的長度盡可能短。且回路的長度盡可能短。 五、五、E圖與圖與H圖問題圖問題第75頁/共86頁 與最短路問題相反，至今未找到有求解旅行商問題的有與最短路問題相反，至今未找到有求解旅行商問題的有效算法，我們試圖尋找一個比較好的方法，但不一定是最優(yōu)效算法，我們試圖尋找一個比較好的方法，但不一定是最優(yōu)解；首先給出近似最優(yōu)的改良后的最鄰近算法，稱為解；首先給出近似最優(yōu)的改良后的最鄰近算法，稱為改良圈改良圈算法，算法，改良圈算法是一種近似算法，給出的結(jié)果不一定是最改良圈算法是一種近似算法，給出的結(jié)果不一定是最優(yōu)的，但是有理由認(rèn)為它常常是比較好的。優(yōu)的，但是有理由認(rèn)為它常常是比較好的。 該算法的該算法的matlabmatlab程序?yàn)椋撼绦驗(yàn)椋?五、五、E圖與圖與H圖問題圖問題第76頁/共86頁772022年年2月月3日日 五、五、E圖與圖與H圖問題圖問題第77頁/共86頁782022年年2月月3日日 五、五、E圖與圖與H圖問題圖問題例：例：給定給定4 4個點(diǎn)的坐標(biāo)為個點(diǎn)的坐標(biāo)為(0,0),(100,1000