電子科技大學圖論第二次作業(yè)楊春

1、習題四：3.（1）畫一個有Euler 閉跡和Hamilton圈的圖； （2）畫一個有Euler 閉跡但沒有Hamilton圈的圖； （3）畫一個有Hamilton圈但沒有Euler閉跡的圖；（4）畫一個即沒有Hamilton圈也沒有Euler閉跡的圖；解：找到的圖如下：(1) 一個有Euler 閉跡和Hamilton圈的圖；(2) 一個有Euler 閉跡但沒有Hamilton圈的圖；(3) 一個有Hamilton圈但沒有Euler閉跡的圖; (4)一個即沒有Hamilton圈也沒有Euler閉跡的圖.4.設(shè)n階無向簡單圖G有m條邊，證明:若mn-12+2,則G是Hamilton圖。證明: G是

2、H圖。 若不然，因為G是無向簡單圖，則n3,由定理1：若G是n3的非單圖，則G度弱于某個Cm,n.于是有： 這與條件矛盾！所以G是H圖。 8.證明：若G有2k0個奇點，則存在k條邊不重的跡Q1,Q2Qk,使得EG=EQ1EQ2EQ3E(Qk).證明：不失一般性，只就G是連通圖進行證明。設(shè)G=(n, m)是連通圖。令vl，v2，,vk,vk+1,v2k是G的所有奇度點。在vi與vi+k間連新邊ei得圖G*（1ik).則G*是歐拉圖，因此，由Fleury算法得歐拉環(huán)游C.在C中刪去ei （1ik).得k條邊不重的跡Qi （1ik):10.證明：若：（1）G不是二連通圖，或者（2）G是具有二分類X,

3、Y的偶圖，這里XY,則G是非Hamilton圖。證明：（1）G不是二連通圖，則G不連通或者存在割點v,有w(G-v)2,由于課本上的相關(guān)定理：若G是Hamilton圖，則對于v（G）的任意非空頂點集S，有：w(G-S)S,則該定理的逆否命題也成立，所以可以得出：若G不是二連通圖，則G是非Hamilton圖(2)因為 G是具有二分類X,Y的偶圖，又因為XY，在這里假設(shè)X<Y,則有wG-X=Y>X,也就是說：對于v（G）的非空頂點集S，有：w(G-S)>S成立，則可以得出則G是非Hamilton圖。11.證明：若G有Hamilton路，則對于V的每個真子集S，有wG-SS+1.證

4、明：G是H圖，設(shè)C是G的H圈。則對V(G)的任意非空子集S, 容易知道:所以，有： ,則必然有： wG-SS+1.12. 設(shè)G是度序列為(d1,d2,dn)的非平凡單圖，且d1d2dn。證明：若G不存在小于(n+1)/2的正整數(shù)m，使得：dm<m且dn-m+1<n-m,則G有H路。證明：在G之外加上一個新點v,把它和G的其余各點連接得圖G1 G1的度序列為： (d1+1,d2+1,dn+1, n) ，由條件：不存在小于(n+1)/2的正整數(shù)m,使得dm+1m,且dn-m+1+1<n-m+1=(n+1)-m。于是由度序列判定定理知：G1是H圖，得G有H路。15. 寫出下列問題的

5、一個好算法： (1) 構(gòu)作一個圖的閉包； (2) 若某圖的閉包是完全圖，求該圖的H圈。 解：(1) 構(gòu)作一個圖的閉包： 根據(jù)圖的閉包定義，構(gòu)作一個圖的閉包，可以通過不斷在度和大于等于n的非鄰接頂點對間添邊得到。據(jù)此設(shè)計算法如下： 圖的閉包算法： 1) 令G0=G ,k=0; 2) 在Gk中求頂點u0與V0,使得： 3) 如果 則轉(zhuǎn)4);否則，停止，此時得到G的閉包； 4) 令Gk+1=Gk+u0v0, k=k+1,轉(zhuǎn)2).復(fù)雜性分析：在第k次循環(huán)里，找到點u0與v0，要做如下運算: (a) 找出所有不鄰接點對-需要n(n-1)/2次比較運算；(b) 計算不鄰接點對度和-需要做n(n-1)/2-

6、m(G)次加法運算;(c ),選出度和最大的不鄰接點對-需要n(n-1)/2-m(G)次比較運算。所以，總運算量為：所以，上面的閉包算法是好算法。 (2) 若某圖的閉包是完全圖，求該圖的H圈。 方法：采用邊交換技術(shù)把閉包中的一個H圈逐步轉(zhuǎn)化為G的一個H圈。 該方法是基于如下一個事實： 在閉包算法中，Gk+1=Gk+u0v0, u0與v0在Gk中不鄰接，且度和大于等于n. 如果在Gk+1中有H圈Ck+1如下： 我們有如下斷言： 若不然，設(shè)dGku0=r那么在Gk中，至少有r個頂點與v0不鄰接，則dGkv0(n-1)-r < n-r，這樣與u0，v0在Gk中度和大于等于n矛盾！上面結(jié)論表明：

7、可以從Ck+1中去掉u0v0而得到新的H圈，實現(xiàn)H圈的邊交換。由此，我們設(shè)計算法如下： 1)在閉包構(gòu)造中，將加入的邊依加入次序記為ei (1iN),這里，N=n(n-1)/2-m(G).在GN中任意取出一個H圈CN,令k=N; 2) 若ek不在Ck中，令Gk-1=Gk-ek, Ck-1=Ck; 否則轉(zhuǎn)3); 3) 設(shè)ek=u0v0 Ck, 令Gk-1=Gk-ek; 求Ck中兩個相鄰點u與v使得u0,v0,u,v依序排列在Ck上，且有：uu0,vv0 E(Gk-1),令： 4) 若k=1,轉(zhuǎn)5)；否則，令k=k-1,轉(zhuǎn)2); 5) 停止。C0為G的H圈。復(fù)雜性分析： 一共進行N次循環(huán)，每次循環(huán)運

8、算量主要在3),找滿足要求的鄰接頂點u與v,至多n-3次判斷。所以總運算量：N(n-3),屬于好算法。習題五：1. （1）證明：每個k方體都有完美匹配(k大于等于2) (2) 求K2n和Kn,n中不同的完美匹配的個數(shù)。證明一：證明每個k方體都是k正則偶圖。事實上，由k方體的構(gòu)造：k方體有2k個頂點，每個頂點可以用長度為k的二進制碼來表示，兩個頂點連線當且僅當代表兩個頂點的二進制碼只有一位坐標不同。如果我們劃分k方體的2k個頂點，把坐標之和為偶數(shù)的頂點歸入X，否則歸入Y。顯然，X中頂點互不鄰接，Y中頂點也如此。所以k方體是偶圖。又不難知道k方體的每個頂點度數(shù)為k,所以k方體是k正則偶圖。由推論：

9、k方體存在完美匹配。 證明二：直接在k方體中找出完美匹配。 設(shè)k方體頂點二進制碼為(x1 ,x2,xk),我們?nèi)?x1 ,x2,xk-1,0),和(x1 ,x2,xk-1,1) 之間的全體邊所成之集為M.顯然，M中的邊均不相鄰接，所以作成k方體的匹配，又容易知道：|M|=2k-1.所以M是完美匹配。 (2) 我們用歸納法求K2n和Kn,n中不同的完美匹配的個數(shù)。 K2n的任意一個頂點有2n-1種不同的方法被匹配。所以K2n的不同完美匹配個數(shù)等于(2n-1)K2n-2,如此推下去，可以歸納出K2n的不同完美匹配個數(shù)為：(2n-1)! 同樣的推導方法可歸納出K n, n的不同完美匹配個數(shù)為：n!

10、2. 證明樹至多存在一個完美匹配。證明：若不然，設(shè)M1與M2是樹T的兩個不同的完美匹配，那么M1M2,容易知道：TM1M2每個非空部分頂點度數(shù)為2，即它存在圈，于是推出T中有圈，矛盾。7.將K9表示為四個生成圈之和。證明：K4n+1= K 2(2n)+1 , 所以，可以分解為2n個邊不重的2因子之和。而K9=K2×4+1。所以K9可以表示為四個邊不重的2因子之和，對于每個分解出的因子的路徑為：Pi=vivi-1vi+1vi-2vi+2vi-3vi-nvi+n,則K9的四條路徑為：P1=v1v8v2v7v3v6v4v5,P2=v2v1v3v8v4v7v5v6,P3=v3v2v4v1v5v8v6v7,P4=v4v3v5v2v6v1v7v8,則生成圈Hi是V2n+1與Pi的兩個端點連線生成的。所以可以將K9表示為四個生成圈之和。10. 證明：若n為偶數(shù)，且(G)n/2+1 ,則n階圖G有3因子。證明：因(G)n/2+1 ,由狄拉克定理：n階圖G有H圈C .又因n為偶數(shù)，所以C為偶圈。于是由C可得到G的兩個1因子。設(shè)其中一個為F1。 考慮G1=G-F1。則(G1)n/2。于是G1