圖論及其應(yīng)用(14)

1、1本次課主要內(nèi)容本次課主要內(nèi)容(一一)、度極大非哈密爾頓圖、度極大非哈密爾頓圖(二二)、TSP問(wèn)題問(wèn)題度極大非哈密爾頓圖與度極大非哈密爾頓圖與TSP問(wèn)題問(wèn)題2 1、定義、定義(一一)、度極大非哈密爾頓圖、度極大非哈密爾頓圖 定義定義1 圖圖G稱為度極大非稱為度極大非H圖，如果它的度不弱圖，如果它的度不弱于其它非于其它非H圖。圖。 2、C m,n圖圖 定義定義2 對(duì)于對(duì)于1 m n/2 ,C m n/2 ,C m,nm,n圖定義為：圖定義為：,2()m nmmnmCKKK 例如，作出例如，作出C1,5與與C2,53 3、Cm,n的性質(zhì)的性質(zhì)1K1K3KC1,52K2K1KC2,5 引理引理1 對(duì)

2、于對(duì)于1mn/2m|S|=m,(G-S)=m+1|S|=m,所以，所以，由由H H圖的性質(zhì)知，圖的性質(zhì)知，G G是非是非H H圖。圖。 4、度極大非度極大非H圖的特征圖的特征4 定理定理1 (Chvtal,1972) 若若G是是n33的非的非H H單圖，則單圖，則G G度弱于某個(gè)度弱于某個(gè)C Cm,nm,n圖。圖。 證明：證明： 設(shè)設(shè)G是度序列為是度序列為 (d1,d2,dn)的非的非H單圖，單圖，且且d1d2dn,n33。 由度序列判定法：存在由度序列判定法：存在mn/2,使得使得dmm,m,且且d dn-mn-mn-m.n-m.于是，于是，G G的度序列必弱于如下序列：的度序列必弱于如下序

3、列：2( ,.,1,1,.,1,1,1,.,1mnmmm mm nmnmnmnnn 而上面序列正好是圖而上面序列正好是圖Cm,n的度序列。的度序列。 注注： (1) 定理定理1刻畫了非刻畫了非H單圖的特征：?jiǎn)螆D的特征：Cm,n圖族中圖族中每個(gè)圖都是某個(gè)每個(gè)圖都是某個(gè)n階非階非H單圖的極圖。單圖的極圖。5 (2) 定理的條件是充分條件而非必要條件。定理的條件是充分條件而非必要條件。 例如：當(dāng)例如：當(dāng)n=5時(shí)，其度極大非時(shí)，其度極大非H圖族是：圖族是：C1,5與與C2,51K1K3KC1,52K2K1KC2,5 C1,5的度序列是：的度序列是：(1,3,3,3,4), C2,5的度序列是的度序列是

4、(2,2,2,4,4)。 而而5階圈階圈C5的度序列是的度序列是: (2,2,2,2,2),它度弱于它度弱于C2,5,但是但是C5是是H圖。圖。6 (3) 如果如果n階單圖階單圖G度優(yōu)于于所有的度優(yōu)于于所有的Cm,n圖族，則圖族，則G是是H圖。圖。 G的度序列是的度序列是(2,3,3,4,4),優(yōu)于優(yōu)于C1,5的度序列的度序列 (1,3,3,3,4)和和C2,5的度序列的度序列 (2,2,2,4,4)。所以可以斷。所以可以斷定定G是是H圖。圖。 例如：例如：G 推論推論 設(shè)設(shè)G是是n階單圖。若階單圖。若n33且且1()12nE G7 則則G是是H圖；并且，具有圖；并且，具有n個(gè)頂點(diǎn)個(gè)頂點(diǎn) 條邊

5、條邊的非的非H圖只有圖只有C1,n以及以及C2,5.112n 證明證明: (1) 先證明先證明G是是H圖。圖。 若不然，由定理若不然，由定理1，G度弱于某個(gè)度弱于某個(gè)Cm,n,于是有：于是有：2,1()()(2)(1)(1)2111(1)(2)(1)(21)2211.2m nE GE Cmnmnmm mnmmmnmn 這與條件矛盾！所以這與條件矛盾！所以G是是H圖。圖。8 (2) 對(duì)于對(duì)于C1,n,有：有： 除此之外，只有當(dāng)除此之外，只有當(dāng)m=2且且n=5時(shí)有：時(shí)有：1,1()()1.2nnE GE C 這就證明了這就證明了(2)。,1()()1.2m nnE GE C 注：推論的條件是充分而

6、非必要的。注：推論的條件是充分而非必要的。 例如：在例如：在C1,7的任意不相鄰頂點(diǎn)間連一邊后可得的任意不相鄰頂點(diǎn)間連一邊后可得H圖：圖：9 但是，在下圖中，盡管但是，在下圖中，盡管C2,7+uv的邊數(shù)不滿足推的邊數(shù)不滿足推論不等式，可它是論不等式，可它是H圖。圖。C1,7+eeuvC2,7+uv10 例例1 設(shè)設(shè)G是度序列為是度序列為(d1,d2,dn)的非平凡單圖，且的非平凡單圖，且d1d2dn。證明：若。證明：若G不存在小于不存在小于(n+1)/2的正的正整數(shù)整數(shù)m，使得：，使得：dmm且且dn-m+1|S|=13.-S)|S|=13. 故，老鼠最后不能到達(dá)中心點(diǎn)。故，老鼠最后不能到達(dá)中

7、心點(diǎn)。13 例例3 對(duì)對(duì)m條邊的條邊的n階圖階圖G，若，若G的每?jī)蓚€(gè)頂點(diǎn)都由的每?jī)蓚€(gè)頂點(diǎn)都由一條一條H路連接著，稱路連接著，稱G是哈密爾頓連通圖。是哈密爾頓連通圖。 (1) 證明：若證明：若G是是H連通圖且連通圖且n4,4,則則1(31)2mn (2) 對(duì)于對(duì)于n4,4,構(gòu)造一個(gè)構(gòu)造一個(gè)H H連通圖連通圖G,G,使得：使得：1(31)2mn證明：證明： (1) 可以證明，可以證明，(G)3.(G)3.于是有：于是有：1(31)2mn事實(shí)上事實(shí)上,若存在若存在v，有，有d(v)=2,設(shè)設(shè)v1與與v2分別是分別是v的兩個(gè)的兩個(gè)鄰接點(diǎn)，則由鄰接點(diǎn)，則由n44知，不存在知，不存在v v1 1為起點(diǎn)為起

8、點(diǎn)v v2 2為終點(diǎn)的為終點(diǎn)的H H路，與條件矛盾。路，與條件矛盾。14 (2) 下面下面構(gòu)造一個(gè)構(gòu)造一個(gè)H H連通圖連通圖G,G,使得：使得：1(31)2mnn為偶數(shù)時(shí)為偶數(shù)時(shí)n為奇數(shù)時(shí)為奇數(shù)時(shí)15 例例4 寫出下列問(wèn)題的一個(gè)好算法：寫出下列問(wèn)題的一個(gè)好算法： (1) 構(gòu)作一個(gè)圖的閉包；構(gòu)作一個(gè)圖的閉包； (2) 若某圖的閉包是完全圖，求該圖的若某圖的閉包是完全圖，求該圖的H圈。圈。 解：解：(1) 構(gòu)作一個(gè)圖的閉包。構(gòu)作一個(gè)圖的閉包。 根據(jù)圖的閉包定義，構(gòu)作一個(gè)圖的閉包，可以通過(guò)不斷在根據(jù)圖的閉包定義，構(gòu)作一個(gè)圖的閉包，可以通過(guò)不斷在度和大于等于度和大于等于n的非鄰接頂點(diǎn)對(duì)間添邊得到。據(jù)此

9、設(shè)計(jì)算法的非鄰接頂點(diǎn)對(duì)間添邊得到。據(jù)此設(shè)計(jì)算法如下：如下： 圖的閉包算法：圖的閉包算法： 1) 令令G0=G ,k=0; 2) 在在Gk中求頂點(diǎn)中求頂點(diǎn)u0與與v0，使得：，使得：00()()m ax()( )()kkkkGGGGkdudvdudvuvE G16 3) 如果如果 ，則轉(zhuǎn)，則轉(zhuǎn)4);否則，停止，此時(shí)否則，停止，此時(shí)得到得到G的閉包；的閉包；00()()kkGGdudvn 4) 令令Gk+1=Gk+u0v0, k=k+1,轉(zhuǎn)轉(zhuǎn)2). 復(fù)雜性分析：在第復(fù)雜性分析：在第k次循環(huán)里，找到點(diǎn)次循環(huán)里，找到點(diǎn)u0與與v0，要做如下運(yùn)，要做如下運(yùn)算算: (a) 找出所有不鄰接點(diǎn)對(duì)找出所有不鄰接

10、點(diǎn)對(duì)-需要需要n(n-1)/2次比較運(yùn)算；次比較運(yùn)算；(b) 計(jì)算不鄰接點(diǎn)對(duì)度和計(jì)算不鄰接點(diǎn)對(duì)度和-需要做需要做n(n-1)/2-m(G)次加法運(yùn)算次加法運(yùn)算;(c ),選出度和最大的不鄰接點(diǎn)對(duì)選出度和最大的不鄰接點(diǎn)對(duì)-需要需要n(n-1)/2-m(G)次比較運(yùn)算。次比較運(yùn)算。所以，總運(yùn)算量為：所以，總運(yùn)算量為：211(1)2(1)()()22n nn nmGOn 所以，上面的閉包算法是好算法。所以，上面的閉包算法是好算法。17 方法：采用邊交換技術(shù)把閉包中的一個(gè)方法：采用邊交換技術(shù)把閉包中的一個(gè)H圈逐步轉(zhuǎn)圈逐步轉(zhuǎn)化為化為G的一個(gè)的一個(gè)H圈。圈。 (2) 若某圖的閉包是完全圖，求該圖的若某圖的

11、閉包是完全圖，求該圖的H圈。圈。 該方法是基于如下一個(gè)事實(shí)：該方法是基于如下一個(gè)事實(shí)： 在閉包算法中，在閉包算法中，Gk+1=Gk+u0v0, u0與與v0在在Gk中不鄰接，中不鄰接，且度和大于等于且度和大于等于n. 如果在如果在Gk+1中有中有H圈圈Ck+1如下：如下：100120(,.,)knCu v vvuu0v0v1vivi+1vn-3vn-2Ck+118 我們有如下斷言：我們有如下斷言：u0v0v1vivi+1vn-3vn-2Ck+111001,()kiiiikCv vu v v vE G在上，使得 若不然，設(shè)若不然，設(shè)dGk(u0)=r,那么在那么在Gk中，至少有中，至少有r個(gè)頂點(diǎn)

12、與個(gè)頂點(diǎn)與v0不鄰接，則不鄰接，則dGk(v0)(n-1)-r n-r，這樣與，這樣與u0，v0在在Gk中度和大于等于中度和大于等于n矛盾！矛盾！ 上面結(jié)論表明：可以從上面結(jié)論表明：可以從Ck+1中去掉中去掉u0v0而得到新的而得到新的H圈，圈，實(shí)現(xiàn)實(shí)現(xiàn)H圈的邊交換。圈的邊交換。 由此，我們?cè)O(shè)計(jì)算法如下：由此，我們?cè)O(shè)計(jì)算法如下：19 1)在閉包構(gòu)造中，將加入的邊依加入次序記為在閉包構(gòu)造中，將加入的邊依加入次序記為ei (1iN),iN),這里，這里，N=n(n-1)/2-m(G).N=n(n-1)/2-m(G).在在G GN N中任意取出一個(gè)中任意取出一個(gè)H H圈圈C CN N, ,令令k=N

13、;k=N; 2) 若若ek不在不在Ck中，令中，令Gk-1=Gk-ek, Ck-1=Ck; 否則轉(zhuǎn)否則轉(zhuǎn)3); 3) 設(shè)設(shè)ek=u0v0 Ck, 令令Gk-1=Gk-ek; 求求Ck中兩個(gè)相鄰點(diǎn)中兩個(gè)相鄰點(diǎn)u與與v使使得得u0,v0,u,v依序排列在依序排列在Ck上，且有：上，且有：uu0,vv0 E(Gk-1),令：令： 10000,kkCCu v uvuu vv 4) 若若k=1,轉(zhuǎn)轉(zhuǎn)5)；否則，令；否則，令k=k-1,轉(zhuǎn)轉(zhuǎn)2); 5) 停止。停止。C0為為G的的H圈。圈。 復(fù)雜性分析：復(fù)雜性分析： 一共進(jìn)行一共進(jìn)行N次循環(huán)，每次循環(huán)運(yùn)算量主要在次循環(huán)，每次循環(huán)運(yùn)算量主要在3),找滿足要求

14、找滿足要求的鄰接頂點(diǎn)的鄰接頂點(diǎn)u與與v,至多至多n-3次判斷。所以總運(yùn)算量：次判斷。所以總運(yùn)算量：N(n-3),屬屬于好算法。于好算法。20(二二)、TSP問(wèn)題問(wèn)題 TSP問(wèn)題即旅行售貨員問(wèn)題，是應(yīng)用圖論中典型問(wèn)題問(wèn)題即旅行售貨員問(wèn)題，是應(yīng)用圖論中典型問(wèn)題之一。問(wèn)題提法為：一售貨員要到若干城市去售貨，每座之一。問(wèn)題提法為：一售貨員要到若干城市去售貨，每座城市只經(jīng)歷一次，問(wèn)如何安排行走路線，使其行走的總路城市只經(jīng)歷一次，問(wèn)如何安排行走路線，使其行走的總路程最短。程最短。 已經(jīng)使用過(guò)的近似算法很多，如遺傳算法、最鄰近算已經(jīng)使用過(guò)的近似算法很多，如遺傳算法、最鄰近算法、最近插值法、貪婪算法和邊交換技

15、術(shù)等。法、最近插值法、貪婪算法和邊交換技術(shù)等。 在賦權(quán)圖中求最小在賦權(quán)圖中求最小H圈是圈是NP難問(wèn)題。理論上也已經(jīng)難問(wèn)題。理論上也已經(jīng)證明：不存在多項(xiàng)式時(shí)間近似算法，使相對(duì)誤差小于或等證明：不存在多項(xiàng)式時(shí)間近似算法，使相對(duì)誤差小于或等于某個(gè)固定的常數(shù)于某個(gè)固定的常數(shù), ,即便是即便是=1000也是如此。也是如此。 下面介紹邊交換技術(shù)。下面介紹邊交換技術(shù)。21 1、邊交換技術(shù)、邊交換技術(shù) (1)、在賦權(quán)完全圖中取一個(gè)初始、在賦權(quán)完全圖中取一個(gè)初始H圈圈C=v1v2,vnv1； (2)、如果存在下圖中紅色邊，、如果存在下圖中紅色邊，且且w(vivi+1)+ w(vjvj+1)w(vivj)+ w(

16、vi+1vj+1),則把則把C修改為：修改為： C1=v1v2,vivjvi+1vj+1,vnv1v1v2viVi+1vjvj+1vn初始初始H圈圈Cv1v2viVi+1vjvj+1vn22 例例5 采用邊交換技術(shù)求下賦權(quán)完全圖的一個(gè)最優(yōu)采用邊交換技術(shù)求下賦權(quán)完全圖的一個(gè)最優(yōu)H圈。圈。13221705651607835365168576861TPePaNYMCL23 解：取初始圈為：解：取初始圈為：132156603651TPePaNYMCL278132170603651TPePaNYMCL27824132170353651TPePaNYMCL251132170356856TPePaNYMCL

17、251 于是，求出一個(gè)近似最優(yōu)解為：于是，求出一個(gè)近似最優(yōu)解為：W(H) =192 注：為了得到進(jìn)一步的優(yōu)解，可以從幾個(gè)不同的初始圈注：為了得到進(jìn)一步的優(yōu)解，可以從幾個(gè)不同的初始圈開(kāi)始，通過(guò)邊交換技術(shù)得到幾個(gè)近似最優(yōu)解，然后從中選取開(kāi)始，通過(guò)邊交換技術(shù)得到幾個(gè)近似最優(yōu)解，然后從中選取一個(gè)近似解。一個(gè)近似解。25 2、最優(yōu)、最優(yōu)H圈的下界圈的下界 可以通過(guò)如下方法求出最優(yōu)可以通過(guò)如下方法求出最優(yōu)H圈的一個(gè)下界：圈的一個(gè)下界： (1) 在在G中刪掉一點(diǎn)中刪掉一點(diǎn)v(任意的任意的)得圖得圖G1; (2) 在圖在圖G1中求出一棵最小生成樹(shù)中求出一棵最小生成樹(shù)T; (3) 在在v的關(guān)聯(lián)邊中選出兩條權(quán)值最

18、小者的關(guān)聯(lián)邊中選出兩條權(quán)值最小者e1與與e2. 若若H是是G的最優(yōu)圈，則：的最優(yōu)圈，則：12()( )()()W HW TW eW e26 例如，估計(jì)例例如，估計(jì)例5中最優(yōu)中最優(yōu)H圈的下界圈的下界 解：在解：在G中刪掉點(diǎn)中刪掉點(diǎn)NY,求得求得G-NY的一棵最優(yōu)生成樹(shù)為：的一棵最優(yōu)生成樹(shù)為：5113MC562PaLPeT3521 所以，所以，W(H)122+35+21=178.122+35+21=178.27 例例6 設(shè)設(shè)G是賦權(quán)完全圖，對(duì)所有的是賦權(quán)完全圖，對(duì)所有的x, y, z V(G),滿足三滿足三角不等式：角不等式：W(x y)+ W (y z)W(xz)W(xz) .證明：證明：G中最優(yōu)圈的中最優(yōu)圈的權(quán)最多是權(quán)最多是2W(T)，這里，這里T是是G中一棵最小生成樹(shù)。中一棵最小生成樹(shù)。 證明：設(shè)證明：設(shè)T是是G的一棵最小生成樹(shù)，將的一棵最小生成樹(shù)，將T的每條邊添上的每條邊添上一條平行邊得圖一條平行邊得圖T1,顯然顯然T1是歐拉圖。是歐拉圖。v1v2v3v4v5v6Tv1v2v3v4v5v6T1 設(shè)設(shè)Q是是T1的一個(gè)歐拉環(huán)游：的一個(gè)歐拉環(huán)游：Q=v1v2.vkv128 則：則：W(T1)=W(Q)=2W(T) 現(xiàn)在，從現(xiàn)在，從Q的第三點(diǎn)開(kāi)始，刪掉與前面的重復(fù)頂點(diǎn)，得的第三點(diǎn)開(kāi)始，刪掉與前面的重