湘潭大學計算機科學與技術劉任任版離散數(shù)學課后習題答案---第二學期--圖論與組合數(shù)學

習題六1 .設G是一個無回路的圖，求證：若G中任意兩個頂點間有惟一的通路，則G是樹. 證明：由假設知，G是一個無回路的連通圖，故 G是樹。2 .證明：非平凡樹的最長通路的起點和終點均為懸掛點.分析：利用最長通路的性質可證。證明：設P是樹T中的極長通路。若P的起點v滿足d(v) >1 ,則P不是T中極長的通路。對 終點u也可同理討論。故結論成立。3 .證明：恰有兩個懸掛點的樹是一條通路.分析：因為樹是連通沒有回路的，所以樹中至少存在一條通路P。因此只需證明恰有兩個 懸掛點的樹中的所有的點都在這條通路 P中即可。證明：設u,v是樹T中的兩個懸掛點，即d(u) =d(v) =1。因T是樹，所以存在(u,v)-通路P ： uwiWkV, k之0。顯然，d(Wi)之2。若d(Wi) >2 ,則由T恰有兩個懸掛點的假 設，可知T中有回路；若T中還有頂點x不在P中，則存在(u,x)-通路，顯然u與x不鄰接， 且d(x) ,2。于是, 可推得T中有回路，矛盾。故結論成立。4 .設G是樹，XG心k,求證：G中至少有k個懸掛點.分析：由于A(G )2k ,所以G中至少存在一個頂點v的度k,于是至少有k個頂點與 鄰接，又G是樹，所以G中沒有回路，因此與v鄰接的點往外延伸出去的分支中，每個 分支的最后一個頂點必定是一個懸掛點，因此 G中至少有k個懸掛點。證明：設u WV(G),且d(u)之m之k 。于是，存在v1,，vm w V(G),使 uvaE(G),i =1,，m。若Vi不是懸掛點，則有mw V(G),使。如此下去，有m(1Yv(G), 滿足vi(l) #vj, i # j,且d(vi)=1, i =1,，m。故G中至少有k個懸掛點。5 .設G(p,q謔一個圖，求證：若q之p,則G中必含回路.分析：利用樹是沒有回路且連通的圖，且樹中的頂點數(shù)和邊數(shù)的關系可證。證明：設 G(p, q)有 k 個分支：GM=G1(p1,q)，GVk = Gk(Pk,qk)。顯然， p = Pi + Pk, q =q +qk。若G無回路，則每個Gi 2 ,qj均是樹，i = 1,，k。 于是qi = Pi -1, i =1,，k。從而 q = pk<p, k21,即q<p。此為矛盾，故G必 含回路。6 .設G(p,q促有k個連通分支的圖，求證：G是森林當且僅當q= p-k. 證明：見題5的證明。7 .畫出K4的所有16棵生成樹.解，K4的所有16棵生成樹如下圖所示。232323232398 .設G(p,q顯連通圖，求證：q>p-1.分析：樹應該是具有p個頂點中邊數(shù)最少的連通圖，而樹中的邊數(shù) q=p-1可證。證明：設G是連通圖。若G無回路，則G是樹，于是q = p-1。若G有回路，則刪去G中 k a0條邊使之保持連通且無回路。于是 q -k = p -1, IP q = p-1 +k > p -1o9 .遞推計算K2 3的生成樹數(shù)目.K2,3e10 .通過考慮樹中的最長通路，直接驗證有標記的5個頂點的樹的總數(shù)為125.分析：設樹中5個頂點的標記分別為1, 2, 3, 4, 5。而5個頂點的樹的最長通路只能是 4、 3、2,如下（1） （2） （3）所示。（i）。0 o 00最長通路長度為4；（2） q0Qq最長通路長度為 3;O(3)最長通路長度為2。對于（1），把每個頂點看作是一個空，不同的頂點序列對應不同的樹，但由于對稱性12345和54321所形成的樹應該是同一棵樹，因此這種情況下所有有標記的樹的數(shù)目為：5! /2=60個；對于（2）,把上面四個頂點分別看作一個空，在構造樹的時候可以先構造這四個頂點，剩下的一個頂點只能放在下面，選擇上面四個頂點的數(shù)目應為可以從所有有標記的樹的數(shù)目為4C5 *4!,但同樣由對稱性，如1234這樣的排列和頂點5構成的樹與1235這樣的排列和4構成的數(shù)是一樣的。因此這種情況下所有有標記的樹的數(shù)目為：C54 *4! /2=60個；對于（3）,只要確定了中間度為4的頂點，這棵樹就構造完了，所有這種情況下有標記的樹的數(shù)目為：C5 =5個；解：有標記的5個頂點的樹的總數(shù)為：60+60+5=125個。11 .用T(n所示n個頂點的有標記樹的個數(shù),求證:n _12 n -1T n 八 k n - k T k T n - k Ck k 1由此得恒等式n 1 k _1n -k-1 kn _2k n - k Cn = 2 n -1 nk 4分析：每個n階樹可由下面的方法構造出來：先從這n個頂點中任取k個頂點構造出一個k階樹， 對剩下的n-k個頂點構造出一個n-k階樹，再將這兩個樹合并成一個樹，顯然這樣得到的樹是一 個n階的樹。又由定理6.2.4有i個頂點的無標記的生成樹共有ii-2個，可得下面的證明。證明：任取k個頂點白一棵k階樹與(n )個頂點構成的n 階樹之間連接兩點就是一棵 n階樹，這里有k (n -k)種連接。并注意到一來一往每條邊用了兩次，因此，k (n *) T(k) t (n -k)Cnk =2T(n)。n -1上式兩邊對 k從 1 到 nT 求和，得 2(n1)T(n) = k(n -k)T(k)T(n -k)C：。再將 T(n) = nn N k=1T(k) = kk N T (n *)= (n *)n*N代入上式便可得恒等式:n 1 k 1n4kn -2% k (n -k) Cn = 2(n -1)n k 112 .如何用Kruskal算法求賦權連通圖的權最大的生成樹(稱為最大樹)？證明：將Kruskal算法中的“小”改成“大”即可得到“最大樹”13 .設G是一個賦權連通圖，V(G ) = "2,，ntn至2.求證：按下列步驟(Prim算法)可以得出G的一個最優(yōu)樹.(i )置U :=1,T :=0 ；(ii )選取滿足條件i WU, jWV(G )U且C(i,j垠小的(i, j)；(iii ) T:TU,jU :=UUj；(iv )若U #V(G )則轉(ii ),否則停止,T中的邊就是最優(yōu)樹的邊. * ，一 . * 、一 .解：(1)設T是按Prim算法得出的圖。由Prim算法的初值及終止條件，可知 T連通，且 * . . . * *T為G的生成子圖。又由(ii)知 T無回路。故T是生成樹。(2)設T(G) =T |T是G的生成樹，T #T ,仿定理6.3.1的證明，可證結論成立。14 .按題13的Prim算法，求出圖6. 9的最優(yōu)樹.解：最優(yōu)樹如下。(權為20)習題七1.對圖7.7中的兩個圖，各作出兩個頂點割。(b)7.7解： 對圖7.7增加加節(jié)點標記如下圖所示,V11=a,b；V21=u,v：V12=c,dV12=y52.求圖7.7中兩個圖的K(G刑MG ).則(a)的兩個頂點割為: (b)的兩個頂點割為：解：如上兩個圖，有 k(G1)=入(G1)=2, k(G2)=1,入(G2)=23.試作出一個連通圖G ,使之滿足：MG )= MG )="G ) 解：做連通圖G如下，于是有：k(G) = K(G) =&(G)4 .求證，若G(p,q誕k -邊連通的，則q之kp/2.證明：設G是k一邊連通的，由定義有入(G)呈k.又由定理7.1.2知入(G)三三入(G)三2q/2q/即kw 2q/,從而Pq-kp217p 一/ p5 .求證，若G是p階簡單圖，且S(G心p-2,則它G)=譏G)分析：由G是簡單圖，且d(G )> p-2,可知G中的B (G)只能等于p-1或p-2；如B(G戶p-1,則G是一個完全圖,根據(jù)書中規(guī)定，有 k(G戶p-1=B(G);如B (G戶p-2,則從G中任取V (G)的子集V1 ,其中|V1|=3,則V(G)-V1的點導出子圖是連 通的，否則在V1中存在一個頂點v,與其他兩個頂點都不連通。則在 G中，頂點v最多與 G中其他p-3個頂點鄰接，所以d(v)<p-3,與B(G尸p-2矛盾。這說明了在G中，去掉任意 p-3個頂點后G還是連通的，按照點連通度的定義有k(G)>k-3,又根據(jù)定義7.1.1,鞏G譯(G),有 k(G)=k-2。證明：因為G是簡單圖，所以d(v)Wp-1,vCV(G),已知6(G)呈p-2(i )若 B (G)= p-1,則 G=Kp (完全圖)，故 k(G)=p-1= B (G)。(ii)若B(G戶p-2,則GwKp,設u,v不鄰接，但對任意的wCV(G),有uw,vw CE(G).于是，對任意的 V1 JV(G),| V1|=p-3 ,G-V1 必連通.因此必有 k(G)呈 p-2= B (G),但 k(G)三 B (G)。故 k(G) = B (G)。6.找出一個p階簡單圖，使$(G)=p3,但m(G)<6(G)7 .設G為3 -正則簡單圖，求證父(G)=MG)分析：G是一個3 -正則簡單圖，所以B(G)=3,根據(jù)定理7.1.1有m(GE尢(GE&(G),所以K(G W能等于0, 1, 2, 3這四種情況。下面的證明中分別討論了這四種情況下 k(G即九(G ) 的關系。證明：(1)若k(G戶0,則G不連通,所以入(G戶K(G).(2)設K(G)=1,且u是G中的一個割點，G-u不連通曲于d(u)=3,從而至少存在一個分 支僅一邊與u相連，顯然這邊是G的割邊，故入(G)= 1 ,所以入(G戶K(G)(3 )設K(G)=2,且v1,v2為G的一個頂點割。G1=G-v1連通則v2是G1的割點且v2 在G1中的度小于等于3 ,類似于(2)知在G1中存在一割邊e2(關聯(lián)v2)使得G1-e2不連通.另 一方面由于入(G)>=K(G)=2故G-e2連通.由于G1-e2= (G-e2)-v1,故v1是G-e2的割點，且 v1在G-e2中的度小于等于3 ,于是類似于(2)知，在G-e2中存在一割邊el,即 (G-e2)-e1=G-e1,e2不連通,故入(G)=2.所以入(G)=K(G).(4)設 k(G) =3,于是，有 3 =k (G)三 MG)WB(G)=3，知 k (G)=MG)與8 .證明：一個圖G是2-邊連通的當且僅當G的任意兩個頂點由至少兩條邊不重的通路所 連通.分析：這個題的證明關鍵是理解2-邊連通的定義。證明：(必要性)因為G是2-邊連通的，所以G沒有割邊。設u, v是G中任意兩個頂點， 由G的連通性知u, v之間存在一條路徑P1,若還存在從u到v的與P1邊不重的路徑P2, 設C=P1UP2,則C中含u,v的回路，若從u到v的任意另外路徑和P1都有一條(或幾條) 公共邊，也就是存在邊e在從u到v的任何路徑中，則從G中刪除e, G就不連通了，于是 e成了 G中一割邊，矛盾。(充分性)假設G不是一個2-邊連通白1則G中有割邊，設e=(u,v)為G中一割邊，由已知 條件可知，u與v處于同一簡單回路C中，于是e處在C中，因而從G中刪除e后G仍然連 通，這與G中無割邊矛盾。9 .舉例說明：若在2 -連通圖G中，P是一條 (u,u )-通路，則G不一定包含一條與P內部不相交的(u,u )-通路Q。解如右圖G,易知G是2一連通的，若取P為uv1v2v,則G中不存在Q 了。10 .證明：若G中無長度為偶數(shù)的回路,則G的每個塊或者是K2,或者是長度為奇數(shù)的回路.分析：塊是G的一個連通的極大不可分子圖，按照不可分圖的定義，有G的每個塊應該是沒 有割點的。因此，如果能證明G的某個塊如果既不是K2 ,也不是長度為奇數(shù)的回路，再由 已知條件G中無長度為偶數(shù)的回路，則可得出G的這個塊肯定存在割點，則可導出矛盾。本 題使用反證法。證明：設K是G的一個塊，若k既不是K2也不是奇回路，則k至少有三個頂點，且存在 割邊e=uv于是u,v中必有一個是割點，此與k是塊相矛盾。11 .證明：不是塊的連通圖G至少有兩個塊，其中每個塊恰含一個割點.分析：一個圖不是塊，按照塊的定義，這個圖肯定含有割點 v,對圖分塊的時候也應該以割 點為標準進行，而且分得的塊中必定含這個割點，否則所得到的子圖一定不是極大不可分子 圖，從而不會是一個塊。證明：由塊的定義知，若圖G不是塊且連通，則G有割點，依次在有割點的地方將 G分解 成塊，一個割點可分成兩塊，每個塊中含 G中的一個割點。如下圖Go易知u,v是割點，G可分成四個塊K1K4。其中每個塊恰含一個割點。12.證明：圖G中塊的數(shù)目等于6(G )+ b (曄)-1)其中，b(v廢示包含u的塊的數(shù)目.- V G分析：一個圖G的非割點只能分布在G的一個塊中，即b(u)=1 (當v是G的非割點時)，且 每個塊至少包含一個割點。因此下面就從 G的割點入手進行證明。證明中使用了歸納法證明：先考慮G是連通的情況(MGH1),對G中的割點數(shù)n用歸納法 由于對G的非割點v, b(v)=1 ,即b(v)-1 =0,故對n=0時，G的塊數(shù)為1 + (bu泊)結論. V G成立。假設G中的割點數(shù)n<k (k>0)時，結論成立。對門=卜+1的情況，任取G的一個割點a,可將G分解為連通子圖G,使得a在Gi中不是割 點，a又是Gi的公共點。這樣，每一個 G,有且僅有一個塊含有a,若這些G共有個，則 b(a戶r,又顯然G的塊也是G的塊，且Gi的割點數(shù)li<k。故由歸納法假設Gi的塊的塊數(shù)為 1 + QQ卜1 (id,2：,r),這里bi(v)是Gi中含v的塊的塊數(shù)，注意到Gi中異于a的v, :V Gib(v)= bi(v),而a在每一個Gi中均為非割點，故bi(a)(i=1,2,r)。于是Gi的塊數(shù)為1% b-1 (i=1,2, ,r)將所有Gi的塊全部加起來，則得到G的塊數(shù)為:上:.biu )1 =r -期。卜1 =1+(r-1) 一;b。,； >-1 =1 -三二垃；：卜1vVG由歸納法可知，當G連通時，結論成立。當G不連通時，對每個連通分支上述結論顯然成立。因此有圖G中塊的數(shù)目等于，Gr廿 -113 .給出一個求圖的塊的好算法。分析：設G是一個具有p個頂點，q條邊，w個連通分支的圖。求圖G的塊可先求圖G的任 一生成森林F,且對每一邊eF,求F+e中的唯一回路，設這些回路 C1, C2,，Cq-p+w都 已求得，(這些都有好算法)。在此基礎上，我們注意到，兩個回路(或一個回路與一個塊)若有多于1個公共點，則它們屬于同一塊。止匕外，由割邊的定義知，G的任一割邊不含于任何回路中，且它們都是G的塊?；谶@些道理，可得如下求圖 G的塊的好算法。解：求圖的塊的算法：(1) 令 s=1, t=1, n=q-p+w(2)若n>0,輸入C1, C2,，/ 否則，轉第4步。(3)若|V(Cs)CV(Cs+)中,令Cs=Cs=Cs+，且對 i=s+t,，n-1,令Ci =Ci由，n =n-1 ,轉第4步；否則，t=t+1,轉第5步。(4)若s<n,令t=1,轉第3步；否則，算法停止(這時 C1, C2,，Cn與E (G) - C1 ,C2,，Cn中的每一邊都是G的塊)(5)若s+tn轉第3步；否則，s=s+1,轉第4步。3步，比較Cs與Cs十的頂點尋本算法除了求回路有已知的好算法外，計算量主要在第找它們的公共點的運算中，這些運算不超出p2*(q-p+w)次，故是好算法14 .證明：H2r *p是(2r+1)連通的。分析：只要證明H2fp不存在少于2r+1個頂點的頂點割集。設V是一個|V|<2r+1的任 一頂點子集，可分|V叫2r和|V|=2r兩種情形證明。證明：(1)當|V|<2r時，根據(jù)定理7.3.1的證明，V不是H2r,p的頂點割集，當然更不是在H 2r 0上加些邊的H2r 的頂點割集。 A r , pr , p(2)當|V|=2r時，設V是H 2fp的頂點割集，i，j屬于H2fp V的不同分支。考 察頂點集合S =i,i 1,., j -1, j和T =j,j +1,.,i 1,i 這里加法取模n若S或T中有一個含V的頂點少于r個，則在H2td -V中存在從i到j的路。與V為 A r , p頂點割集矛盾。若S和T中都有V的r個頂點，則：若S或T中，有一個(不妨說S)中V的r個頂點不是相繼連成段，則S-V中存在從 i到j的路。與V為頂點割集矛盾。若S與T中，V的r個頂點都是相繼連成一段的。若S與T中至少有一個沒有被分 成兩段，則立即與V為頂點割集矛盾；若S-V被分成兩段：含i的記S1,含j的記S2 ,且T -V也被分為兩段：含i的記T1 ,含j的記T2。這樣，V -V被分為兩段：含i的 U T1 和含j的S2UT2。這兩段都是連通的，且含i段的中間點(或最靠近中間的一點)i0與含j段 的類似點j。滿足：jo = *i0i0n+ 2n 1+2(n為偶數(shù))(n為奇數(shù))故i0與j0有邊相連，在H2r書,p V中有路(i,.,i0, j0,., j),與V為頂點割集矛盾。綜上所述，H 2Tp是(2r +1)連通的。15.證明：K(Hm,n )=MHm,n )= m.分析：根據(jù)定理7.3.1,圖Hm,n是m-連通圖，因此有 k (Hm,n)=m又根據(jù)Hm,n的構造，可知 6 (Hm,n) 5 ,再由定理7.1.1可證。證明：由定理7.3.1知：K (Hm,n) =m 已知：k三入三B而 5 (H m,n) = m.因止匕 m = k M 兒 M 6 = m.故九(Hm,n) =m.16.試畫出 H48、H58 和 H59.,分析：根據(jù)書上第54頁構造H m,n的方法可構造出H48、H58和H59。.,(i) H4.8: r = 2 ,p=8對任意 i,j V( H4.8), I i- jij Er,其中, j =0, j =7,6 J=8,j = 7,6則H4.8如下圖：i = i(mod p), j = j(mod p).1 =1,j=7 j=9j=7H 4,8圖(ii) H5.8圖：r =2,p=8,則在H 4.8中添加連接頂點i+p/2(mod p)的邊，其中 1<i<p/2,：1 一5; 2 6;3 7;4 0.則 H 5.8 圖如下(iii) H 5.9 圖:r=2,在H 4,.9圖上添加連接頂點0與 i + (p+1) /2(mod p)的邊，其中 1 < i<(p-1) /2和(p+1) /2的邊，以及頂點i與 (p-1) /2.i =0, j =8,7= 9j = 8,7:0一4; 0 一5;一 6；i = 1, j =8 二 10， j = 82 一 7;3 8.則H5.9圖如下:80762354H 5,9圖習題81、圖中8.10中哪些是E圖？哪些是半E圖?(a)(b)(c)分析：根據(jù)歐拉定理及其推論，E圖是不含任何奇點的圖，半 E圖是最多含兩個奇點的圖。解： (a)半E圖。(b) E圖。(c)非半E圖和E圖2、試作出一個E圖G(p,q),使得p與q均為奇數(shù)。能否作出一個E圖G(p,q),使得p為偶數(shù)，而q 為奇數(shù)？如果是p為奇數(shù)，q為偶數(shù)呢？解：以下E圖中，p與q的奇偶如下表PqG1奇數(shù)奇數(shù)G2偶數(shù)奇數(shù)G3奇數(shù)偶數(shù)GiG2G33、求證：若G是E圖，則G的每個塊也是E圖。分析：一個圖如果含有E回路，則該圖是E圖;另一方面一個塊是G中不含割點的極大連通不可分子圖，且非割點不可能屬于兩個或兩個以上的塊。這樣沿G中的一條E回路遍歷G的所有邊時，從一個塊到達另一個塊時，只能經過割點才能實現(xiàn)。證明：設B是G的塊，任取G中一條E回路C,由B中的某一點v出發(fā)，沿C前進，C只有經 過G的割點才能離開B,也就是說只有經過同一個割點才能回到 B中，注意到這個事實后，我們將C中屬于B外的一個個閉筆回路除去，最后回到 v時，我們得到的就是B上的一個E回路,所以B也是E圖。4、求證：若G無奇點，則G中存在邊互不重的回路Ci, ，Cm使得E(G) =E(Ci) - E(C2)- E(Cm)分析：G中無奇點，則除了孤立點后其他所有點的度至少為2,而孤立點不與任何邊關聯(lián)，因此在分析由邊構成的回路時可以不加考慮；而如果一個圖所有的頂點的度至少為2,則由第五章習 題18知該圖必含回路。證明：將G中孤立點去掉以后得到圖 G1,顯然G1也是一個無奇點的E圖，且"G1)22。由第 五章習題18知，G1必含有回路C1;在圖G1-C1中去掉孤立點，得圖 G2,顯然G2仍然是一個 無奇點的圖，且6(G2)及，于是G2中也必含回路C2,如此直到Gm中有回路Cm,且Gm-Cm 全為孤立點為止，于是有：E(G) =E(G) 一 E&) 一 一 E(Cm)5、求證：若G有2k>0個奇點，則G中存在k個邊互不重的鏈Q1 Qk ,使得：1 , kE(G) =E(QJ . E)一. E(Qk)分析：一個圖的E回路去掉一條邊以后，將得到一條 E鏈。證明：設 V1V2,，Vk,Vk書，V2k為G中的奇數(shù)度頂點，k> 1在Vi和Vi+k之間用新邊ei連 接，i =1, 2.k,所得之圖記為G*,易知G*的每個頂點均為偶數(shù)，從而 G*存在E閉鏈C* 。 現(xiàn)從C*中刪去ei (i=1, 2.k),則C*被分解成k條不相交的鏈Qi( i =1, 2.k),顯然有：E(G) =E(Q1)一 E(Q2)一 E(Qk)6、證明：如果(1) G不是2連通圖，或者(2) G是二分圖<X,Y>,且XWY,則G不是H圖。 分析：G不是2連通圖，說明MG1 ,于是工口或K(G)=0 ,如果K(G)=0,則說明g 不連通，如G不連通，顯然G不是H圖，如K(G)=1則g中存在孤立點，因此有w(G-v)>2, 由定理8.2.1G不是H圖。若G是二分圖<X , Y> ,則X或Y中的任意兩個頂點不鄰接，因此G-X 剩下的是Y中的點，這些點都是孤立點；同樣 G-Y剩下的是X中的點，這些點也是孤立點；即 有叫G -X)卡|,8(G Y) =|X|,如果x.丫，則有0 (G 一X)卡|鄧|或s (G -Y)平|>Y|成立。無論哪個結論成立，根據(jù)定理 8.2.1都有G不是H圖。證明：若(1)成立則G不連通或者是G有割點u,若G不連通，則G不是H圖，若G有割點u, 取S=u,于是co (G-u)> S因此 G不是H圖.若(2)成立，不妨設|X| <|丫|.令$ = *,則金(g - S) =|y|>|x| =|s|即：切(G -S) >|S.因此G不是H圖.(G-S)S 1.7、證明:若 G是半H圖，則對于V(G)的每一個真子集S,有：分析：圖G的權與它的生成子圖G的連通分支數(shù)滿足：CO(G)"(G)因為一個圖的生成子圖是在該圖的基礎上去掉若干邊得到的，顯然去掉邊以后只能使該圖的連通分支增加。對于圖G的一條H通路C,滿足任取Sc V , s(C -S) < S +1.證明:設C是G的一條H通路，任取SUV,易知(C -S) < S 1.而 C-S 是 G-S 的生成子圖. 故(GS) Wco(CS)w S+1.故與(G S)S+1.8、試述H圖與E圖之間的關系。分析：H圖是指存在一條從某個點出發(fā)經過其他頂點有且僅有一次的回路；而E圖是指從某點出發(fā)通過圖中所有的邊一次且僅有一次的回路。從定義可看出，這兩者之間沒有充分或必要的關系。解：考慮如下四個圖：易知G1是E圖，但非H圖；G2是H圖，但非E圖；G3既非E圖，又非H圖；G4既是E圖，也 是H圖。9、作一個圖，它的閉包不是完全圖分析：一個p階圖的閉包是指對G中滿足d(u)+d(v)> p的頂點u,v,若uv*E(G),則將邊uv力口至U G中，得到G+uv,如此反復加邊，直到滿足d(u)+d(v) >p的所有頂點均鄰接。由閉包的定義，如 果一個圖本身不存在任何一對頂點u,v,滿足d(u)+d(v)>p,則它的閉包就是其自身。顯然可找到滿足這種條件的非完全圖。解：如右圖G, G=G,但G不是完全圖10、若G的任何兩個頂點均由一條 H通路連接著，則稱G是H連通的。 一 一 一， 一 一 1(1)證明：若G是H連通的，且p之4,則q之.1(3p+1)1 一、I(2)對于p皂4,構造一個具有q = J (3p +1)的H連通圖Go2 39pp分析：根據(jù)定理5.3.1有2q = d(vi),因此q = d(Vi)/2 i 1i =1P而Z d(vi)之P* 6(G),所以q>p*S(G)/2,因此如果能判斷S(G)>3,則有 i 41q之pw 6(G)/2至3P/2之(3p+1)下面的證明關鍵是判斷S(G)>3。證明：(1)任取we V(G),由于G是連通的，所以d(w)>1op> 4,所以GH通路與u與若d(w)=1,則與w鄰接的頂點u與w之間不可能有一條H通路連接它們，否則因為 中除了 u與w外還有其他頂點，因此，如果 u與w之間有一條H通路的話，這條 w的連線就構成了一個回路，這樣與 d(w)=1矛盾，所以d(w)w1；同樣的道理，若d(w)=2,則與w鄰接的頂點u與v之間不存在H通路。因此 8(G) >3o從而 2q=Ed(u)>3p,即：2q>3p,也即 q > 3p/21- 八若p為奇數(shù)，于是q -(3p+1)；1(ii)若p為偶數(shù)，則3P為偶數(shù)，于是q 2(3p+1)；綜合以上各種情況，有:1q 至 q(3p + 1)；(2) (i )當p=偶數(shù)時，q=3p/2,滿足條件的圖如下圖(a);40圖(a)11、證明：若G是一個具有p三28的連通簡單圖，則 G有一條長度至少是2 8的通路。分析：使用反證法，假設G中沒有一條長度大于或等于 2 8的通路。先找到圖G的一條最長通路P,設其長度為m,由假設m<2 8。再在P的基礎上構造一條長度為 m+1的回路C,顯然C中包 含的頂點數(shù)小<2 8,由于p皂28,所以圖G至少還有一個頂點v不在該圈中，又由于 G是連通 的，所以v到C上有一條通路P。于是P+C的長度等于通路P的長度的通路構成了一條比 P更 長的通路，這與P是G的一條最長通路矛盾。從而本題可得到證明。證明：(用反證法)設p =VV 棟G的最長通路 淇長度為m,假設m<2 8。由P是G的最長通路，則V1,Vm+1只3與P中的頂點相鄰，注意到 G是簡單圖令S =Vi V2 i E(G), T =Vi vm a E(G),二 S =d (vi)至 6,T =d (vm韋)>5o由定義知：vm +更ST ,因止匕|sUT|wmM26 ,于是ST#中，事實上，= 2S A SJt = S + T -|st| S> - SnT|=2 - SnT 二怕口丁 卜 0,即 STQ。設丫1三$1丁#我從而有G中的長為 m+1的回路C： v1V2“ivivm41Vmvi+v1.因p >26, m+1 W26,所以，C外至少還有一個頂點v0 e V (G)。由G連通可知，有一條 P外的通路與C連接。不妨設 v0vj WE (G) ,1EjEm+1.是有通路P ： V0VjVj 4V1Vi書VmVm由ViVi/V1.且P I A P ,此與P的假設矛盾！ 故結論成立。12、設p(豺階簡單圖G的度序列為：d1Wd2Wrqp.證明：若對任何m,117W(p1)/2,均有dm>m右p為奇數(shù)，還有d1P布與(p1)則G是H圖。分析：由定理824,如果p (>3)階簡單圖G的各頂點度數(shù)序列di京2W玄p,而且又t任何m<p/2,有dmmdp_m>p-m,貝UG是H圖。卜面的證明就是利用這個定理來判斷當m<p/2時，dm滿足dm>m。從而G是H圖。證明：對任何正整數(shù) m；E,2(1)若p為偶數(shù)(p之3),則必有：14mwB1=E<_p二1 222即1 <m <(p 1)/2，由題設有dm >m,再由定理8.2.4知G為H圖(2)若p為奇數(shù)，則m E p 1 (a)若m < p 1,則由題設有dm > m, 22p -1p-1(bm= ，地 pm=p=221 口 r于是 dp_m =d 1> ( p -1)Wd p_m 至(p 1)22 L2 p - p 1 p 12 一 21(p1)+1 = p m,也即 dp_m 至 p m,2從而，由定理8.2.4知，G是H圖。13、在圖8-8中，如果分別去掉v3, v4和v5,則相應得到的旅行推銷員問題的解分別取什么下 界估計值？ 分析：利用Kruskal算法可給出一個關于旅行推銷員問題的的下界估計式:任選賦權完全圖Kn的一個頂點v,用Kruskal算法求出Kn-v的最優(yōu)樹T,設C是最優(yōu)的H回路，于是有C-v也是Kn-v的一個生成樹，因此有：w(T) < w(C-v)設e1和e2是Kn中與v關聯(lián)的邊中權最小的兩條邊，于是： w(T)+w(e1)+w(e2) <w(C)上式左邊的表達式即是w(C)的下界估計式。解：(1)去掉v3后的最優(yōu)數(shù)T3的權為w(T3)=5+5+1+7=18，而與v3關聯(lián)的5條邊中權最小的兩條之權為w(e1)=8,w(e2)=9，因此下界估計值為 w(C3)=18+8+9=35,(2 )去掉 v4 后，仿上有 w(T4)=20, w(C4)=20+7+8=35;(3)去掉 v5 后，有 w(T5)=26, w(C5)=26+1+5=32.14、設G是一種賦權完全圖，其中對任意 x,y,zC V(G),都滿足缶 僅十8 &Z " 僅才： 證明：G中最優(yōu)H回路最多具有權28(T)其中T是G中的一棵最優(yōu)樹。分析：H回路是指從圖中某點出發(fā)，經過圖中每個頂點有且僅有一次，最后回到出發(fā)點的一條回路。由于G是一種賦權完全圖，所以從任意頂點出發(fā)包括了 G的其他所有頂點有且僅有一次再回到原點的回路都構成了 G的一條H回路C,且最優(yōu)H回路C的權滿足。因此只428(C)%(C)E(O<2(T)需證明G中存在一條H回路C,其權即可，因此證明本題的關鍵是找到滿足這個結論的H回路C。證明：設T是G中的一棵最優(yōu)樹，將T的每邊加倍得到圖T,則T的每個頂點的度數(shù)均為偶數(shù)。所以T有一歐拉回路Q,設Q=(v1, v2，vn,v1), (n>|v(G)|), Q中某些頂點可能有重復，且0 (Q)=28(T)在Q中，從v3開始，凡前面出現(xiàn)過的頂點全部刪去，得到 G的|v(G)由頂點的一個排列兀。由 于G是完全的，所以兀可以看作G中的一個H回路。在兀中任意邊(u,v),在T中對應存在唯一 的(u,v)-通路P,由權的三角不等式有切(u,v)<o(F>)由于將兀中的邊(u,v)用T中的P來代替時，就得到Q,因而 (冗)抬(Q)=2o(T澈G中的最優(yōu)H回路C的權 切(C)<tt(n)<2w(T)45習題九1 .證明：任何樹最多只有一個完美匹配分析：樹是連通沒有回路的圖；樹的完美匹配是樹存在一個匹配M,滿足樹的所有頂點 v都是M-飽和點。而兩個完美匹配中不同的邊所關聯(lián)的頂點的度至少為 2,否則如果等于1的話，則該 頂點關聯(lián)的邊只有一條，在構造完美匹配的時候為了使得這個點成飽和點，只有一種選擇。證明：設樹T有兩個或兩個以上的完美匹配，任取完美匹配M1和M 2, M1 # M2。于是Mi份M2 #中。易知邊導出子圖H =TMi M2中的每個頂點v滿足dH(v) A 2。于是H 中存在回路，從而T中有回路。此與T是樹矛盾，故結論成立。2 .證明：樹G有完美匹配當且僅當對任意 vWV(G),均有O(Gv) = 1分析：一方面，由定理9.1.3圖G存在完美匹配當且僅當對任意 SUV(G),有O(GS)E|S|,所 以如果樹G有完美匹配，則O(G-v)4v|=1 ；而G有完美匹配，說明|V(G) =偶數(shù)，所以 O(G -v)之 1 ；從而有 O(G -v) =1。另一方面，如果對任意vV(G),均有O(G -v) =1 ,則對v而言，可利用這個這個奇分 支找到v關聯(lián)的唯一邊，從而構造出 G的一個完美匹配。證明：必要性 設G有完美匹配。由定理9.1.3,取S =v,則O(G -v) =O(G -S) M|S| = 1又G有完美匹配，|V(G)上偶數(shù)。于是M(Gv)|=奇數(shù)。故 O(Gv)*.從而 O(Gv)=1.充分性 設對任意v V(G),有O(G v) =1.即G v恰有一個奇分支Co(v),因G是樹，故v只能與Co(v)中的一個頂點鄰接。設v與Co(v) 的關聯(lián)邊為e(v)KuWE(G)。顯然v確定以后，uv是唯一確定的，且易知Co(u)=uv。因為G-v 只有一個奇分支Co(v),則G-u以后，v應該與G-v的其他偶分支在一個連通分支中，而這個分 支的頂點數(shù)顯然是奇數(shù)，從而構成G-u的唯一一個奇分支Co(u),而u與這個奇分支中的頂點顯 然也只有與v鄰接，所以Co(u)=uv。于是對任意vW(G),按這樣的方法構造其關聯(lián)邊 e(v), 所的的匹配 M =e(v) |v WV(G)就是G的一個完美匹配3 .設k >1是奇數(shù)。舉出沒有完美匹配的k -正則簡單圖的例子。分析：作G如下：取2k-1個頂點v1,2,v2ki,在奇足標頂點和偶足標頂點間兩兩連以邊外，再連以V1V3,V5v7： ,V2k_5V2k工邊，所得圖記為G0,顯然G0除V2k外其余頂點的度均為k,而V2k 的度為k-1,取k個兩兩不相交的Go的拷貝和一個新頂點V0,并把每個Go拷貝中對應于V2k的 頂點與Vo相連以邊。最后所得的圖記為G,顯然G是k-正則的簡單圖。又由于Go含2k-1個頂點， 則G的頂點數(shù)為：k*(2k-1)+1。所以如果G有一個完美匹配M的話，則k*(2k-1) 1 , 2 k-1|M|= - = k 。22假設M是G的一個完美匹配，則其邊應來自k個獨立的Go,和跟Vo相關聯(lián)的一條邊。而每個Go,其包含的頂點數(shù)為2k-1,所以Go能提供給M的邊最多為k-1條，k個這樣的Go能提22 k-1供給M的邊最多為k*(k-1),因此M最多包含的邊為k*(k-1)+1=k 2-(k-1)< k ,因此G不可2能有完美匹配。解：令k=3,得到的圖Go及G如下：4 .設k A o為偶數(shù)，舉出沒有完美匹配的 k-正則簡單圖的例子.分析：當k為偶數(shù)時，取G=Kk+1,則G的頂點數(shù)為k+1 ,顯然G的頂點數(shù)為奇數(shù)，所以G無完美匹配。解：令k=2時，可構造出無完美匹配的 2-正則圖K3 o5 .兩人在圖G上進行對奕雙方分別執(zhí)黑子和白子，輪流向G的不同頂點Vo,Vi,V2, 下子，要求當i >0時，Vi與v鄰接，并規(guī)定最后可下子的一方獲勝。若規(guī)定執(zhí)黑子者先下子，試證明執(zhí) 黑子的一方有取勝的策略當且僅當 G無完美匹配。分析：假設G有完美匹配，則G的每個頂點都是M-飽和點，這樣先下者無論取哪個頂點，后下 者都可取其相鄰的M-飽和點，這樣先下的人必輸；因此先下的人如要贏的話，G中肯定無完美匹 配。反過來，如果G中無完美匹配，由于任何圖都有最大匹配，則可找到 G的一個最大匹配 M,由 于M不是完美匹配，因此 G中存在M-非飽和點v,先下的黑方就可找到這個點下，則與 v相鄰 的下一個點必是M-飽和點，不然，M Uuv就是一個更大的匹配，與M是最大匹配矛盾。同理G 中不存在M可增廣路，故黑方所選vi必是M飽和點，如此下去，最后必是白方無子可下，故黑 方必勝。證明：必要性(反證法) 若G中存在一個完美匹配M ,則G中任何點v都是M飽和點。 故不論執(zhí)黑子(先下者)一方如何取 v一,白方總可以取M中和v關聯(lián)邊的另一端點作為M , 于是，黑方必輸。充分性.設G中不存在完美匹配，令M是G的最大匹配，而v0是非M飽和點。于是，黑方 可先取v0點，白方所選必必是M飽和點(因M是最大的匹配)由M的最大性可知G中不存 在M可增廣路，故黑方所選m必是M飽和點，如此下去，最后必是白方無子可下，故黑方必勝。6 .證明：二分圖G有完美匹配當且僅當對任何 S v(G),有|s.|Ng(s)| 成立舉例說明若G不是二分圖，則上述條件未必充分。分析：由定理9.1.2Hall定理，對于具有二劃分(X,Y)的二分圖，G有飽和X中每個頂點的匹配 當且僅當對任意的SX ,<|S|<|Ng(S),顯然如果G有完美匹配M的話，則M既飽和X, 也飽和Y。但當G不是二分圖時，這個結論不一定成立，如 K2n+1對任意的S=V(G)滿足 |S閆Ng(S)|,但它無完美匹配。證明：必要性.設G有完美匹配M ,則M飽和X及Y ,由Hall定理和對任何S X或 SY ,有|S|-|Ng(s)|今任取S=V(G),有$ = & = $2,& =X, S21Y于是有|S|=|S - S2|=|S| |S|-|Ng(S)| |Ng(S2)|二|Ng(Si - S2)|=|Ng(S)|46充分性：設對任何S 3 V (G),有| S兇Ng (S)|.即任取SIX ,有|S區(qū)Ng(S)|,于是由Hall定理，存在飽和X的匹配M(X),同理，存 在飽和Y的匹配M (Y),從而| X |二|Y |,易知M (X)和M (Y)都是完美匹配。當G不是二分圖時，條件不充分，如 G = K3。7 . 2n個學生做化學實驗，每兩個人一組，如果每對學生只在一起互作一次實驗，試作出一個安排，使任意兩個學生都在一起做過實驗。分析：該題可轉化為對具有2n個頂點(可分別記為0, 1, 2,，2n-1)的完全圖構造其不同的2n-1 個完美匹配，使得(0, 1) (0, 2)(0, 2n-1), (1, 2) (1, 3),，(1, 2n-1)， (2n-2,2n-1)在這2n-1個匹配中出現(xiàn)且僅出現(xiàn)一次。解： 共安排2n-1次實驗，可使任意兩個學生都在一起做過實驗。安排如下：第 1 次：(0,1), (2, 2n-1), (3, 2n-2),(x,y)其中,x+y=2n+1;第 2 次：(0, 2), (3, 1), (4, 2n-1),(x, y) 其中，x+y=2n+3;第 2n-1 次：(0, 2n-1), (1,2n-2), (2, 2n3),(x, y)其中，x+y=2n-1;8 .試證明：任何一個(0,1)矩陣中，包含元素1的行或列的最小數(shù)目，等于位于不同行不同列 的1的最大數(shù)目。分析：由定理922,對二分圖G,均成立a (G) = P(G)(其中a,(G)為G的最大匹配數(shù)，P(G) 為G的點覆蓋數(shù))。將給定的(0, 1)矩陣表示成一個二分圖G(V1,V2,E)V1 =U1,，un , V2 =V1,，vn.其中 M(i, j) =1 當且僅當(u,Vj)w E(G) 該題轉化為了判斷G的0(G)和a (G)的關系。證明： 設M m>n是一個(0,1)矩陣.將M m沏表示成一個二分圖G(V1,V2 ,E),V1 =u1,，Un , V2 =必,，Vn .其中M(i, j) =1 當且僅當(Ui,Vj)w E(G)于是，G的(最小)點覆蓋數(shù)P(G)等于含M m看中元素1的行(第i行元素1的數(shù)目表示頂點ui 覆蓋的邊之數(shù)目)或列(第j列元素1的數(shù)目表示頂點Vj覆蓋的邊數(shù)目)的數(shù)目。而 G的最大 匹配數(shù)a (G)等于M m坨中位于不同行不同列的1的最大數(shù)目.由定理9.2.2知，若G為二分圖，則a(G) = P(G)。故結論成立.9 .能否用5個1父2的長方表將圖9-13中的10個1父1正方形完全遮蓋?。繄D 9-13分析：按如下方法作出G圖：在圖9-13的每個正方形格子中放一個頂點，U與V鄰接當且僅當U與V所在的方格有公共邊。則該問題等價于判斷相應圖G是否有完美匹配，解：按照分析，構造圖G如下：則有O(G<u)=3>1=u|,由定理9.1.3可判斷它沒有完美匹 配。因此不能用5個1父2的長方表將圖9-13中的10個1父1正方形完全遮蓋住。110 .試證明：G是二分圖當且僅當對 G的每個子圖H均有 a(H ) >- |V(H) |o2分析：若6= (X,Y)是二分圖，顯然X和Y都構成G的點獨立集，所以G的最大獨立數(shù)ct(G)>|X| , 且u(G)平|;而二分圖的每個子圖顯然也是二分圖。證明：必要性.設G是二分圖，于是 G的任何子圖 H也是二分圖，設 H =(X,Y),|X | 十|Y|=|V(H)|。不妨設 |X 戶|丫|。顯然 (H) >| X |,因此，次之必mX|+|Y田|。于是，a(H)卻V(H)1。充分性.若G不是二分圖，則G中含奇回路C。令H =C。顯然，a(H ) = V(H)/2工工|V(H)|。矛盾。故G 是二分圖。4811 .試證明：G是二分圖當且僅當對 G的每個適合6(H ) >0的子圖H ,均有a(H) = P(H). 分析：ot(G)是指G的最大獨立集，P <G)是指G的邊覆蓋數(shù)。如果 G是不含孤立點的二分圖( X, Y),顯然ct(G) =max(|X|,|Y|),因此如果能證明P,(H )=max(|X|,|Y|),則對不含孤立點的二分圖 G,有a(G)=P，(G)證明：必要性.設G是二分圖。 HWG, 6(H) >0 ,即H無孤立點。顯然H也是二分圖， 設H =(X,Y),且| X以丫 |。于是， u(H ) =|X |。而一條邊最多覆蓋一個頂點，故 pH) >|X |o 但由于 H 無孤立點，因此，P(H) <|X| ,故 P(H )=|X | = u(H)。充分性.若G不是二分圖，則G含奇回路C = H。設|V(H)|=2n+1, n之1。于是 a(H) =n ,而 P(H) =n +1 >s(H)。矛盾。故 G 必為二分圖。12 .設G是具有劃分(X, Y)的二分圖。證明：若對于任何 uw X,vWY.均有d(u)之d(v), 則G有飽和X中每一頂點的匹配。分析：根據(jù)定理9.1.2,二分圖G有飽和X中每個點的匹配當且僅當對任何 S= X，有|S四Ng(S)| 根據(jù)這個結論，如果能說明滿足條件的二分圖 G中不存在任何SG X ,有|S|>|Ng(S)| ,則題目 得證。證明：由題意知，對VuWX, d(u)之1。若G中不存在飽和X的匹配，則由Hall定理，存在S= X ,使|S|>| Ng(S)|。設 S=u1 J ,um, Ng (S) =Vj ， ,其中 m > n o1 ,n由對任何uWX,vWY, d(u)之d(v),得 d(u)至d d(v),但由于S中的點關聯(lián)的邊u Sv三Ng (S)都是Ng (S)的點關聯(lián)的邊，因此d d(u)< d d(v),因此有 d(u)= d d(v),但mn,u Sv=Ng (S)u Sv三Ng(S)因此在Ng (S)中總存在一點，有d(vjr)>d(ut)。矛盾。故G中存在飽和X的匹配。13.證明(Hall定理的推廣)：在以G(X,Y)為二劃分的二分圖G中，最大匹配數(shù)二(G)為(G) =min| X -S| |Ng(s)|s x-分析：由定理9.2.2有：如果一個圖G是二分圖，則u(G) = P(G) , a(a)是G的最大匹配數(shù)，P(G)是G的最小覆蓋。因此如果能說明 mjn|X-S|Ng(S)|等于目(G)的話，則本題得以證明。s x證明：由于X SNg(S)H,所以 |XS|+|Ng(S)| = XSjNg(S)|顯然 X S3Ng (S)是G的一個覆蓋，而G的任意一個覆蓋都可以寫成 X S= N g (S)的形式，所以 FG) = min|X-S| |Ng(S)|因此有：(G) = -(G)=xmin|X-S| |Ng(S)|S x4914 .證明：在無孤立點的二分圖 G中，最大獨立集的頂點集“(G)等于最小邊覆蓋數(shù)P (H)。證明：參見題1115 .在9個人的人群中，假設有一個人認識另外兩個人，有兩個人每人認識另外4個人，有4個人認識另外5個人，余下的兩個人每人認識另外的6個人。證明：有3個人，他們全部互相認識。分析：將該題中的人用圖中的節(jié)點表示，兩個節(jié)點有連線當且僅當兩個人認識，則該題轉化為求證滿足上述條件的圖G含有一個K3。要判斷一個圖是否含有 K3,我們先要了解以下概念和定理：T2, p：具有p個頂點的完全2分圖，如果p是偶數(shù)，則該圖的每一部分頂點數(shù)為 p/2;如果p為奇 數(shù)，則該圖的其中一部分頂點數(shù)為(p-1)/2,另一部分頂點數(shù)為(p+1)/2。Turan定理(托蘭定理)的推論：若簡單圖 G不含K3,則E(G)< E(T2,p),且當E(G)=E(T2,p)時， 有G三T2, p該定理的嚴格內容為：若簡單圖G不含Km+1,則E(G)WE(Tm，p)