歐拉圖及哈密頓圖.ppt

1、第二章 第一節(jié) 歐拉圖(1),定義1 給定無孤立結(jié)點(diǎn)的無向圖G,經(jīng)過圖G的 每邊一次且僅一次的跡為一條歐拉路.經(jīng)過圖 G的每邊一次且僅一次的回為一條歐拉回路. 說明:(1)由定義,含有歐拉路(回)的圖顯然是 連通的; (2)歐拉路是跡(邊互不重復(fù)),但不是嚴(yán)格意 義上的路. 定理1連通圖G具有歐拉回路當(dāng)且僅當(dāng)其每個(gè) 頂點(diǎn)的度數(shù)為偶數(shù).,歐拉路(2),證明:必要性:不妨設(shè)C是從頂點(diǎn)x1開始的無向圖G 的一條歐拉回路.對該回路中的任何一個(gè)內(nèi)部點(diǎn)xi 而言,每出現(xiàn)一次,其度數(shù)必增加2,對x1來講,回路 最后在該點(diǎn)結(jié)束,當(dāng)然其度數(shù)也為偶數(shù). 充分性:若G是連通無向圖,作G的一條最長回C,并 假設(shè)C不是

2、歐拉回路.這樣,在C中必存在xkV(C)及關(guān)聯(lián)xk的邊e=xk,x1 C;又deg( x1)為偶數(shù),所以存在e1=x1,x2 ,e2=x2,x3, en=xn,xk,這樣在G中又找到一條回C,若G=CUC,則結(jié)論成立,反之,繼續(xù)尋找,總可以找到符合條件的回.,第二章 歐拉圖與哈密頓圖(2),定理2 連通圖G具有歐拉路而無歐拉回路,當(dāng)且僅當(dāng)G恰有兩個(gè)奇數(shù)度頂點(diǎn). 證:必要性:設(shè)連通圖G從頂點(diǎn)a到頂點(diǎn)b有歐拉路C,但不是歐拉回路.在歐拉路C中,除第一邊和最后一邊外,每經(jīng)過G中頂點(diǎn)xi(包括a和b),都為頂點(diǎn)xi貢獻(xiàn)2度,而C的第一邊為a貢獻(xiàn)1度,C的最后一條邊為b貢獻(xiàn)1度.因此,a和b的度數(shù)均為奇

3、數(shù),其余結(jié)點(diǎn)度數(shù)均為偶數(shù).,充分性:設(shè)連通圖G恰有兩個(gè)奇數(shù)度結(jié)點(diǎn), 不妨設(shè)為a和b,在圖G中添加一條邊e=a,b 得G,則G的每個(gè)結(jié)點(diǎn)的度數(shù)均為偶數(shù),因 而G中存在歐拉回路,故G中必存在歐拉路. 定義2 給定有向圖D,經(jīng)過D中每邊一次且僅 一次的有向跡稱為D的有向歐拉路.經(jīng)過D中 每邊一次且僅一次的有向閉跡(回),稱為有 向歐拉回路.,第二章 歐拉圖與哈密頓圖(3),定理3 具有弱連通性的有向圖G具有有向歐拉 回路,當(dāng)且僅當(dāng)G的每個(gè)結(jié)點(diǎn)的入度等于出度. 具有弱連通性的有向圖G具有有向歐拉路,當(dāng)且僅當(dāng)在G中,一個(gè)結(jié)點(diǎn)的入度比出度大1,另一個(gè)結(jié)點(diǎn)的入度比出度小1,而其余每個(gè)結(jié)點(diǎn)的入度等于出度. 定

4、義3 含有歐拉回路的無向連通圖與含有向歐 拉回路的弱連通有向圖,統(tǒng)稱為歐拉圖.,求Euler圖的Euler回路的Fleury算法.,(1)任意選取一個(gè)頂點(diǎn)v0,置W0=v0; (2)假定跡(若是有向圖,則是有跡) Wi=v0e1v1eivi已經(jīng)選出,則 用下列方法從E(G)-e1,e2,ei中取ei+1; (a)ei+1與vi關(guān)聯(lián)(若是有向圖, ei+1 以vi為起點(diǎn)) (b)除非沒有別的邊可選擇, ei+1不是 Gi=G- e1,e2,ei的割邊. (3)當(dāng)(2)不能執(zhí)行時(shí),停止.否則讓i+1 i,轉(zhuǎn) (2).,定理4若G是Euler圖,則Fleury算法終止時(shí)得到的跡是Euler回路。,定

5、義1 給定無向圖G,若存在一條路經(jīng)過圖G的每個(gè)結(jié)點(diǎn)一次且僅一次,這條路稱為哈密頓路.若存在一條閉路經(jīng)過圖G的每個(gè)結(jié)點(diǎn)一次且僅一次,這條閉路稱為哈密頓回路. 定義2給定有向圖D,若存在一條路經(jīng)過圖G的每個(gè)結(jié)點(diǎn)一次且僅一次,這條路稱為哈密頓有向路.若存在一條閉路經(jīng)過圖G的每個(gè)結(jié)點(diǎn)一次且僅一次,這條有向閉路稱為哈密頓有向回路.,第二節(jié) 哈密頓圖(1),第二節(jié) 哈密頓圖(1),定義3 具有哈密頓回路的無向圖與具有哈密頓有向回路的有向圖,統(tǒng)稱為哈密頓圖. 例1對于完全圖Kn(n3),由于Kn中任意兩個(gè)頂點(diǎn)之間都有邊,從Kn的某一頂點(diǎn)開始,總可以遍歷其余節(jié)點(diǎn)后,再回到該結(jié)點(diǎn),因而Kn(n3)是哈密頓圖.

6、說明:判斷一個(gè)給定的圖是否為哈密頓圖,是圖論 中尚未解決的難題之一,下面介紹若干必要條件 和充分條件.,第二節(jié) 哈密頓圖(2),定理1設(shè)任意n(n3)階圖G,對所有不同非鄰接頂 點(diǎn)x和y,若deg(x)+deg(y) n,則G是哈密頓圖. 證明:僅就G是無向圖加以證明.假設(shè)定理不成立. 則存在一個(gè)階為n(n3),滿足定理?xiàng)l件且邊數(shù)最 多的非哈密頓圖,即G是一個(gè)非哈密頓圖且對G 的任何兩個(gè)非鄰接點(diǎn)x1和x2,圖G+邊x1,x2是哈 密頓圖.,因?yàn)閚3,所以G不是完全圖.設(shè)u和v是G的兩 個(gè)頂點(diǎn).因此G+邊u,v是哈密頓圖.且G+邊u,v 是哈密頓回路一定包含邊u,v.故在G中存在一 條uv路T=

7、u1u2un(u=u1,v=un)包含G中每個(gè)頂點(diǎn). 若u1,uiE(G)(2in),則ui-1,unE(G).否則 u1uiui+1unui-1ui-2u1是G的一個(gè)哈密頓回路,故 對u2,u3,un-1中每一個(gè)鄰接到u1的頂點(diǎn)存在一 個(gè)u1,u3,un-1中與un不鄰接的頂點(diǎn),故 deg(un) n-1-deg(u1),所以deg(u)+deg(v) n-1 矛盾.,第二節(jié) (3),定理2 設(shè)u和v是n階圖G的不同非鄰接點(diǎn),且deg(u) +deg(v)n, 則G+邊u,v是哈密頓圖當(dāng)且僅當(dāng)哈密頓圖. 定義4 給定n階圖G,若將圖G度數(shù)之和至少是n的非 鄰接點(diǎn)用一條邊連接起來得圖G,對圖G

8、重復(fù)上述 過程,直到不再有這樣的結(jié)點(diǎn)對存在為止,所得到的 圖,稱為是原圖G的閉包,記作C(G). 定理3 一個(gè)圖是哈密頓圖當(dāng)且僅當(dāng)它的閉包是哈密 頓圖.,定理4 設(shè)G是階至少為3的圖,如果G的閉包是完全圖, 則G是哈密頓圖. 定理5如果G是一個(gè)n階(n3)任意圖,且對G的每個(gè)頂 點(diǎn)x,都有deg(x) n/2,則G是哈密頓圖. 說明:由哈密頓圖的定義可知,哈密頓圖有向圖必是 強(qiáng)連通的,哈密頓無向圖必?zé)o割點(diǎn).,8.哈密頓圖(4),定理5 若G是一個(gè)哈密頓圖,則對于V(G)的每個(gè)非空真子集S, 其中W(G-S)為G-S的分支數(shù). 證明:設(shè)C是G的一個(gè)哈密頓回路,則對于V(G)的任意一個(gè)非空真子集S

9、,均成立 由于C-S為G-S的一個(gè)生成子圖,因而W(G-S)W(C-S),故,9.哈密頓圖(5),說明:定理6只是一個(gè)必要條件,如下的皮特森圖,盡 管有 但它不是哈密頓圖.,10.哈密頓圖(6),應(yīng)用定理5.若G是一個(gè)n(n3)階任意圖,且對G的每個(gè)頂點(diǎn)x,都有deg(x) n/2,則G是哈密頓圖. 例1.11個(gè)學(xué)生要共進(jìn)晚餐,他們將坐成一個(gè)圓桌,計(jì)劃要求每次晚餐上,每個(gè)學(xué)生有完全不同的鄰座.這樣能共進(jìn)晚餐幾次. 分析:如何將該問題轉(zhuǎn)化成圖論中的相關(guān)問題.實(shí)際上,可以這樣來構(gòu)造一個(gè)圖,即以每個(gè)學(xué)生看作圖的頂點(diǎn),以學(xué)生的鄰座關(guān)系作為圖的的邊,11.哈密頓圖(7),這樣學(xué)生每次進(jìn)餐的就坐方式就對應(yīng)

10、一個(gè)哈密頓 回路.兩次進(jìn)餐中,每個(gè)學(xué)生有完全不同的鄰座對應(yīng)著 兩個(gè)沒有公共邊的哈密頓回路.因?yàn)槊總€(gè)學(xué)生都可以與 其余學(xué)生鄰座,故問題轉(zhuǎn)化為在圖K11中找出所有沒有 公共邊的哈密頓回路的個(gè)數(shù). K11中共有 條邊,而K11中每條哈密頓回路的 長度為11,因此K11中最多有55/11=5條沒有公共邊的哈 密頓回路,構(gòu)造方法為:設(shè)第一條哈密頓回路為 (1,2,3,11,1),將1固定在圓心,其余固定在圓周上,如圖 (1)所示,然后將圖的頂點(diǎn)旋轉(zhuǎn)i 3600/10(i=1,2,3,4),從 而就得到另外4個(gè)哈密頓回路.,12.哈密頓圖(8),1 (3,2,4,6)5 7(5,3,2,4) (2,4,6

11、,8 )3 9(7,5,3,2) (4,6,8,10)2 11(9,7,5,3) ( 6,8,10,11)4 10 (11,9,7,5) (8,10,11,9)6 8(10,11,9,7) 圖1,例2.有n個(gè)人,任意兩個(gè)人合起來認(rèn)識其余的n-2個(gè)人,證明:當(dāng)n4時(shí),這n個(gè)人能站成一圈,使每一個(gè)人的兩旁站著自己認(rèn)識的人. 證明:構(gòu)造簡單無向圖G=,其中V中的n個(gè)結(jié)點(diǎn)表示這n個(gè)人,G中的邊表示他們間的認(rèn)識關(guān)系. 對u,vV(G),顯然d(u)+d(v)n-2,即其余n-2個(gè)結(jié)點(diǎn)必與u或v鄰接. (1)若u,v相鄰,則d(u)+d(v)2+n-2=n;,(2)若u與v不相鄰,如果d(u)+d(v)=

12、n-2,則 V-u,v中恰有n-2個(gè)結(jié)點(diǎn)(n4,故V-u,v),其中每個(gè)結(jié)點(diǎn)只能與u,v中的一個(gè)結(jié)點(diǎn)相鄰.不妨設(shè)aV-u,v,且a與u相鄰,a與v不相鄰,此時(shí)對于結(jié)點(diǎn)a與u來說,都不與v相鄰,這與已知矛盾,所以 d(u)+d(v)n-2,即d(u)+d(v)n-1.,若d(u)+d(v)=n-1,由于n4,在結(jié)點(diǎn)集V-u,v中至少有兩個(gè)結(jié)點(diǎn)a和b,其中a與u和v都相鄰,而b只與u和v中的一個(gè)相鄰,不妨設(shè)b與u相鄰,此時(shí)v與b和u都不相鄰, 顯然與已知矛盾,因此d(u)+d(v)n-1,即 d(u)+d(v)n 綜上所述,對u,vV(G),都有d(u)+d(v)n, 因此G中存在一條哈密頓回路,

13、從而這n個(gè)人能站成一圈,使得每一個(gè)人的兩旁站著自己認(rèn)識的人.,第三節(jié) 并行運(yùn)算圖論模型與格雷碼 串行計(jì)算機(jī):傳統(tǒng)的計(jì)算機(jī)一般稱為串行計(jì)算機(jī),即執(zhí)行程序是一次完成一個(gè)操作.實(shí)際上,為解決問題而寫的算法都設(shè)計(jì)成一次執(zhí)行一步,這樣的算法稱為串行的.到目前為止,幾乎所有書本描述的算法都是串行的. 然而在有些問題上,如氣象模擬,醫(yī)學(xué)圖像及密碼分析等許多高強(qiáng)度計(jì)算問題,即使在超計(jì)算機(jī)上,也不能通過串行操作在合理時(shí)間范圍內(nèi)解決;而且對計(jì)算機(jī)的運(yùn)行速度來講,還,存在著物理上的限制,即總有問題不能用串行操作在合理長度的時(shí)間之內(nèi)解決.另外,隨著硬件價(jià)格的下降,使得制造并行計(jì)算機(jī)成為可能. 并行計(jì)算機(jī)就是使用多個(gè)處

14、理器實(shí)現(xiàn)在同一時(shí)間執(zhí)行多條指令. 并行算法就是把問題分成可同時(shí)解決的若干子問題,其單個(gè)指令流控制著算法的執(zhí)行,包括把子問題送到不同的處理器,以及把子問題的輸入和輸出定向到適當(dāng)?shù)奶幚砥?,采用并行處理,一個(gè)處理器需要另一個(gè)處理器產(chǎn)生的輸出.因此.處理器需要互聯(lián).用圖來描述帶有多重處理器的計(jì)算機(jī)里處理器的互聯(lián)網(wǎng)絡(luò),是一種十分便利的方法,即所謂的并行運(yùn)算圖論模型.在第一章中介紹的n維立方體Qn中,有2n(n0)個(gè)處理器,每個(gè)處理器有自己的內(nèi)存,在一個(gè)單位時(shí)間內(nèi),n維立方體中的每個(gè)處理器同時(shí)處理一條指令,然后與相鄰的處理器通信.若一個(gè)處理器要與一個(gè)不相鄰的處理器通信,第一個(gè)處理器要發(fā)送一些信息,這包括

15、路徑信息及接受者的最終目的地.當(dāng)然這要花費(fèi)數(shù)個(gè)時(shí)間段.,許多計(jì)算機(jī)已經(jīng)根據(jù)n維立方體Qn的模型制造和運(yùn)行.下面將證明n維立方體Qn中存在哈密頓回路,為此先介紹格雷碼.格雷碼是以弗蘭克.格雷的名字命名的,在20世紀(jì)40年代,他為了把傳送數(shù)字信號過程中的錯(cuò)誤的影響降到最低而發(fā)現(xiàn)的.下面介紹格雷碼的有關(guān)定義和構(gòu)造定理.,定義1 n 階格雷碼是序列s1,s2,st,(t=2n), 其中每個(gè)si是n位二進(jìn)制串，滿足 （1）每個(gè)n位二進(jìn)制串都出現(xiàn)在序列中； （2） si與si+1只有一位不同； （3） st和s1只有一位不同。,定理1令G1表示序列，由Gn-1根據(jù)以規(guī)則來定義Gn: （1）令 表示序列Gn

16、-1的逆序； （2）令 表示在序列G的每個(gè)成員前加0所得的序列； （3）令 表示在序列 的每個(gè)成員前加1所得的序列； （4）令G為由 后加上 組成的序列。,例1從G1開始構(gòu)造G3。,推論.對于每個(gè)正整數(shù)n2，n維立方體都包含一個(gè)哈密頓回路。,0000,0001,1001,1000,0010,0011,1011,1010,0110,0111,1111,1110,0100,0101,1101,1100,例2 證明任一個(gè)有限集合的全部子集可以這樣排列順序使任何相鄰的兩個(gè)子集僅相差一個(gè)元素. 證明:設(shè)此有限集為A=a1,a2,an,用長為n的二進(jìn)制數(shù)列對應(yīng)它的2n個(gè)子集:當(dāng)且僅當(dāng)子集中含有A的第i個(gè)元

17、素時(shí),數(shù)列的第二個(gè)數(shù)碼為1,否則為0.以這2n個(gè)數(shù)列為頂點(diǎn),當(dāng)且僅當(dāng)數(shù)列僅一個(gè)同位數(shù)碼相異時(shí),該兩頂點(diǎn)間連一邊,得到一個(gè)圖G.顯然圖G為n維立方體.而n維立方體為哈密頓圖.按照一條哈密頓回路的順序排列對應(yīng)子集即可.,第四節(jié) 算法的時(shí)間復(fù)雜性,一個(gè)算法是有限指令的集合 有限性:任何算法都會在有限條指令執(zhí)行完 后結(jié)束。 確定性:算法的每一步有精確的定義。 輸入有零個(gè)或多個(gè)輸入，且輸入取自特定 的對象集合。,輸出 :有一個(gè)或多個(gè)輸出與輸入有某種特定關(guān)系。 唯一性 :每一步執(zhí)行后所得到的中間結(jié)果是唯一的，且僅依賴于輸入和先前步驟的結(jié)果.。 通用性:算法適用于一類輸入。 問題是要求回答的提問通常有幾個(gè)參

18、數(shù)它們的值是特定的，取自定義域。,問題的描述:是對參數(shù)進(jìn)行描述，指出其解是滿足什么性質(zhì)的命題。 實(shí)例 :給問題的全體參數(shù)都指定了確定的值便得到一個(gè)問題的實(shí)例。 A是問題P的算法，若算法A對問題P的每個(gè)實(shí)例都給出正確答案。 問題P算法可解，若存在一個(gè)算法解答問題P。,算法分析 是指通過分析得到算法所需的時(shí)間和空間的估計(jì)量。 算法的復(fù)雜度是指執(zhí)行算法所需的時(shí)間和空間的量。,定義1令f和g為從整數(shù)集合或?qū)崝?shù)集合到實(shí)數(shù)集合的函數(shù)，如果存在常數(shù)c和k，使得只要xk就有f(x) cg(x) 則稱f(x)是O(g(x)記為f(x)=O(g(x)讀作f(x)是O(g(x),定理1: 令f(x)=an xn +

19、an-1 xn-1 +a1 x+a0其中a0 、 a1 、 an-1 、 an為實(shí)數(shù)，則f(x)=O(xn) 定理2 設(shè)f1 (x)=O(g1 (x)、 f2 (x)=O(g2 (x) ，則f1 (x) + f2 (x) =O(max(g1 (x)、 g2 (x)）。,定理3 設(shè)f1 (x)=O(g1 (x)、 f2 (x)=O(g2 (x)， 則f1 (x) *f2 (x) =O(g1 (x)* g2 (x)。 例1對于正整數(shù)n，給出n!和logn!的大O估計(jì). 解:n!=1*2*3*nnn,故n!=O(nn), 又logn! lognn =nlogn,所以logn! =O(nlogn).,

20、例2 給出f(n)=3n*logn!+(n2+3)*logn的大O估計(jì),其中n是正整數(shù)。 解:logn!=O(nlogn),故3n*logn!=O(n2logn) 所以f(n)= O(n2logn). 例3 給出f(x)=(x+1)log(x2+1)+3x2的大O估計(jì)。 解:當(dāng)x1時(shí),x2+12x2; 當(dāng)x2時(shí),Log(x2+1)log(2x2) 3logx, 故Log(x2+1)=O(logx),所以(x+1)Log(x2+1)=O(xlogx) 又x1時(shí),xlogx x2,所以f(x)=O(x2).,易處理的，能用多項(xiàng)式最壞情況復(fù)雜性的算法解決的問題，否則稱為不易處理的. P問題:易處理的

21、問題. NP問題：至今沒有找到多項(xiàng)式算法，又不能證明它不存在多項(xiàng)式算法的一類問題. NPC問題：其中任何一個(gè)問題能用一個(gè)多項(xiàng)式時(shí)間最壞情況算法解答的一類問題。,例4 冒泡排序 它把一個(gè)列表排列成升序；相繼地比較相鄰的元素，若它們順序不對，則交換它們。試分析冒泡排序 的最壞時(shí)間 復(fù)雜度。O(n2),第五節(jié) 最短路路問題,1.加權(quán)圖:邊上有數(shù)的圖稱為加權(quán)圖;該數(shù)稱為邊的權(quán)。 2.最短路問題:如何求兩個(gè)結(jié)點(diǎn)之間的最短路. 3.迪克斯曲拉算法:這是荷蘭計(jì)算機(jī)科學(xué)教授Edsger W.Dijkstra(1930-)在1959年發(fā)現(xiàn)的一個(gè)算法.他在1972年獲得計(jì)算機(jī)協(xié)會授予的圖靈獎,這是計(jì)算機(jī)科學(xué)中最具

22、聲望的獎項(xiàng). 迪克斯曲拉算法是求出一個(gè)連通加權(quán)簡單圖中從結(jié)點(diǎn)a到結(jié)點(diǎn)z的最短路.邊i,j的權(quán)(i,j)0,且結(jié)點(diǎn)x的標(biāo)號為L(x),結(jié)束時(shí),L(z)是從x到z的最短路的長度.,4.迪克斯曲拉算法流程,Procedure Dijkstra(G:所有權(quán)為正的加權(quán)連通簡單圖) G帶有頂點(diǎn)a=v0,v1,vn=z和權(quán)w(vi,vj),若vi,vj不是G中的邊,則w(vi,vj)=) For i:=1 to n L(vi):= L(a):=0 S:= 初始化標(biāo)記,a的標(biāo)記為0,其余結(jié)點(diǎn)標(biāo)記為,S是空集 While zS begin u:=不屬于S的L(u)最小的一個(gè)頂點(diǎn) S:=Su For 所有不屬于S

23、的頂點(diǎn)v If L(u)+w(u,v)L(v) then L(v):=L(u)+w(u,v) 這樣就給S中添加帶最小標(biāo)記的頂點(diǎn)并且更新不在S中的頂點(diǎn)的標(biāo)記 End L(z)=從a到z的最短路的長度.,例1.用迪克斯曲拉算法求下圖所示的加權(quán)圖中頂點(diǎn)a與z之間最短路的長度.（見65頁）,定理1 迪克斯曲拉算法求出連通簡單無向圖的中兩點(diǎn)之間的最短路的長度。 定理2 迪克斯曲拉算法使用O(n2)次運(yùn)算（加法和比較）來求出n階連通簡單無向加權(quán)圖中兩個(gè)頂點(diǎn)之間的最短路的長度。 迪克斯曲拉算法可以推廣到求加權(quán)有向圖的最短路。（p68） 定理3 設(shè)有向圖G中不含長度非正的有向圈，并且從點(diǎn)1到其余各點(diǎn)都有有限長

24、的有向路，那么式（2）有唯一有限解。 定理4-5見p69.,Floyd算法,Dijkstra算法只求出一個(gè)特定頂點(diǎn)到其他 各頂點(diǎn)的最短路.但在許多實(shí)際問題中,需求出 任意兩點(diǎn)之間的最短路,如全國各城市之間最 短的航線,選址問題等.Floyd算法可以比較好 地解決這一問題. 為介紹Floyd算法,先定義矩陣的兩種運(yùn)算. 定義1. 已知矩陣A=(aij)ml, B=(bij)ln,規(guī)定 C=AB=(cij)mn, 其中cij=min(ai1+b1j,ai2+b2j,ail+blj).,定義2.已知矩陣A=(aij)mn,B=(bij)mn,規(guī)定 D=AB=(dij)mn,其中dij=min(aij

25、,bij). 可以利用上面定義的運(yùn)算求任意兩點(diǎn)間的 最短距離. 已知n階加權(quán)簡單圖G,設(shè)D=(dij)nn是圖G的 邊權(quán)矩陣即dij=w(i,j) (若G是有向圖,則dij=w), 若結(jié)點(diǎn)i到結(jié)點(diǎn)j無邊相連時(shí),則取dij=. 然后依次計(jì)算出矩陣D2,D3,Dn及S, 其中,D2=DD=(dij2)nn D3=D2 D=(dij3)nn, Dn=Dn-1 D=(dijn)nn S=DD2D3Dn=(Sij)nn 由定義可知,dijk表示從結(jié)點(diǎn)i到結(jié)點(diǎn)j經(jīng)k 邊的路(在有向圖中即為有向路)中的長度最短 者.這就是Floyd算法. 請同學(xué)們分析一下Floyd算法的時(shí)間復(fù)雜度.,例2.利用Floyd算

26、法求下圖中任意兩點(diǎn)間最短有向路的長度.(p71-73),Warshall算法,實(shí)質(zhì)上是考慮經(jīng)過n次結(jié)點(diǎn)轉(zhuǎn)換每一次保留最短路的長度。見P74.,第六節(jié)旅行推銷員問題和中國投遞員問題（NPC問題）一。旅行推銷員問題,（最鄰近算法給出旅行推銷員問題的近似解） 步驟如下 （1）由任意選擇的結(jié)點(diǎn)開始，找出于該結(jié)點(diǎn)鄰近的點(diǎn)，形成一條有邊的初始路。 （2）以表示最新加到這條路上的結(jié)點(diǎn)，從不在路上的所有結(jié)點(diǎn)中選一個(gè)和最靠近的結(jié)點(diǎn)，把連接與這一結(jié)點(diǎn)的邊加到這條路上，重復(fù)這一步驟直到這條路包含圖中所有結(jié)點(diǎn)。,例1 用“最鄰近算法”給出下面加權(quán)圖中有充分小權(quán)的哈密頓路P76.,說明: “最鄰近插入方法”是“最鄰近法”的一種改進(jìn)方法.該方法是在每次迭代中都構(gòu)成一個(gè)閉的旅行路線.求解時(shí),在已經(jīng)建立旅程以外的頂點(diǎn)中,尋找最臨近于旅程中某個(gè)頂點(diǎn)的頂點(diǎn),然后將其插入該旅程中,并使增加的距離盡可能小,當(dāng)全部頂點(diǎn)收入這個(gè)旅程后,就找到了所求的最短哈密頓回路的近似解.