圖論及其應用(14)

1、1本次課主要內(nèi)容本次課主要內(nèi)容(一一)、度極大非哈密爾頓圖、度極大非哈密爾頓圖(二二)、TSP問題問題度極大非哈密爾頓圖與度極大非哈密爾頓圖與TSP問題問題2 1、定義、定義(一一)、度極大非哈密爾頓圖、度極大非哈密爾頓圖 定義定義1 圖圖G稱為度極大非稱為度極大非H圖，如果它的度不弱圖，如果它的度不弱于其它非于其它非H圖。圖。 2、C m,n圖圖 定義定義2 對于對于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 對

2、于對于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度弱于某個度弱于某個C Cm,nm,n圖。圖。 證明：證明： 設設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單圖的特征：單圖的特征：Cm,n圖族中圖族中每個圖都是某個每個圖都是某個n階非階非H單圖的極圖。單圖的極圖。5 (2) 定理的條件是充分條件而非必要條件。定理的條件是充分條件而非必要條件。 例如：當例如：當n=5時，其度極大非時，其度極大非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 推論推論 設設G是是n階單圖。若階單圖。若n33且且1()12nE G7 則則G是是H圖；并且，具有圖；并且，具有n個頂點個頂點 條邊

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

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

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

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

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

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

11、閉包是完全圖，求該圖的H圈。圈。 該方法是基于如下一個事實：該方法是基于如下一個事實： 在閉包算法中，在閉包算法中，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在上，使得 若不然，設若不然，設dGk(u0)=r,那么在那么在Gk中，至少有中，至少有r個頂點

12、與個頂點與v0不鄰接，則不鄰接，則dGk(v0)(n-1)-r n-r，這樣與，這樣與u0，v0在在Gk中度和大于等于中度和大于等于n矛盾！矛盾！ 上面結(jié)論表明：可以從上面結(jié)論表明：可以從Ck+1中去掉中去掉u0v0而得到新的而得到新的H圈，圈，實現(xiàn)實現(xiàn)H圈的邊交換。圈的邊交換。 由此，我們設計算法如下：由此，我們設計算法如下：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中任意取出一個中任意取出一個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) 設設ek=u0v0 Ck, 令令Gk-1=Gk-ek; 求求Ck中兩個相鄰點中兩個相鄰點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圈。圈。 復雜性分析：復雜性分析： 一共進行一共進行N次循環(huán)，每次循環(huán)運算量主要在次循環(huán)，每次循環(huán)運算量主要在3),找滿足要求

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

15、術等。法、最近插值法、貪婪算法和邊交換技術等。 在賦權圖中求最小在賦權圖中求最小H圈是圈是NP難問題。理論上也已經(jīng)難問題。理論上也已經(jīng)證明：不存在多項式時間近似算法，使相對誤差小于或等證明：不存在多項式時間近似算法，使相對誤差小于或等于某個固定的常數(shù)于某個固定的常數(shù), ,即便是即便是=1000也是如此。也是如此。 下面介紹邊交換技術。下面介紹邊交換技術。21 1、邊交換技術、邊交換技術 (1)、在賦權完全圖中取一個初始、在賦權完全圖中取一個初始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 采用邊交換技術求下賦權完全圖的一個最優(yōu)采用邊交換技術求下賦權完全圖的一個最優(yōu)H圈。圈。13221705651607835365168576861TPePaNYMCL23 解：取初始圈為：解：取初始圈為：132156603651TPePaNYMCL278132170603651TPePaNYMCL27824132170353651TPePaNYMCL251132170356856TPePaNYMCL

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

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