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

1、圖論方法專(zhuān)題圖的基本概念圖的基本概念最短路問(wèn)題及其算法最短路問(wèn)題及其算法最小生成樹(shù)問(wèn)題最小生成樹(shù)問(wèn)題E圖與圖與H圖圖圖的矩陣表示圖的矩陣表示第1頁(yè)/共86頁(yè) 22022年年2月月3日日 一、圖的基本概念一、圖的基本概念第2頁(yè)/共86頁(yè)32022年年2月月3日日 一、圖的基本概念一、圖的基本概念第3頁(yè)/共86頁(yè) 一、圖的基本概念一、圖的基本概念次數(shù)為奇數(shù)頂點(diǎn)稱(chēng)為次數(shù)為奇數(shù)頂點(diǎn)稱(chēng)為奇點(diǎn)奇點(diǎn)，否則稱(chēng)為否則稱(chēng)為偶點(diǎn)偶點(diǎn)。42022年年2月月3日日第4頁(yè)/共86頁(yè)常用常用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) )稱(chēng)為頂點(diǎn)稱(chēng)

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

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

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

5、稱(chēng)為連通分圖連通分圖。 連通而無(wú)圈的圖稱(chēng)為連通而無(wú)圈的圖稱(chēng)為樹(shù)樹(shù), , 常用常用T T 表示樹(shù)表示樹(shù). . 樹(shù)中最長(zhǎng)路的邊數(shù)稱(chēng)為樹(shù)的樹(shù)中最長(zhǎng)路的邊數(shù)稱(chēng)為樹(shù)的高，高，度數(shù)為度數(shù)為1 1的頂點(diǎn)的頂點(diǎn)稱(chēng)為稱(chēng)為樹(shù)葉樹(shù)葉。其余的頂點(diǎn)稱(chēng)為。其余的頂點(diǎn)稱(chēng)為分枝點(diǎn)分枝點(diǎn)。樹(shù)的邊稱(chēng)為。樹(shù)的邊稱(chēng)為樹(shù)樹(shù)枝枝。 設(shè)設(shè)G G是有向圖，如果是有向圖，如果G G的底圖是樹(shù)，則稱(chēng)的底圖是樹(shù)，則稱(chēng)G G是是有向樹(shù)有向樹(shù)，也簡(jiǎn)稱(chēng)，也簡(jiǎn)稱(chēng)樹(shù)樹(shù)。 一、圖的基本概念一、圖的基本概念第8頁(yè)/共86頁(yè)鄰接矩陣（結(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頁(yè)/共86頁(yè)1 1 有向圖的鄰接矩陣有向圖的鄰接矩陣 A = (aij )nn （n為結(jié)點(diǎn)數(shù)）EvvEvvajijiij, 0, 1 例例1 1：寫(xiě)出右圖的鄰接矩陣：寫(xiě)出右圖的鄰接矩陣：0101100101001010A解：二、圖的矩陣表示二、圖的矩陣表示第10頁(yè)/共86頁(yè)2 2 有向圖的權(quán)矩陣有向圖的權(quán)矩陣A = (aij ) nn （n為結(jié)點(diǎn)數(shù)） EvvjiEvvvvFajijijiij , , 0 ,例2：寫(xiě)出右圖的權(quán)矩陣：05420370860A解：二、圖的矩陣表示

7、二、圖的矩陣表示第11頁(yè)/共86頁(yè)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有向圖：有向圖： 無(wú)向圖：無(wú)向圖：不關(guān)聯(lián)與若關(guān)聯(lián)與若jijiijvvvva, 0 , 1 二、圖的矩陣表示二、圖的矩陣表示第12頁(yè)/共86頁(yè)例3：分別寫(xiě)出右邊兩圖的關(guān)聯(lián)矩陣解：分別為：1101100011011000000111011001A 二、圖的矩陣表示二、圖的矩陣表示eabcd1e2e3e4e5e0001101001111000011010000A第13頁(yè)/共86頁(yè) 二、圖的矩陣表示4 4

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

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

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

11、1941941941651651941941941941651651941941941941651651941941941941651401651651651651414A.63066161)4(ijijat因此，因此， 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）第17頁(yè)/共86頁(yè)又令又令 ,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個(gè)，個(gè)，若只有若只有1 1和和i(i=2,3,4,5)i(i=2,3,4,5)，這樣的鎖具數(shù)，這樣的鎖具數(shù)=G=G中以中以1 1和和i i為為頂點(diǎn)，長(zhǎng)度為頂點(diǎn)，長(zhǎng)度為3 3的道路數(shù)，此數(shù)可通過(guò)的道路數(shù)，此數(shù)可通過(guò)A A的子矩陣的子矩陣A A1i1i計(jì)計(jì)算得到算得到 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）124356第18頁(yè)/

13、共86頁(yè) 二、圖的矩陣表示（應(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í)的情形，類(lèi)似計(jì)算可得時(shí)的情形，類(lèi)似計(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頁(yè)/共86頁(yè) 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）公交線路選擇問(wèn)題：公交線路選擇問(wèn)題：在給定某城市公交線路的公交網(wǎng)信息后，在給定某城市公交線路的公交網(wǎng)信息后，求任意兩個(gè)站點(diǎn)之間的最佳出行路線，包括換乘次數(shù)最少、出行求任意兩個(gè)站點(diǎn)之間的最佳出行路線，包括換乘次數(shù)最少、出行時(shí)間最短、出行費(fèi)用最低等。以下圖的簡(jiǎn)化公交網(wǎng)為例來(lái)說(shuō)明。時(shí)間最短、出行費(fèi)用最低等。以下圖的簡(jiǎn)化公交網(wǎng)為例來(lái)說(shuō)明。 12345 圖中由兩條公交線路組成，實(shí)線表示第圖中由兩條公交線路組成

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

16、問(wèn)題較簡(jiǎn)單，結(jié)過(guò)換乘一次都可到達(dá)，由于問(wèn)題較簡(jiǎn)單，結(jié)果顯然正確。果顯然正確。 一般地，比較一般地，比較A=(aA=(aijij),A),A2 2=(a=(a(2)(2)ijij),), , A Ak k=(a=(a(k)(k)ijij) )中的中的(i,j)(i,j)元夠成的向量中第一個(gè)元夠成的向量中第一個(gè)非零向量的上標(biāo)即為出行換乘的最少次數(shù)。非零向量的上標(biāo)即為出行換乘的最少次數(shù)。第21頁(yè)/共86頁(yè) 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）011231012110112103210T12345接下來(lái)考慮出行時(shí)間最短的接下來(lái)考慮出行時(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頁(yè)/共86頁(yè) 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）41235利用利用matlabmatlab編寫(xiě)程序如下：編寫(xiě)程序如下：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頁(yè)/共86頁(yè) 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）12345 類(lèi)似可計(jì)算出類(lèi)似可計(jì)算出T T3 3，T T4 4，實(shí)際上實(shí)際上T T2 2的值已為的值已為出

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

20、一條船，每次最多只能坐兩個(gè)人。為安全起見(jiàn)，商人數(shù)不能少于隨條船，每次最多只能坐兩個(gè)人。為安全起見(jiàn)，商人數(shù)不能少于隨從數(shù)，否則隨從會(huì)殺人越貨。船過(guò)一次河需要從數(shù)，否則隨從會(huì)殺人越貨。船過(guò)一次河需要5 5分鐘，問(wèn)最短幾分鐘，問(wèn)最短幾分鐘能使他們都過(guò)去？分鐘能使他們都過(guò)去？用鄰接矩陣來(lái)解決：用鄰接矩陣來(lái)解決：設(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頁(yè)/共86頁(yè) 二、圖的矩陣表示（應(yīng)用實(shí)例及解法分析）)(00對(duì)稱(chēng)陣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)的來(lái)那個(gè)頂點(diǎn)間連一邊，從而建立一個(gè)二分圖的來(lái)那個(gè)頂點(diǎn)間連一邊，從而建立一個(gè)二分圖G=G=，如右，如右圖所示。圖所示。G=G=的鄰接矩陣為：的鄰接矩陣為：第26頁(yè)/共86頁(yè) 二、圖的矩陣表示（應(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)到右岸，說(shuō)明共有能把所有人全部運(yùn)到右岸，說(shuō)明共有4 4種不同的過(guò)河方案。繼續(xù)計(jì)種不同的

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

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

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

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

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

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

31、日日ijkkijicbvvF1)(求求v v1 1到到v v6 6的最短路問(wèn)題的最短路問(wèn)題. . 三、最短路問(wèn)題及其算法三、最短路問(wèn)題及其算法4 11411()11 568kkF vvbc 第45頁(yè)/共86頁(yè)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的最短路的最短路. . 三、最短路問(wèn)題及其算法三、最短路問(wèn)題及其算法第46頁(yè)/共86頁(yè)472022年年2月月3日日 三、最短路問(wèn)題及其算法三、

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

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

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

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

36、取算算法法終終止止；否否是是)2(1,?1|)4(1 kkVE注：算法構(gòu)造的最小生成樹(shù)的邊集為注：算法構(gòu)造的最小生成樹(shù)的邊集為 E E1 1；標(biāo)號(hào)；標(biāo)號(hà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，否則會(huì)形成一個(gè)圈。，否則會(huì)形成一個(gè)圈。 四、最小生成樹(shù)問(wèn)題及其

37、算法四、最小生成樹(shù)問(wèn)題及其算法第52頁(yè)/共86頁(yè)532022年年2月月3日日 四、最小生成樹(shù)問(wèn)題及其算法四、最小生成樹(shù)問(wèn)題及其算法第53頁(yè)/共86頁(yè)542022年年2月月3日日 四、最小生成樹(shù)問(wèn)題及其算法四、最小生成樹(shù)問(wèn)題及其算法第54頁(yè)/共86頁(yè)552022年年2月月3日日 四、最小生成樹(shù)問(wèn)題及其算法四、最小生成樹(shù)問(wèn)題及其算法運(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頁(yè)/共86頁(yè)562022年年2月月3日日 四、最小生成樹(shù)問(wèn)題及其算法四、最小生成樹(shù)問(wèn)題及其算法 第56頁(yè)/共86頁(yè)572022年年2月月3日日 四、最小生成樹(shù)問(wèn)題及其算法四、最小生成樹(shù)問(wèn)題及其算法第57頁(yè)/共86頁(yè)582022年年2月月3日日 四、最小生成樹(shù)問(wèn)題及其算法四、最小生成樹(shù)問(wèn)題及其算法第58頁(yè)/共86頁(yè)592022年年2月月3日日 四、最小生成樹(shù)問(wèn)題及其算法四、最小生成樹(shù)問(wèn)題及其算法 運(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頁(yè)/共86頁(yè)1v2v3v4v5v64686865505061456054例：分別利用例：分別利用KruskalKruskal算法和算法和PrimPrim算法如圖算法如圖G G的最小生的最小生成樹(shù)：成樹(shù)： 四、最小生成樹(shù)問(wèn)題及其算法四、最小生成樹(shù)問(wèn)題及其算法第60頁(yè)/共86頁(yè)稱(chēng)經(jīng)過(guò)圖稱(chēng)經(jīng)過(guò)圖 G G = ( = (V V , , E E ) ) 的每條邊恰好一次的路為的每條邊

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

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

42、H圖問(wèn)題圖問(wèn)題第62頁(yè)/共86頁(yè)將將G G的度數(shù)為奇數(shù)的點(diǎn)（必的度數(shù)為奇數(shù)的點(diǎn)（必為偶數(shù)個(gè)）兩個(gè)一組、兩為偶數(shù)個(gè)）兩個(gè)一組、兩個(gè)一組用最短路連結(jié)起來(lái)。個(gè)一組用最短路連結(jié)起來(lái)。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ù)路徑的總長(zhǎng)度最短重復(fù)路徑的總長(zhǎng)度最短？ 23 2 22 五、五、E圖與圖與H圖問(wèn)題圖問(wèn)題第63頁(yè)/共86頁(yè) 五、五、E圖與圖與H圖問(wèn)題圖問(wèn)題若若G G是是EulerEuler圖，則任何一條圖，則任何一條EulerEuler回路是最短投遞路線回路是最短投遞路線, ,都滿

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

44、月月3日日 五、五、E圖與圖與H圖問(wèn)題圖問(wèn)題第65頁(yè)/共86頁(yè)662022年年2月月3日日 五、五、E圖與圖與H圖問(wèn)題圖問(wèn)題第66頁(yè)/共86頁(yè)672022年年2月月3日日 五、五、E圖與圖與H圖問(wèn)題圖問(wèn)題第67頁(yè)/共86頁(yè)682022年年2月月3日日 五、五、E圖與圖與H圖問(wèn)題圖問(wèn)題第68頁(yè)/共86頁(yè)692022年年2月月3日日 五、五、E圖與圖與H圖問(wèn)題圖問(wèn)題第69頁(yè)/共86頁(yè)702022年年2月月3日日 五、五、E圖與圖與H圖問(wèn)題圖問(wèn)題上述例題的上述例題的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頁(yè)/共86頁(yè)1v2v3v4v5v例：確定所示的賦權(quán)圖是否例：確定所示的賦權(quán)圖是否EulerEuler圖，圖，若是，找出圖中的若是，找出圖中的EulerEuler回路?；芈贰?五、五、E圖與圖與H圖問(wèn)題圖問(wèn)題第71頁(yè)/共86頁(yè)722022年年2月月3日日 五、五、E圖與圖與H圖問(wèn)題圖問(wèn)題運(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頁(yè)/共86頁(yè)稱(chēng)經(jīng)過(guò)圖稱(chēng)經(jīng)過(guò)圖 G G =( =(V V, ,E E) )的每個(gè)點(diǎn)恰好一次的路為的每個(gè)點(diǎn)恰好一次的路為HamiltonHamilton路路，經(jīng)過(guò)，經(jīng)過(guò)G G的每個(gè)點(diǎn)恰好一次的回路為的每個(gè)點(diǎn)恰好一次的回路為HamiltonHamilton回路回路。稱(chēng)有。稱(chēng)有HamiltonHamilton回路的回路的圖為圖為HamiltonHamilton圖圖。1112345678910121314151617181920十二面體的平面嵌入十二面體的平面嵌入為為 Hamilton 圖圖 Hamilton 圖與圖與 Euler 圖圖在定義上很相似，但判在定義上很相似，但判斷一

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

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

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