建模課件圖論模型貴

1、數(shù)學(xué)模型 圖論模型 朱和貴朱和貴 1. 圖論的基本概念2. 最短路問(wèn)題及算法 圖論模型 3. 最小生成樹(shù)及算法 4.網(wǎng)絡(luò)流問(wèn)題及算法 5. 行遍性問(wèn)題及算法18 最短路徑問(wèn)題是圖論中十分重要的最優(yōu)最短路徑問(wèn)題是圖論中十分重要的最優(yōu)化問(wèn)題之一，它作為一個(gè)經(jīng)常被用到的基本化問(wèn)題之一，它作為一個(gè)經(jīng)常被用到的基本工具，可以解決生產(chǎn)實(shí)際中的許多問(wèn)題，比工具，可以解決生產(chǎn)實(shí)際中的許多問(wèn)題，比如城市中的管道鋪設(shè)，線路安排，工廠布局，如城市中的管道鋪設(shè)，線路安排，工廠布局，設(shè)備更新等等。也可以用于解決其它的最優(yōu)設(shè)備更新等等。也可以用于解決其它的最優(yōu)化問(wèn)題?；瘑?wèn)題。2. 最短路問(wèn)題及算法 19 例例 如下圖所示

2、的單行線交通網(wǎng)，每個(gè)弧旁邊的數(shù)字如下圖所示的單行線交通網(wǎng)，每個(gè)弧旁邊的數(shù)字表示這條單行線的長(zhǎng)度?，F(xiàn)在有一個(gè)人要從表示這條單行線的長(zhǎng)度?，F(xiàn)在有一個(gè)人要從V1出發(fā)，經(jīng)出發(fā)，經(jīng)過(guò)這個(gè)交通網(wǎng)到達(dá)過(guò)這個(gè)交通網(wǎng)到達(dá)V6 6， 要尋求總路程最短的要尋求總路程最短的 線路。線路。 v6v5v3v1v4v2365112436 從從v v1 1到到v v6 6的路線是很多的。比如從的路線是很多的。比如從V V1 1出發(fā)，經(jīng)過(guò)出發(fā)，經(jīng)過(guò)V V2 2 ,V,V4 4到達(dá)到達(dá)V V6 6或者從或者從V V1 1出發(fā)，經(jīng)過(guò)出發(fā)，經(jīng)過(guò)V V2 2，V V3 3，V V5 5到達(dá)到達(dá)V V6 6等等。但不同等等。但不同的路線

3、，經(jīng)過(guò)的總長(zhǎng)度是不同的。例如，按照第一個(gè)線路，的路線，經(jīng)過(guò)的總長(zhǎng)度是不同的。例如，按照第一個(gè)線路，總長(zhǎng)度是總長(zhǎng)度是3+6+3=123+6+3=12單位，按照第二個(gè)路線，總長(zhǎng)度是單位，按照第二個(gè)路線，總長(zhǎng)度是3+1+1+6=113+1+1+6=11單位。單位。20 求非負(fù)賦權(quán)圖求非負(fù)賦權(quán)圖G中某一點(diǎn)到其它各點(diǎn)最中某一點(diǎn)到其它各點(diǎn)最短路，一般用短路，一般用Dijkstra( (迪克斯特拉迪克斯特拉) )標(biāo)號(hào)算標(biāo)號(hào)算法；求非負(fù)賦權(quán)圖上任意兩點(diǎn)間的最短路，法；求非負(fù)賦權(quán)圖上任意兩點(diǎn)間的最短路，一般用一般用Floyd(弗洛伊德弗洛伊德) )算法。這兩種算法均算法。這兩種算法均適用于有向非負(fù)賦權(quán)圖（適用于

4、有向非負(fù)賦權(quán)圖（Floyd算法算法也適應(yīng)也適應(yīng)于負(fù)賦權(quán)圖）。于負(fù)賦權(quán)圖）。 21原則：原則： 如果如果P是是D中從中從vs到到vj的最短路，的最短路，vi是是P中中的一個(gè)點(diǎn)，那么，從的一個(gè)點(diǎn)，那么，從vs沿沿P到到vi的路是從的路是從vs到到vi的最短路。的最短路。24例例6求求v1到到v6的最短路的最短路（1）首先給）首先給v1以以P標(biāo)號(hào)：標(biāo)號(hào)： 標(biāo)號(hào)以標(biāo)號(hào)以（ ）形式標(biāo)在結(jié)點(diǎn)旁邊形式標(biāo)在結(jié)點(diǎn)旁邊 0 0：表示從表示從V V1 1到該點(diǎn)的最短距離到該點(diǎn)的最短距離 V1V1：表示從表示從V V1 1到該點(diǎn)的最短路中上一個(gè)頂點(diǎn)。到該點(diǎn)的最短路中上一個(gè)頂點(diǎn)。v6v5v3v1v4v236511243

5、625（2）S：V1S：V2，V3，V4，V5，V6求出（求出（S S）所有）所有弧，分別計(jì)算：弧，分別計(jì)算：S12=0+3=3,S13=0+5=5,MinSij=S12給給V2標(biāo)號(hào)（標(biāo)號(hào)（3，V1）v6v5v3v1v4v236511243626（3）S：V1，V2S：V3，V4，V5，V6求出（求出（S S）所有）所有弧，分別計(jì)算：弧，分別計(jì)算：S13=0+5=5S23=3+1=4S14=S24=3+6=9MinSij=S23給給V3標(biāo)號(hào)（標(biāo)號(hào)（4，V2）v6v5v3v1v4v236511243627（4）S：V1，V2，V3S：V4，V5，V6求出（求出（S S）所有）所有弧，分別計(jì)算：弧

6、，分別計(jì)算：S14=S24=3+6=9S34=4+4=8S15=S25=S35=4+1=5MinSij=S35給給V5標(biāo)號(hào)（標(biāo)號(hào)（5，V3）v6v5v3v1v4v236511243628v6v5v3v1v4v2365112436（5）S：V1，V2，V3，V5S：V4，V6求出（求出（S S）所有）所有弧，分別計(jì)算：弧，分別計(jì)算：S14=S24=3+6=9S34=4+4=8S54=5+2=7S56=5+6=11MinSij=S54給給V4標(biāo)號(hào)（標(biāo)號(hào)（7，V5）29（6）S：V1，V2，V3，V4，V5S：V6求出（求出（S S）所有）所有弧，分別計(jì)算：弧，分別計(jì)算：S46=7+3=10S56=

7、5+6=11MinSij=S46給給V6標(biāo)號(hào)（標(biāo)號(hào)（10，V4）12354v6v5v3v1v4v236511243630(7) (7) 標(biāo)出最短路標(biāo)出最短路 最短路徑是：最短路徑是： V1V2V3V5V4V6 路長(zhǎng)路長(zhǎng)1010。同時(shí)得到起點(diǎn)到其余各點(diǎn)的最短路。同時(shí)得到起點(diǎn)到其余各點(diǎn)的最短路。（3 3）（4 4）v6v5v3v1v4v2365112436（5 5）（7 7）31求天然氣管道最優(yōu)路徑求天然氣管道最優(yōu)路徑 籌建中的天然氣管道網(wǎng)設(shè)計(jì)如圖所示：籌建中的天然氣管道網(wǎng)設(shè)計(jì)如圖所示： 解為：解為： LJGEDA 表示壓縮機(jī)站，流動(dòng)主向用箭表示壓縮機(jī)站，流動(dòng)主向用箭頭表示，每個(gè)管道旁的數(shù)字表示管

8、段長(zhǎng)度，現(xiàn)需要頭表示，每個(gè)管道旁的數(shù)字表示管段長(zhǎng)度，現(xiàn)需要求該網(wǎng)絡(luò)從起點(diǎn)求該網(wǎng)絡(luò)從起點(diǎn)A A到終點(diǎn)到終點(diǎn)L L的最短通道，并確定沿最的最短通道，并確定沿最優(yōu)路徑相應(yīng)的壓縮機(jī)站所處的節(jié)點(diǎn)。優(yōu)路徑相應(yīng)的壓縮機(jī)站所處的節(jié)點(diǎn)。 LCBA、A AC CF FI IK KL LJ JE EB BD DH HG G3 33 35 52 21 12 23 34 44 44 43 33 34 46 64 43 31 15 55 52 2 例例: :每對(duì)頂點(diǎn)間的最短路算法每對(duì)頂點(diǎn)間的最短路算法 尋求賦權(quán)圖中各對(duì)頂點(diǎn)之間最短路，顯然可以調(diào)用 Dijkstra 算法。具體方法是：每次以不同的頂點(diǎn)作為起點(diǎn)，用 Dijk

9、stra 算法求出從該起點(diǎn)到其余頂點(diǎn)的最短路徑，反復(fù)執(zhí)行次這樣的操作，就可得到每對(duì)頂點(diǎn)之間的最短路。但這樣做需要大量重復(fù)計(jì)算，效率不高。R. W. Floyd（弗洛伊德）另辟蹊徑，提出了比這更好的算法，操作方式與 Dijkstra 算法截然不同。 Floyd 算法的基本思想是：從圖的帶權(quán)鄰接矩陣 A = a(i, j)nn 開(kāi)始，在 A 中用插入頂點(diǎn)的方法依次構(gòu)造出 n 個(gè)矩陣 D(1)、D(2)、D(n)，使最后得到的矩陣 D(n) 成為圖的距離矩陣圖的距離矩陣，即矩陣矩陣D(n)的的i 行行j 列元素便是列元素便是i 號(hào)頂點(diǎn)到號(hào)頂點(diǎn)到j(luò) 號(hào)頂號(hào)頂點(diǎn)的距離點(diǎn)的距離。構(gòu)造 D(i) 的同時(shí)，也

10、引入一個(gè)路由路由矩陣矩陣P(i) 來(lái)記錄兩點(diǎn)間的最短路徑。 構(gòu)造矩陣 D(k)，k = 1, 2, , n，采用如下的遞推公式： D(0) = dij(0)nn = A：是帶權(quán)鄰接矩陣，dij(0) 表示從 vi 到 vj 的、中間不插入任何點(diǎn)的路徑，即邊 vivj 的權(quán)值； D(1) = dij(1)nn，其中 dij(1) = mindij(0)，di1(0) d1j(0)：dij(1) 表示從 vi 到 vj 的、中間最多只允許 v1 作為插入點(diǎn)的路徑中最短路的長(zhǎng)度； D(2) = dij(2)nn，其中 dij(2) = mindij(1)，di2(1) d2j(1)：dij(2) 表

11、示從 vi 到 vj 的、中間最多只允許 v1 和 v2 作為插入點(diǎn)的路徑中最短路的長(zhǎng)度； D(n) = dij(n)nn，其中 dij(n) = mindij(n1)， di, n1(n1) dn1, j(n1)：dij(n) 表示從 vi 到 vj 的、中間最多只允許 v1, v2, , vn1 作為插入點(diǎn)的路徑中最短路的長(zhǎng)度，即 vi 和 vj 之間的距離。（II）求路徑矩陣的方法.在建立距離矩陣的同時(shí)可建立路徑矩陣R ivjv（III）查找最短路路徑的方法.然后用同樣的方法再分頭查找若：1av2av3avkav1bv2bvmbv例 求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑. ,05314

12、2503330212044401210 )0(D,654321654321654321654321654321654321 )0(R,053142503330212044401210 )0(D,min) 1() 1() 1()(kkjkikkijkijdddd插入點(diǎn)插入點(diǎn)v1，得：得：,053132503330212043401210)1(D,654311654321654321654321154321654321 )1(R矩陣中帶“=”的項(xiàng)為經(jīng)迭代比較以后有變化的元素.,min) 1() 1() 1()(kkjkikkijkijdddd插入點(diǎn)插入點(diǎn)v2，得：得：,05313250333021

13、2043401210)1(D矩陣中帶“=”的項(xiàng)為經(jīng)迭代比較以后有變化的元素.,05313250333021204534012510)2(D,654311654321654321654322154321654221 )2(R,min) 1() 1() 1()(kkjkikkijkijdddd,053132503330267120453640127510)3(D,654311654321654333654322153321653221 )3(R插入點(diǎn)插入點(diǎn)v3，得：得：,05313250333021204534012510)2(D,min) 1() 1() 1()(kkjkikkijkijdddd

14、,053132503330267120453640127510)3(D插入點(diǎn)插入點(diǎn)v4，得：得：,05313250359103302671520453964012107510)4(D,654311654444654333644322143321643221 )4(R,)4()5(DD插入點(diǎn)插入點(diǎn)v5，得：得：,)4()5(RR,min) 1() 1() 1()(kkjkikkijkijdddd插入點(diǎn)插入點(diǎn)v6，得：得：,05313250359103302671520453964012107510)5(D,053132503587330265152043386401275310)6(D.6543

15、11654466654336644326163321666621 )6(R,053132503587330265152043386401275310)6(D.654311654466654336644326163321666621 )6(R8)6(52d故從v5到v2的最短路為8 6)6(52R由v6向v5追溯: . 6)6(56R由v6向v2追溯: , 1)6(62R. 2)6(12R所以從到的最短路徑為： .2165vvvv Kruskal(克魯斯卡爾克魯斯卡爾)算法的基本思想算法的基本思想 設(shè) T 和 C(T) 分別為圖 G 的最小生成樹(shù)的邊集及其權(quán)值，初始狀態(tài)均為空，算法結(jié)束時(shí) T包含

16、最小生成樹(shù)的所有邊，C(T) 表示最小生成樹(shù)的權(quán)值。令 VS是一個(gè)不相交的節(jié)點(diǎn)的集合，初始狀態(tài)時(shí) VS = v1, v2, , vn。算法的主要步驟是每次從邊集 E 中選出一條未處理的有最小權(quán)值的邊 (u, v) 進(jìn)行分析，如果 u 和 v 同屬于 VS 的一個(gè)元素集，則將邊 (u, v) 刪除，如果 u 和 v 分屬于 VS 的兩個(gè)元素集，則將邊 (u, v) 加入到 T 中，并將這兩個(gè)元素集合并為一個(gè)元素集并將這兩個(gè)元素集合并為一個(gè)元素集，然后再?gòu)?E 中另選權(quán)值最小的邊進(jìn)行處理，直至找到一棵最小生成樹(shù)為止。例n n個(gè)城市個(gè)城市, ,各城市之間的距離如下各城市之間的距離如下，從一個(gè)城市出發(fā)

17、走遍各個(gè)城市, ,如何選擇最優(yōu)的如何選擇最優(yōu)的旅行路線.用 Kruskal 算法求上圖給出的賦權(quán)圖的最小生成樹(shù)。 解：將圖的邊按照權(quán)值從小到大進(jìn)行排列：邊(a, b) (c, e) (a, e) (b, c) (d, g) (a, c)權(quán)45791215邊(d, f)(f, g)(c, d) (a, g) (e, g) (d, e)權(quán)162025283032步驟選出邊ew(e)操作VSTC(T)1(a, b)4加到T中a, b, c, d, e, f, g(a, b)42(c, e)5加到T中a, b, c, e, d, f, g(a, b), (c, e)93(a, e)7加到T中a, b,

18、 c, e, d, f, g(a, b), (c, e), (a, e)164(b, c)9刪除a, b, c, e, d, f, g(a, b), (c, e), (a, e)165(d, g)12加到T中a, b, c, e, d, g, f(a, b), (c, e), (a, e), (d, g)286(a, c)15刪除a, b, c, e, d, g, f(a, b), (c, e), (a, e), (d, g)287(d, f)16加到T中a, b, c, e, d, g, f(a, b), (c, e), (a, e), (d, g), (d, f)448(f, g)20刪除

19、a, b, c, e, d, g, f(a, b), (c, e), (a, e), (d, g), (d, f), (c, d)449(c, d)25加到T中a, b, c, e, d, g, f(a, b), (c, e), (a, e), (d, g), (d, f), (c, d)692求最小生成樹(shù)的 Prim 算法Prim(普里姆普里姆)算法的直觀描述算法的直觀描述 假設(shè) T是賦權(quán)圖 G 的最小生成樹(shù)。任選一個(gè)頂點(diǎn)將其涂紅，其余頂點(diǎn)為白點(diǎn)；在一個(gè)端在一個(gè)端點(diǎn)為紅色，另一個(gè)端點(diǎn)為白色的邊中點(diǎn)為紅色，另一個(gè)端點(diǎn)為白色的邊中，找一條權(quán)最小的邊涂紅，把該邊的白端點(diǎn)也涂成紅色；如此，每次將一條

20、邊和一個(gè)頂點(diǎn)涂成紅色，直直到所有頂點(diǎn)都成紅色為止到所有頂點(diǎn)都成紅色為止。最終的紅色邊便構(gòu)成最小生成樹(shù) T的邊集合。 例如，上一小節(jié)給出的賦權(quán)圖，按照上面的描述，容易求出其最小生成樹(shù)。 在實(shí)際應(yīng)用中，還會(huì)遇到求一個(gè)賦權(quán)圖的最大生在實(shí)際應(yīng)用中，還會(huì)遇到求一個(gè)賦權(quán)圖的最大生成樹(shù)的問(wèn)題。比如，某圖的邊權(quán)代表的是利潤(rùn)或成樹(shù)的問(wèn)題。比如，某圖的邊權(quán)代表的是利潤(rùn)或效益，則最終的問(wèn)題很可能就是求其最大生成樹(shù)。效益，則最終的問(wèn)題很可能就是求其最大生成樹(shù)。事實(shí)上，從上面兩個(gè)算法可以看出，只要邊權(quán)的事實(shí)上，從上面兩個(gè)算法可以看出，只要邊權(quán)的選擇改為從大到小，求最小生成樹(shù)的算就可以用選擇改為從大到小，求最小生成樹(shù)的算

21、就可以用來(lái)求最大生成樹(shù)了來(lái)求最大生成樹(shù)了58 例：有一項(xiàng)工程，要埋設(shè)電纜將中央控制室與例：有一項(xiàng)工程，要埋設(shè)電纜將中央控制室與12個(gè)控制點(diǎn)連通。圖中的各線段標(biāo)出了允許挖電纜溝個(gè)控制點(diǎn)連通。圖中的各線段標(biāo)出了允許挖電纜溝的地點(diǎn)和距離（單位：百米）。若電纜線每米的地點(diǎn)和距離（單位：百米）。若電纜線每米20元，元，挖電纜溝（深挖電纜溝（深1米，寬米，寬0.6米）土方每立方米米）土方每立方米5元，請(qǐng)?jiān)?qǐng)作該項(xiàng)工程預(yù)算，回答最少需要多少元？作該項(xiàng)工程預(yù)算，回答最少需要多少元？ 行行 遍遍 性性 問(wèn)問(wèn) 題題一、中一、中 國(guó)國(guó) 郵郵 遞遞 員員 問(wèn)問(wèn) 題題二、推二、推 銷銷 員員 問(wèn)問(wèn) 題題三、建模案例：

22、最佳災(zāi)情巡視路線三、建模案例：最佳災(zāi)情巡視路線（一）（一） 歐歐 拉拉 圖圖（二）（二） 中中 國(guó)國(guó) 郵郵 遞遞 員員 問(wèn)問(wèn) 題題（一）（一） 哈哈 密密 爾爾 頓頓 圖圖（二）（二） 推推 銷銷 員員 問(wèn)問(wèn) 題題 定定義義 設(shè)圖 G =（V，E） ，ME，若 M 的邊互不相鄰，則稱 M 是 G 的一個(gè)匹匹配配.若頂點(diǎn) v與 M 的一條邊關(guān)聯(lián)，則稱 v是 M飽和的飽和的 設(shè) M 是 G 的一個(gè)匹配，若 G 的每個(gè)頂點(diǎn)都是 M飽和的，則稱 M 是 G 的理理想想匹匹配配.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割邊G的邊e是割邊的充要條件是e不含在G的圈中 割邊的定義割邊

23、的定義：設(shè)G連通，e E(G),若從G中刪除邊e后，圖G-e不連通，則稱邊e為圖G的割邊e3v1v2v3v4e1e2e4e5e6歐歐 拉拉 圖圖e3v1v2v3v4e1e2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1歐拉道路：v1e1v2e2v3e5v1e4v4e3v3歐拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題- -定義定義 若將投遞區(qū)的街道用邊表示，街道的長(zhǎng)度用邊權(quán)表示，郵局街道交叉口用點(diǎn)表示，則一個(gè)投遞區(qū)構(gòu)成一個(gè)賦權(quán)連通無(wú)向圖中國(guó)郵遞員問(wèn)題轉(zhuǎn)化為：在一個(gè)非負(fù)加權(quán)連通圖中，尋求一個(gè)權(quán)最小的巡回這樣的巡回稱為最最佳佳巡巡回回

24、中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題- -算法算法 1、G是歐拉圖是歐拉圖 此時(shí) G 的任何一個(gè)歐拉巡回便是最佳巡回問(wèn)題歸結(jié)為在歐拉圖中確定一個(gè)歐拉巡回Fleury 算算法法：求歐拉圖的歐拉巡回V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10Fleury 算算法法 算算法法步步驟驟 ：（）任選 一個(gè)頂點(diǎn) v0，令道路 w0=v0（）假定 道路 wi=v0e1v1e2eivi已經(jīng)選好，則從 Ee1,e2, ,ei中選一條邊 ei+1，使： a）ei+1與 vi相關(guān)聯(lián)b）除非不能 選擇，否 則一定要 使 ei+1不是 Gi=GE-e1,e2, ,ei的割邊（）第（ ）步不 能進(jìn)行時(shí)

25、就停止2、G 不是歐拉圖不是歐拉圖 若G不是歐拉圖，則G的任何一個(gè)巡回經(jīng)過(guò)某些邊必定多于一次 解決這類問(wèn)題的一般方法是，在一些點(diǎn)對(duì)之間引入重復(fù)邊（重復(fù)邊與它平行的邊具有相同的權(quán)），使原圖成為歐拉圖，但希望所有添加的重復(fù)邊的權(quán)的總和為最小情形情形G正好有兩個(gè)奇次頂點(diǎn)正好有兩個(gè)奇次頂點(diǎn)（）用 Dijkstra 算法求出奇次頂點(diǎn) u 與 v 之間的最短路徑 P（）令 G*=GP，則 G*為歐拉圖（）用 Fleury 算法求出 G*的歐拉巡回，這就是 G 的最佳巡回V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9情形情形G有有n個(gè)奇次頂點(diǎn)個(gè)奇次頂點(diǎn)（n）Edmonds 最小對(duì)集算法：最

26、小對(duì)集算法：基 本 思 想 ： 先將奇次頂點(diǎn)配對(duì)，要求最佳配對(duì)，即點(diǎn)對(duì)之間距離總和最小再沿點(diǎn)對(duì)之間的最短路徑添加重復(fù)邊得歐拉圖 G*，G*的歐拉巡回便是原圖的最佳巡回算法步驟：算法步驟：（）用 Floyd 算法求出的所有奇次頂點(diǎn)之間的最短路徑和距離（）以 G 的所有奇次頂點(diǎn)為頂點(diǎn)集（個(gè)數(shù)為偶數(shù)） ，作一完備圖，邊上的權(quán)為兩端點(diǎn)在原圖 G 中的最短距離，將此完備加權(quán)圖記為 G1（）在 G 中沿配對(duì)頂點(diǎn)之間的最短路徑添加重復(fù)邊得歐拉圖 G*（）用 Fleury 算法求出 G*的歐拉巡回，這就是 G 的最佳巡回（）求出G1的最小權(quán)理想匹配M，得到奇次頂點(diǎn)的最佳配對(duì)例例求右圖所示投遞區(qū)的一條最佳郵遞路

27、線1圖中有 v4、v7、v8、v9四個(gè)奇次頂點(diǎn)用 Floyd 算法求出它們之間的最短路徑和距離：3),(,6),(,9),(,6)(,3),(,5),(,9898979787879,49848484747234989787948474vvdvvPvvdvvPvvdvvPvvdvvvPvvdvvPvvdvvvvPvvvvvvvvvvvv2以 v4、v7、v8、v9為頂點(diǎn)，它們之間的距離為邊權(quán)構(gòu)造完備圖 G13求出 G1的最小權(quán)完美匹配 M=(v4,v7),(v8,v9)4在 G 中沿 v4到 v7的最短路徑添加重復(fù)邊，沿 v8到 v9的最短路徑 v8v9添加重復(fù)邊，得歐拉圖 G2G2中一條歐拉巡

28、回就是 G 的一條最佳巡回其權(quán)值為返回返回哈哈 密密 爾爾 頓頓 圖圖定定義義設(shè) G=(V,E)是連通無(wú)向圖（） 經(jīng)過(guò) G 的每個(gè)頂點(diǎn)正好一次的路徑，稱為 G 的一條 哈哈密密爾爾頓頓路路徑徑（） 經(jīng)過(guò) G 的每個(gè)頂點(diǎn)正好一次的圈，稱為 G 的哈哈密密爾爾 頓頓圈圈或 H 圈（）含 H 圈的圖稱為哈哈密密爾爾頓頓圖圖或 H 圖返回返回推銷員問(wèn)題推銷員問(wèn)題- -定義定義 流動(dòng)推銷員需要訪問(wèn)某地區(qū)的所有城鎮(zhèn)，最后回到出發(fā)點(diǎn)問(wèn)如何安排旅行路線使總行程最小這就是推銷員問(wèn)題推銷員問(wèn)題 若用頂點(diǎn)表示城鎮(zhèn)，邊表示連接兩城鎮(zhèn)的路，邊上的權(quán)表示距離（或時(shí)間、費(fèi)用），距離（或時(shí)間、費(fèi)用），于是推銷員問(wèn)題就成為在加

29、權(quán)圖中尋找一條經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的最短閉通路問(wèn)題定義定義在加權(quán)圖G=(V,E)中，（）權(quán)最小的哈密爾頓圈稱為最佳最佳H圈圈（）經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的權(quán)最小的閉通路稱為最佳推銷員回最佳推銷員回路路 一般說(shuō)來(lái)，最佳哈密爾頓圈不一定是最佳推銷員回路，同樣最佳推銷員回路也不一定是最佳哈密爾頓圈H回路，長(zhǎng)22最佳推銷員回路，長(zhǎng)4最佳推銷員回路問(wèn)題可轉(zhuǎn)化為最佳 H 圈問(wèn)題方法是由給定的圖 G=(V,E)構(gòu)造一個(gè)以 V 為頂點(diǎn)集的完備圖 G=(V,E)，E的每條邊(x,y)的權(quán)等于頂點(diǎn) x 與 y 在圖中最短路的權(quán)即：x,yE w(x,y)=mindG(x,y)定理定理加權(quán)圖 G 的最佳推銷員回路的權(quán)與 G的最佳 H 圈的權(quán)相同（）任取初始 H 圈: C0=v1,v2,vi, ,vj,vn,v1（）對(duì)所