【正文】 ， ， ， 。 （ iv）選 中一頂點 ，若 已被 許配，且 ，則 ， ，轉(zhuǎn)（ iii）；否則，取 中一個 可增廣軌 ，令 ， 轉(zhuǎn)（ ii）。 其中 是 中 的相鄰頂點集。 l lGlGMX M lGu }{uS? ??TTSN lG ?)( TSN lG ?)()}()()({m i n, xywylxlTySxl ??? ?????????????其它),(,)(,)()(vlTvvlSvvlvl ll??ll? ll GG ?TSN lG ?)( y y M Myx?}{zSS ?? }{yTT ?? lG M ),( yuP))(())(( MPEPEMM ??? ?)(SN lG lG S Euler圖和 Hamilton圖 基本概念 定義 經(jīng)過的每條邊的跡叫做的 Euler跡；閉的 Euler跡叫做 Euler回路或回路； 含 Euler回路的圖叫做 Euler圖。 直觀地講， Euler圖就是從一頂點出發(fā)每邊恰通過一次能回到出發(fā)點的那種圖， 即不重復(fù)地行遍所有的邊再回到出發(fā)點。 定理 7 （ i） 是 Euler圖的充分必要條件是 連通且每頂點皆偶次。 （ ii） 是 Euler圖的充分必要條件是 連通且 ， 是圈。 （ iii） 中有 Euler跡的充要條件是 連通且至多有兩個奇次點。 G GG G?diiCG1?? iCG G定義 包含的每個頂點的軌叫做 Hamilton(哈密頓 )軌；閉的 Hamilton軌 叫做 Hamilton圈或 圈；含 Hamilton圈的圖叫做 Hamilton圖。 H直觀地講， Hamilton圖就是從一頂點出發(fā)每頂點恰通過一次能回到出發(fā)點的那種圖 ，即不重復(fù)地行遍所有的頂點再回到出發(fā)點。 Euler回路的 Fleury算法 1921年， Fleury給出下面的求 Euler回路的算法。 Fleury算法： 1. ，令 。 2. 假設(shè)跡 已經(jīng)選定，那么按下述方法從 中選取邊： （ i） 和 相關(guān)聯(lián)； （ ii）除非沒有別的邊可選擇，否則不是 的割邊 (cut edge)。 (所謂 割邊是一條刪除后使連通圖不再連通的邊 )。 3. 當(dāng)?shù)?2步不能再執(zhí)行時，算法停止。 )(0 GVv ?? 00 vW ?iii vevevW ?110?},{ 1 ieeE ??1?ieiv},{ 1 ii eeGG ??? 應(yīng)用 郵遞員問題 中國郵遞員問題 一位郵遞員從郵局選好郵件去投遞，然后返回郵局，當(dāng)然他必須經(jīng)過他負責(zé)投遞的 每條街道至少一次，為他設(shè)計一條投遞路線，使得他行程最短。 上述中國郵遞員問題的數(shù)學(xué)模型是：在一個賦權(quán)連通圖上求一個含所有邊的回路，且使此 回路的權(quán)最小。顯然，若此連通賦權(quán)圖是 Euler圖，則可用 Fleury算法求 Euler回路，此回路 即為所求。 旅行商（ TSP）問題 一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品，然后回到他的出發(fā)地。如何為他設(shè)計一條最短的 旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？這個問題稱為旅行商 問題。用圖論的術(shù)語說，就是在一個賦權(quán)完全圖中，找出一個有最小權(quán)的 Hamilton圈。 稱這種圈為最優(yōu)圈。與最短路問題及連線問題相反，目前還沒有求解旅行商問題的有效算 法。所以希望有一個方法以獲得相當(dāng)好（但不一定最優(yōu)）的解。 一個可行的辦法是首先求一個 Hamilton圈，然后適當(dāng)修改以得到具有較小權(quán)的 另一個 Hamilton圈。修改的方法叫做改良圈算法。設(shè)初始圈 。 121 vvvvC n??（ i）對于 ，構(gòu)造新的 Hamilton圈 : , 它是由中刪去邊 和 ，添加邊 和 而得到的。若 ，則以 代替 ， 叫做 的改良圈。 （ ii）轉(zhuǎn)（ i），直至無法改進，停止 nji ???? 1112112121 vvvvvvvvvvvC njjijjjiij ??? ??????1?iivv 1?jjvv jivv 11 ?? jivv)()()()( 1111 ???? ??? jjiijiji vvwvvwvvwvvw ijC CijCC用改良圈算法得到的結(jié)果幾乎可以肯定不是最優(yōu)的。為了得到更高的精確度，可以選擇 不同的初始圈，重復(fù)進行幾次算法，以求得較精確的結(jié)果。 例 13 從北京（ Pe）乘飛機到東京 (T)、紐約 (N)、墨西哥城 (M)、倫敦 (L)、巴黎 (Pa) 五城市做旅游，每城市恰去一次再回北京，應(yīng)如何安排旅游線，使旅程最短？各城市 之間的航線距離如下表： L M N Pa Pe T L 56 35 21 51 60 M 56 21 57 78 70 N 35 21 36 68 68 Pa 21 57 36 51 61 Pe 51 78 68 51 13 T 60 70 68 61 13 解：編寫程序如下： clc,clear a(1,2)=56。a(1,3)=35。a(1,4)=21。a(1,5)=51。a(1,6)=60。 a(2,3)=21。a(2,4)=57。a(2,5)=78。a(2,6)=70。 a(3,4)=36。a(3,5)=68。a(3,6)=68。 a(4,5)=51。a(4,6)=61。 a(5,6)=13。 a(6,:)=0。 a=a+a39。 c1=[5 1:4 6]。 L=length(c1)。 flag=1。 while flag0 flag=0。 for m=1:L3 for n=m+2:L1 if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))a(c1(m),c1(m+1))+a(c1(n),c1(n+1)) flag=1。 c1(m+1:n)=c1(n:1:m+1)。 end end end end sum1=0。 for i=1:L1 sum1=sum1+a(c1(i),c1(i+1))。 end circle=c1。 sum=sum1。 c1=[5 6 1:4]。%改變初始圈，該算法的最后一個頂點不動 flag=1。 while flag0 flag=0。 for m=1:L3 for n=m+2:L1 if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))... a(c1(m),c1(m+1))+a(c1(n),c1(n+1)) flag=1。 c1(m+1:n)=c1(n:1:m+1)。 end end end end sum1=0。 for i=1:L1 sum1=sum1+a(c1(i),c1(i+1))。 end if sum1sum sum=sum1。 circle=c1。 end circle,sum