《湘潭大學(xué)計算機(jī)科學(xué)與技術(shù)劉任任版離散數(shù)學(xué)課后習(xí)題答案---第二學(xué)期--圖論與組合數(shù)學(xué)》由會員分享，可在線閱讀，更多相關(guān)《湘潭大學(xué)計算機(jī)科學(xué)與技術(shù)劉任任版離散數(shù)學(xué)課后習(xí)題答案---第二學(xué)期--圖論與組合數(shù)學(xué)（88頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、習(xí)題六1 .設(shè)G是一個無回路的圖，求證：若G中任意兩個頂點(diǎn)間有惟一的通路，則G是樹. 證明：由假設(shè)知，G是一個無回路的連通圖，故 G是樹。2 .證明：非平凡樹的最長通路的起點(diǎn)和終點(diǎn)均為懸掛點(diǎn).分析：利用最長通路的性質(zhì)可證。證明：設(shè)P是樹T中的極長通路。若P的起點(diǎn)v滿足d(v) 1 ,則P不是T中極長的通路。對 終點(diǎn)u也可同理討論。故結(jié)論成立。3 .證明：恰有兩個懸掛點(diǎn)的樹是一條通路.分析：因?yàn)闃涫沁B通沒有回路的，所以樹中至少存在一條通路P。因此只需證明恰有兩個 懸掛點(diǎn)的樹中的所有的點(diǎn)都在這條通路 P中即可。證明：設(shè)u,v是樹T中的兩個懸掛點(diǎn)，即d(u) =d(v) =1。因T是樹，所以存在(u
2、,v)-通路P ： uwiWkV, k之0。顯然，d(Wi)之2。若d(Wi) 2 ,則由T恰有兩個懸掛點(diǎn)的假 設(shè)，可知T中有回路；若T中還有頂點(diǎn)x不在P中，則存在(u,x)-通路，顯然u與x不鄰接， 且d(x) ,2。于是, 可推得T中有回路，矛盾。故結(jié)論成立。4 .設(shè)G是樹，XG心k,求證：G中至少有k個懸掛點(diǎn).分析：由于A(G )2k ,所以G中至少存在一個頂點(diǎn)v的度k,于是至少有k個頂點(diǎn)與 鄰接，又G是樹，所以G中沒有回路，因此與v鄰接的點(diǎn)往外延伸出去的分支中，每個 分支的最后一個頂點(diǎn)必定是一個懸掛點(diǎn)，因此 G中至少有k個懸掛點(diǎn)。證明：設(shè)u WV(G),且d(u)之m之k 。于是，存在
3、v1,，vm w V(G),使 uvaE(G),i =1,，m。若Vi不是懸掛點(diǎn)，則有mw V(G),使。如此下去，有m(1Yv(G), 滿足vi(l) #vj, i # j,且d(vi)=1, i =1,，m。故G中至少有k個懸掛點(diǎn)。5 .設(shè)G(p,q謔一個圖，求證：若q之p,則G中必含回路.分析：利用樹是沒有回路且連通的圖，且樹中的頂點(diǎn)數(shù)和邊數(shù)的關(guān)系可證。證明：設(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,
4、i =1,，k。從而 q = pkp, k21,即qp-1.分析：樹應(yīng)該是具有p個頂點(diǎn)中邊數(shù)最少的連通圖，而樹中的邊數(shù) q=p-1可證。證明：設(shè)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 .通過考慮樹中的最長通路，直接驗(yàn)證有標(biāo)記的5個頂點(diǎn)的樹的總數(shù)為125.分析：設(shè)樹中5個頂點(diǎn)的標(biāo)記分別為1, 2, 3, 4, 5。而5個頂點(diǎn)的樹的最長通路只能是 4、 3、2,如下（1） （2） （3）所示。（i）。0 o
5、 00最長通路長度為4；（2） q0Qq最長通路長度為 3;O(3)最長通路長度為2。對于（1），把每個頂點(diǎn)看作是一個空，不同的頂點(diǎn)序列對應(yīng)不同的樹，但由于對稱性12345和54321所形成的樹應(yīng)該是同一棵樹，因此這種情況下所有有標(biāo)記的樹的數(shù)目為：5! /2=60個；對于（2）,把上面四個頂點(diǎn)分別看作一個空，在構(gòu)造樹的時候可以先構(gòu)造這四個頂點(diǎn)，剩下的一個頂點(diǎn)只能放在下面，選擇上面四個頂點(diǎn)的數(shù)目應(yīng)為可以從所有有標(biāo)記的樹的數(shù)目為4C5 *4!,但同樣由對稱性，如1234這樣的排列和頂點(diǎn)5構(gòu)成的樹與1235這樣的排列和4構(gòu)成的數(shù)是一樣的。因此這種情況下所有有標(biāo)記的樹的數(shù)目為：C54 *4! /2=6
6、0個；對于（3）,只要確定了中間度為4的頂點(diǎn)，這棵樹就構(gòu)造完了，所有這種情況下有標(biāo)記的樹的數(shù)目為：C5 =5個；解：有標(biāo)記的5個頂點(diǎn)的樹的總數(shù)為：60+60+5=125個。11 .用T(n所示n個頂點(diǎn)的有標(biāo)記樹的個數(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階樹可由下面的方法構(gòu)造出來：先從這n個頂點(diǎn)中任取k個頂點(diǎn)構(gòu)造出一個k階樹， 對剩下的n-k個頂點(diǎn)構(gòu)造出一個n-k階樹，再將這兩個樹合并成一個樹，顯然這樣得到的樹是一 個n階的樹。又
7、由定理6.2.4有i個頂點(diǎn)的無標(biāo)記的生成樹共有ii-2個，可得下面的證明。證明：任取k個頂點(diǎn)白一棵k階樹與(n )個頂點(diǎn)構(gòu)成的n 階樹之間連接兩點(diǎ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
8、)n k 112 .如何用Kruskal算法求賦權(quán)連通圖的權(quán)最大的生成樹(稱為最大樹)？證明：將Kruskal算法中的“小”改成“大”即可得到“最大樹”13 .設(shè)G是一個賦權(quán)連通圖，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 )則轉(zhuǎn)(ii ),否則停止,T中的邊就是最優(yōu)樹的邊. * ，一 . * 、一 .解：(1)設(shè)T是按Prim算法得出的圖。由Prim算法的初值及
9、終止條件，可知 T連通，且 * . . . * *T為G的生成子圖。又由(ii)知 T無回路。故T是生成樹。(2)設(shè)T(G) =T |T是G的生成樹，T #T ,仿定理6.3.1的證明，可證結(jié)論成立。14 .按題13的Prim算法，求出圖6. 9的最優(yōu)樹.解：最優(yōu)樹如下。(權(quán)為20)習(xí)題七1.對圖7.7中的兩個圖，各作出兩個頂點(diǎn)割。(b)7.7解： 對圖7.7增加加節(jié)點(diǎn)標(biāo)記如下圖所示,V11=a,b；V21=u,v：V12=c,dV12=y52.求圖7.7中兩個圖的K(G刑MG ).則(a)的兩個頂點(diǎn)割為: (b)的兩個頂點(diǎn)割為：解：如上兩個圖，有 k(G1)=入(G1)=2, k(G2)=1
10、,入(G2)=23.試作出一個連通圖G ,使之滿足：MG )= MG )=G ) 解：做連通圖G如下，于是有：k(G) = K(G) =&(G)4 .求證，若G(p,q誕k -邊連通的，則q之kp/2.證明：設(shè)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
11、,則從G中任取V (G)的子集V1 ,其中|V1|=3,則V(G)-V1的點(diǎn)導(dǎo)出子圖是連 通的，否則在V1中存在一個頂點(diǎn)v,與其他兩個頂點(diǎn)都不連通。則在 G中，頂點(diǎn)v最多與 G中其他p-3個頂點(diǎn)鄰接，所以d(v)k-3,又根據(jù)定義7.1.1,鞏G譯(G),有 k(G)=k-2。證明：因?yàn)镚是簡單圖，所以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,設(shè)u,v不鄰接，但對任意的wCV(G),有uw,vw CE(G).于是，對任意的 V1 JV(G),| V1|
12、=p-3 ,G-V1 必連通.因此必有 k(G)呈 p-2= B (G),但 k(G)三 B (G)。故 k(G) = B (G)。6.找出一個p階簡單圖，使$(G)=p3,但m(G)=K(G)=2故G-e2連通.由于G1-e2= (G-e2)-v1,故v1是G-e2的割點(diǎn)，且 v1在G-e2中的度小于等于3 ,于是類似于(2)知，在G-e2中存在一割邊el,即 (G-e2)-e1=G-e1,e2不連通,故入(G)=2.所以入(G)=K(G).(4)設(shè) k(G) =3,于是，有 3 =k (G)三 MG)WB(G)=3，知 k (G)=MG)與8 .證明：一個圖G是2-邊連通的當(dāng)且僅當(dāng)G的任意
13、兩個頂點(diǎn)由至少兩條邊不重的通路所 連通.分析：這個題的證明關(guān)鍵是理解2-邊連通的定義。證明：(必要性)因?yàn)镚是2-邊連通的，所以G沒有割邊。設(shè)u, v是G中任意兩個頂點(diǎn)， 由G的連通性知u, v之間存在一條路徑P1,若還存在從u到v的與P1邊不重的路徑P2, 設(shè)C=P1UP2,則C中含u,v的回路，若從u到v的任意另外路徑和P1都有一條(或幾條) 公共邊，也就是存在邊e在從u到v的任何路徑中，則從G中刪除e, G就不連通了，于是 e成了 G中一割邊，矛盾。(充分性)假設(shè)G不是一個2-邊連通白1則G中有割邊，設(shè)e=(u,v)為G中一割邊，由已知 條件可知，u與v處于同一簡單回路C中，于是e處在C
14、中，因而從G中刪除e后G仍然連 通，這與G中無割邊矛盾。9 .舉例說明：若在2 -連通圖G中，P是一條 (u,u )-通路，則G不一定包含一條與P內(nèi)部不相交的(u,u )-通路Q。解如右圖G,易知G是2一連通的，若取P為uv1v2v,則G中不存在Q 了。10 .證明：若G中無長度為偶數(shù)的回路,則G的每個塊或者是K2,或者是長度為奇數(shù)的回路.分析：塊是G的一個連通的極大不可分子圖，按照不可分圖的定義，有G的每個塊應(yīng)該是沒 有割點(diǎn)的。因此，如果能證明G的某個塊如果既不是K2 ,也不是長度為奇數(shù)的回路，再由 已知條件G中無長度為偶數(shù)的回路，則可得出G的這個塊肯定存在割點(diǎn)，則可導(dǎo)出矛盾。本 題使用反證
15、法。證明：設(shè)K是G的一個塊，若k既不是K2也不是奇回路，則k至少有三個頂點(diǎn)，且存在 割邊e=uv于是u,v中必有一個是割點(diǎn)，此與k是塊相矛盾。11 .證明：不是塊的連通圖G至少有兩個塊，其中每個塊恰含一個割點(diǎn).分析：一個圖不是塊，按照塊的定義，這個圖肯定含有割點(diǎn) v,對圖分塊的時候也應(yīng)該以割 點(diǎn)為標(biāo)準(zhǔn)進(jìn)行，而且分得的塊中必定含這個割點(diǎn)，否則所得到的子圖一定不是極大不可分子 圖，從而不會是一個塊。證明：由塊的定義知，若圖G不是塊且連通，則G有割點(diǎn)，依次在有割點(diǎn)的地方將 G分解 成塊，一個割點(diǎn)可分成兩塊，每個塊中含 G中的一個割點(diǎn)。如下圖Go易知u,v是割點(diǎn)，G可分成四個塊K1K4。其中每個塊恰含
16、一個割點(diǎn)。12.證明：圖G中塊的數(shù)目等于6(G )+ b (曄)-1)其中，b(v廢示包含u的塊的數(shù)目.- V G分析：一個圖G的非割點(diǎn)只能分布在G的一個塊中，即b(u)=1 (當(dāng)v是G的非割點(diǎn)時)，且 每個塊至少包含一個割點(diǎn)。因此下面就從 G的割點(diǎn)入手進(jìn)行證明。證明中使用了歸納法證明：先考慮G是連通的情況(MGH1),對G中的割點(diǎn)數(shù)n用歸納法 由于對G的非割點(diǎn)v, b(v)=1 ,即b(v)-1 =0,故對n=0時，G的塊數(shù)為1 + (bu泊)結(jié)論. V G成立。假設(shè)G中的割點(diǎn)數(shù)n0)時，結(jié)論成立。對門=卜+1的情況，任取G的一個割點(diǎn)a,可將G分解為連通子圖G,使得a在Gi中不是割 點(diǎn)，a又
17、是Gi的公共點(diǎn)。這樣，每一個 G,有且僅有一個塊含有a,若這些G共有個，則 b(a戶r,又顯然G的塊也是G的塊，且Gi的割點(diǎn)數(shù)li-1 =1 -三二垃；：卜1vVG由歸納法可知，當(dāng)G連通時，結(jié)論成立。當(dāng)G不連通時，對每個連通分支上述結(jié)論顯然成立。因此有圖G中塊的數(shù)目等于，Gr廿 -113 .給出一個求圖的塊的好算法。分析：設(shè)G是一個具有p個頂點(diǎn)，q條邊，w個連通分支的圖。求圖G的塊可先求圖G的任 一生成森林F,且對每一邊eF,求F+e中的唯一回路，設(shè)這些回路 C1, C2,，Cq-p+w都 已求得，(這些都有好算法)。在此基礎(chǔ)上，我們注意到，兩個回路(或一個回路與一個塊)若有多于1個公共點(diǎn)，則
18、它們屬于同一塊。止匕外，由割邊的定義知，G的任一割邊不含于任何回路中，且它們都是G的塊?；谶@些道理，可得如下求圖 G的塊的好算法。解：求圖的塊的算法：(1) 令 s=1, t=1, n=q-p+w(2)若n0,輸入C1, C2,，/ 否則，轉(zhuǎn)第4步。(3)若|V(Cs)CV(Cs+)中,令Cs=Cs=Cs+，且對 i=s+t,，n-1,令Ci =Ci由，n =n-1 ,轉(zhuǎn)第4步；否則，t=t+1,轉(zhuǎn)第5步。(4)若sn,令t=1,轉(zhuǎn)第3步；否則，算法停止(這時 C1, C2,，Cn與E (G) - C1 ,C2,，Cn中的每一邊都是G的塊)(5)若s+tn轉(zhuǎn)第3步；否則，s=s+1,轉(zhuǎn)第4步
19、。3步，比較Cs與Cs十的頂點(diǎn)尋本算法除了求回路有已知的好算法外，計算量主要在第找它們的公共點(diǎn)的運(yùn)算中，這些運(yùn)算不超出p2*(q-p+w)次，故是好算法14 .證明：H2r *p是(2r+1)連通的。分析：只要證明H2fp不存在少于2r+1個頂點(diǎn)的頂點(diǎn)割集。設(shè)V是一個|V|2r+1的任 一頂點(diǎn)子集，可分|V叫2r和|V|=2r兩種情形證明。證明：(1)當(dāng)|V|2r時，根據(jù)定理7.3.1的證明，V不是H2r,p的頂點(diǎn)割集，當(dāng)然更不是在H 2r 0上加些邊的H2r 的頂點(diǎn)割集。 A r , pr , p(2)當(dāng)|V|=2r時，設(shè)V是H 2fp的頂點(diǎn)割集，i，j屬于H2fp V的不同分支?？?察頂點(diǎn)
20、集合S =i,i 1,., j -1, j和T =j,j +1,.,i 1,i 這里加法取模n若S或T中有一個含V的頂點(diǎn)少于r個，則在H2td -V中存在從i到j(luò)的路。與V為 A r , p頂點(diǎn)割集矛盾。若S和T中都有V的r個頂點(diǎn)，則：若S或T中，有一個(不妨說S)中V的r個頂點(diǎn)不是相繼連成段，則S-V中存在從 i到j(luò)的路。與V為頂點(diǎn)割集矛盾。若S與T中，V的r個頂點(diǎn)都是相繼連成一段的。若S與T中至少有一個沒有被分 成兩段，則立即與V為頂點(diǎn)割集矛盾；若S-V被分成兩段：含i的記S1,含j的記S2 ,且T -V也被分為兩段：含i的記T1 ,含j的記T2。這樣，V -V被分為兩段：含i的 U T1
21、 和含j的S2UT2。這兩段都是連通的，且含i段的中間點(diǎn)(或最靠近中間的一點(diǎn))i0與含j段 的類似點(diǎn)j。滿足：jo = *i0i0n+ 2n 1+2(n為偶數(shù))(n為奇數(shù))故i0與j0有邊相連，在H2r書,p V中有路(i,.,i0, j0,., j),與V為頂點(diǎn)割集矛盾。綜上所述，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的構(gòu)造，可知 6 (Hm,n) 5 ,再由定理7.1.1可證。證明：由定理7.3.1知：K (Hm,n) =m 已知：k三入三B而 5 (
22、H m,n) = m.因止匕 m = k M 兒 M 6 = m.故九(Hm,n) =m.16.試畫出 H48、H58 和 H59.,分析：根據(jù)書上第54頁構(gòu)造H m,n的方法可構(gòu)造出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中添加連接頂點(diǎn)i+p/2(mod p)的邊，其中 1ip/2,：
23、1 一5; 2 6;3 7;4 0.則 H 5.8 圖如下(iii) H 5.9 圖:r=2,在H 4,.9圖上添加連接頂點(diǎn)0與 i + (p+1) /2(mod p)的邊，其中 1 i0個奇點(diǎn)，則G中存在k個邊互不重的鏈Q(jìng)1 Qk ,使得：1 , kE(G) =E(QJ . E)一. E(Qk)分析：一個圖的E回路去掉一條邊以后，將得到一條 E鏈。證明：設(shè) V1V2,，Vk,Vk書，V2k為G中的奇數(shù)度頂點(diǎn)，k 1在Vi和Vi+k之間用新邊ei連 接，i =1, 2.k,所得之圖記為G*,易知G*的每個頂點(diǎn)均為偶數(shù)，從而 G*存在E閉鏈C* 。 現(xiàn)從C*中刪去ei (i=1, 2.k),則C
24、*被分解成k條不相交的鏈Q(jìng)i( i =1, 2.k),顯然有：E(G) =E(Q1)一 E(Q2)一 E(Qk)6、證明：如果(1) G不是2連通圖，或者(2) G是二分圖,且XWY,則G不是H圖。 分析：G不是2連通圖，說明MG1 ,于是工口或K(G)=0 ,如果K(G)=0,則說明g 不連通，如G不連通，顯然G不是H圖，如K(G)=1則g中存在孤立點(diǎn)，因此有w(G-v)2, 由定理8.2.1G不是H圖。若G是二分圖 ,則X或Y中的任意兩個頂點(diǎn)不鄰接，因此G-X 剩下的是Y中的點(diǎn)，這些點(diǎn)都是孤立點(diǎn)；同樣 G-Y剩下的是X中的點(diǎn)，這些點(diǎn)也是孤立點(diǎn)；即 有叫G -X)卡|,8(G Y) =|X|
25、,如果x.丫，則有0 (G 一X)卡|鄧|或s (G -Y)平|Y|成立。無論哪個結(jié)論成立，根據(jù)定理 8.2.1都有G不是H圖。證明：若(1)成立則G不連通或者是G有割點(diǎn)u,若G不連通，則G不是H圖，若G有割點(diǎn)u, 取S=u,于是co (G-u) S因此 G不是H圖.若(2)成立，不妨設(shè)|X| |x| =|s|即：切(G -S) |S.因此G不是H圖.(G-S)S 1.7、證明:若 G是半H圖，則對于V(G)的每一個真子集S,有：分析：圖G的權(quán)與它的生成子圖G的連通分支數(shù)滿足：CO(G)(G)因?yàn)橐粋€圖的生成子圖是在該圖的基礎(chǔ)上去掉若干邊得到的，顯然去掉邊以后只能使該圖的連通分支增加。對于圖G
26、的一條H通路C,滿足任取Sc V , s(C -S) S +1.證明:設(shè)C是G的一條H通路，任取SUV,易知(C -S) p的頂點(diǎn)u,v,若uv*E(G),則將邊uv力口至U G中，得到G+uv,如此反復(fù)加邊，直到滿足d(u)+d(v) p的所有頂點(diǎn)均鄰接。由閉包的定義，如 果一個圖本身不存在任何一對頂點(diǎn)u,v,滿足d(u)+d(v)p,則它的閉包就是其自身。顯然可找到滿足這種條件的非完全圖。解：如右圖G, G=G,但G不是完全圖10、若G的任何兩個頂點(diǎn)均由一條 H通路連接著，則稱G是H連通的。 一 一 一， 一 一 1(1)證明：若G是H連通的，且p之4,則q之.1(3p+1)1 一、I(2
27、)對于p皂4,構(gòu)造一個具有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),所以qp*S(G)/2,因此如果能判斷S(G)3,則有 i 41q之pw 6(G)/2至3P/2之(3p+1)下面的證明關(guān)鍵是判斷S(G)3。證明：(1)任取we V(G),由于G是連通的，所以d(w)1op 4,所以GH通路與u與若d(w)=1,則與w鄰接的頂點(diǎn)u與w之間不可能有一條H通路連接它們，否則因?yàn)?中除了 u與w外還有其他頂點(diǎn)，因此，如果 u與w之間有一條H通路的話，這條 w的連線
28、就構(gòu)成了一個回路，這樣與 d(w)=1矛盾，所以d(w)w1；同樣的道理，若d(w)=2,則與w鄰接的頂點(diǎn)u與v之間不存在H通路。因此 8(G) 3o從而 2q=Ed(u)3p,即：2q3p,也即 q 3p/21- 八若p為奇數(shù)，于是q -(3p+1)；1(ii)若p為偶數(shù)，則3P為偶數(shù)，于是q 2(3p+1)；綜合以上各種情況，有:1q 至 q(3p + 1)；(2) (i )當(dāng)p=偶數(shù)時，q=3p/2,滿足條件的圖如下圖(a);40圖(a)11、證明：若G是一個具有p三28的連通簡單圖，則 G有一條長度至少是2 8的通路。分析：使用反證法，假設(shè)G中沒有一條長度大于或等于 2 8的通路。先找
29、到圖G的一條最長通路P,設(shè)其長度為m,由假設(shè)m2 8。再在P的基礎(chǔ)上構(gòu)造一條長度為 m+1的回路C,顯然C中包 含的頂點(diǎn)數(shù)小2 8,由于p皂28,所以圖G至少還有一個頂點(diǎn)v不在該圈中，又由于 G是連通 的，所以v到C上有一條通路P。于是P+C的長度等于通路P的長度的通路構(gòu)成了一條比 P更 長的通路，這與P是G的一條最長通路矛盾。從而本題可得到證明。證明：(用反證法)設(shè)p =VV 棟G的最長通路 淇長度為m,假設(shè)m5o由定義知：vm +更ST ,因止匕|sUT|wmM26 ,于是ST#中，事實(shí)上，= 2S A SJt = S + T -|st| S - SnT|=2 - SnT 二怕口丁 卜 0
30、,即 STQ。設(shè)丫1三$1丁#我從而有G中的長為 m+1的回路C： v1V2“ivivm41Vmvi+v1.因p 26, m+1 W26,所以，C外至少還有一個頂點(diǎn)v0 e V (G)。由G連通可知，有一條 P外的通路與C連接。不妨設(shè) v0vj WE (G) ,1EjEm+1.是有通路P ： V0VjVj 4V1Vi書VmVm由ViVi/V1.且P I A P ,此與P的假設(shè)矛盾！ 故結(jié)論成立。12、設(shè)p(豺階簡單圖G的度序列為：d1Wd2Wrqp.證明：若對任何m,117W(p1)/2,均有dmm右p為奇數(shù)，還有d1P布與(p1)則G是H圖。分析：由定理824,如果p (3)階簡單圖G的各頂
31、點(diǎn)度數(shù)序列di京2W玄p,而且又t任何mp-m,貝UG是H圖。卜面的證明就是利用這個定理來判斷當(dāng)mm。從而G是H圖。證明：對任何正整數(shù) m；E,2(1)若p為偶數(shù)(p之3),則必有：14mwB1=E_p二1 222即1 m m,再由定理8.2.4知G為H圖(2)若p為奇數(shù)，則m E p 1 (a)若m 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中，如果分別
32、去掉v3, v4和v5,則相應(yīng)得到的旅行推銷員問題的解分別取什么下 界估計值？ 分析：利用Kruskal算法可給出一個關(guān)于旅行推銷員問題的的下界估計式:任選賦權(quán)完全圖Kn的一個頂點(diǎn)v,用Kruskal算法求出Kn-v的最優(yōu)樹T,設(shè)C是最優(yōu)的H回路，于是有C-v也是Kn-v的一個生成樹，因此有：w(T) w(C-v)設(shè)e1和e2是Kn中與v關(guān)聯(lián)的邊中權(quán)最小的兩條邊，于是： w(T)+w(e1)+w(e2) w(C)上式左邊的表達(dá)式即是w(C)的下界估計式。解：(1)去掉v3后的最優(yōu)數(shù)T3的權(quán)為w(T3)=5+5+1+7=18，而與v3關(guān)聯(lián)的5條邊中權(quán)最小的兩條之權(quán)為w(e1)=8,w(e2)=9
33、，因此下界估計值為 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、設(shè)G是一種賦權(quán)完全圖，其中對任意 x,y,zC V(G),都滿足缶 僅十8 &Z 僅才： 證明：G中最優(yōu)H回路最多具有權(quán)28(T)其中T是G中的一棵最優(yōu)樹。分析：H回路是指從圖中某點(diǎn)出發(fā)，經(jīng)過圖中每個頂點(diǎn)有且僅有一次，最后回到出發(fā)點(diǎn)的一條回路。由于G是一種賦權(quán)完全圖，所以從任意頂點(diǎn)出發(fā)包括了 G的其他所有頂點(diǎn)有且僅有一次再回到原點(diǎn)的回路都構(gòu)成了 G的一條H回路C,且最優(yōu)H回路C
34、的權(quán)滿足。因此只428(C)%(C)E(O|v(G)|), Q中某些頂點(diǎn)可能有重復(fù)，且0 (Q)=28(T)在Q中，從v3開始，凡前面出現(xiàn)過的頂點(diǎn)全部刪去，得到 G的|v(G)由頂點(diǎn)的一個排列兀。由 于G是完全的，所以?？梢钥醋鱃中的一個H回路。在兀中任意邊(u,v),在T中對應(yīng)存在唯一 的(u,v)-通路P,由權(quán)的三角不等式有切(u,v)由于將兀中的邊(u,v)用T中的P來代替時，就得到Q,因而 (冗)抬(Q)=2o(T澈G中的最優(yōu)H回路C的權(quán) 切(C)tt(n)1是奇數(shù)。舉出沒有完美匹配的k -正則簡單圖的例子。分析：作G如下：取2k-1個頂點(diǎn)v1,2,v2ki,在奇足標(biāo)頂點(diǎn)和偶足標(biāo)頂點(diǎn)間
35、兩兩連以邊外，再連以V1V3,V5v7： ,V2k_5V2k工邊，所得圖記為G0,顯然G0除V2k外其余頂點(diǎn)的度均為k,而V2k 的度為k-1,取k個兩兩不相交的Go的拷貝和一個新頂點(diǎn)V0,并把每個Go拷貝中對應(yīng)于V2k的 頂點(diǎn)與Vo相連以邊。最后所得的圖記為G,顯然G是k-正則的簡單圖。又由于Go含2k-1個頂點(diǎn)， 則G的頂點(diǎn)數(shù)為：k*(2k-1)+1。所以如果G有一個完美匹配M的話，則k*(2k-1) 1 , 2 k-1|M|= - = k 。22假設(shè)M是G的一個完美匹配，則其邊應(yīng)來自k個獨(dú)立的Go,和跟Vo相關(guān)聯(lián)的一條邊。而每個Go,其包含的頂點(diǎn)數(shù)為2k-1,所以Go能提供給M的邊最多為
36、k-1條，k個這樣的Go能提22 k-1供給M的邊最多為k*(k-1),因此M最多包含的邊為k*(k-1)+1=k 2-(k-1)0時，Vi與v鄰接，并規(guī)定最后可下子的一方獲勝。若規(guī)定執(zhí)黑子者先下子，試證明執(zhí) 黑子的一方有取勝的策略當(dāng)且僅當(dāng) G無完美匹配。分析：假設(shè)G有完美匹配，則G的每個頂點(diǎn)都是M-飽和點(diǎn)，這樣先下者無論取哪個頂點(diǎn)，后下 者都可取其相鄰的M-飽和點(diǎn)，這樣先下的人必輸；因此先下的人如要贏的話，G中肯定無完美匹 配。反過來，如果G中無完美匹配，由于任何圖都有最大匹配，則可找到 G的一個最大匹配 M,由 于M不是完美匹配，因此 G中存在M-非飽和點(diǎn)v,先下的黑方就可找到這個點(diǎn)下，則
37、與 v相鄰 的下一個點(diǎn)必是M-飽和點(diǎn)，不然，M Uuv就是一個更大的匹配，與M是最大匹配矛盾。同理G 中不存在M可增廣路，故黑方所選vi必是M飽和點(diǎn)，如此下去，最后必是白方無子可下，故黑 方必勝。證明：必要性(反證法) 若G中存在一個完美匹配M ,則G中任何點(diǎn)v都是M飽和點(diǎn)。 故不論執(zhí)黑子(先下者)一方如何取 v一,白方總可以取M中和v關(guān)聯(lián)邊的另一端點(diǎn)作為M , 于是，黑方必輸。充分性.設(shè)G中不存在完美匹配，令M是G的最大匹配，而v0是非M飽和點(diǎn)。于是，黑方 可先取v0點(diǎn)，白方所選必必是M飽和點(diǎn)(因M是最大的匹配)由M的最大性可知G中不存 在M可增廣路，故黑方所選m必是M飽和點(diǎn)，如此下去，最后
38、必是白方無子可下，故黑方必勝。6 .證明：二分圖G有完美匹配當(dāng)且僅當(dāng)對任何 S v(G),有|s.|Ng(s)| 成立舉例說明若G不是二分圖，則上述條件未必充分。分析：由定理9.1.2Hall定理，對于具有二劃分(X,Y)的二分圖，G有飽和X中每個頂點(diǎn)的匹配 當(dāng)且僅當(dāng)對任意的SX ,|S|n是一個(0,1)矩陣.將M m沏表示成一個二分圖G(V1,V2 ,E),V1 =u1,，Un , V2 =必,，Vn .其中M(i, j) =1 當(dāng)且僅當(dāng)(Ui,Vj)w E(G)于是，G的(最小)點(diǎn)覆蓋數(shù)P(G)等于含M m看中元素1的行(第i行元素1的數(shù)目表示頂點(diǎn)ui 覆蓋的邊之?dāng)?shù)目)或列(第j列元素1
39、的數(shù)目表示頂點(diǎn)Vj覆蓋的邊數(shù)目)的數(shù)目。而 G的最大 匹配數(shù)a (G)等于M m坨中位于不同行不同列的1的最大數(shù)目.由定理9.2.2知，若G為二分圖，則a(G) = P(G)。故結(jié)論成立.9 .能否用5個1父2的長方表將圖9-13中的10個1父1正方形完全遮蓋?。繄D 9-13分析：按如下方法作出G圖：在圖9-13的每個正方形格子中放一個頂點(diǎn)，U與V鄰接當(dāng)且僅當(dāng)U與V所在的方格有公共邊。則該問題等價于判斷相應(yīng)圖G是否有完美匹配，解：按照分析，構(gòu)造圖G如下：則有O(G1=u|,由定理9.1.3可判斷它沒有完美匹 配。因此不能用5個1父2的長方表將圖9-13中的10個1父1正方形完全遮蓋住。110
40、.試證明：G是二分圖當(dāng)且僅當(dāng)對 G的每個子圖H均有 a(H ) - |V(H) |o2分析：若6= (X,Y)是二分圖，顯然X和Y都構(gòu)成G的點(diǎn)獨(dú)立集，所以G的最大獨(dú)立數(shù)ct(G)|X| , 且u(G)平|;而二分圖的每個子圖顯然也是二分圖。證明：必要性.設(shè)G是二分圖，于是 G的任何子圖 H也是二分圖，設(shè) H =(X,Y),|X | 十|Y|=|V(H)|。不妨設(shè) |X 戶|丫|。顯然 (H) | X |,因此，次之必mX|+|Y田|。于是，a(H)卻V(H)1。充分性.若G不是二分圖，則G中含奇回路C。令H =C。顯然，a(H ) = V(H)/2工工|V(H)|。矛盾。故G 是二分圖。481
41、1 .試證明：G是二分圖當(dāng)且僅當(dāng)對 G的每個適合6(H ) 0的子圖H ,均有a(H) = P(H). 分析：ot(G)是指G的最大獨(dú)立集，P 0 ,即H無孤立點(diǎn)。顯然H也是二分圖， 設(shè)H =(X,Y),且| X以丫 |。于是， u(H ) =|X |。而一條邊最多覆蓋一個頂點(diǎn)，故 pH) |X |o 但由于 H 無孤立點(diǎn)，因此，P(H) s(H)。矛盾。故 G 必為二分圖。12 .設(shè)G是具有劃分(X, Y)的二分圖。證明：若對于任何 uw X,vWY.均有d(u)之d(v), 則G有飽和X中每一頂點(diǎn)的匹配。分析：根據(jù)定理9.1.2,二分圖G有飽和X中每個點(diǎn)的匹配當(dāng)且僅當(dāng)對任何 S= X，有|
42、S四Ng(S)| 根據(jù)這個結(jié)論，如果能說明滿足條件的二分圖 G中不存在任何SG X ,有|S|Ng(S)| ,則題目 得證。證明：由題意知，對VuWX, d(u)之1。若G中不存在飽和X的匹配，則由Hall定理，存在S= X ,使|S| Ng(S)|。設(shè) S=u1 J ,um, Ng (S) =Vj ， ,其中 m n o1 ,n由對任何uWX,vWY, d(u)之d(v),得 d(u)至d d(v),但由于S中的點(diǎn)關(guān)聯(lián)的邊u Sv三Ng (S)都是Ng (S)的點(diǎn)關(guān)聯(lián)的邊，因此d d(u)d(ut)。矛盾。故G中存在飽和X的匹配。13.證明(Hall定理的推廣)：在以G(X,Y)為二劃分的二
43、分圖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
44、 x4914 .證明：在無孤立點(diǎn)的二分圖 G中，最大獨(dú)立集的頂點(diǎn)集“(G)等于最小邊覆蓋數(shù)P (H)。證明：參見題1115 .在9個人的人群中，假設(shè)有一個人認(rèn)識另外兩個人，有兩個人每人認(rèn)識另外4個人，有4個人認(rèn)識另外5個人，余下的兩個人每人認(rèn)識另外的6個人。證明：有3個人，他們?nèi)炕ハ嗾J(rèn)識。分析：將該題中的人用圖中的節(jié)點(diǎn)表示，兩個節(jié)點(diǎn)有連線當(dāng)且僅當(dāng)兩個人認(rèn)識，則該題轉(zhuǎn)化為求證滿足上述條件的圖G含有一個K3。要判斷一個圖是否含有 K3,我們先要了解以下概念和定理：T2, p：具有p個頂點(diǎn)的完全2分圖，如果p是偶數(shù)，則該圖的每一部分頂點(diǎn)數(shù)為 p/2;如果p為奇 數(shù)，則該圖的其中一部分頂點(diǎn)數(shù)為(p-1)/2,另一部分頂點(diǎn)數(shù)為(p+1)/2。Turan定理(托蘭定理)的推論：若簡單圖 G不含K3,則E(G) E(T2,p),且當(dāng)E(G)=E(T2,p)時， 有G三T2, p該定理的嚴(yán)格內(nèi)容為：若簡單圖G不含Km+1,則E(G)WE(Tm，p)
湘潭大學(xué)計算機(jī)科學(xué)與技術(shù)劉任任版離散數(shù)學(xué)課后習(xí)題答案---第二學(xué)期--圖論與組合數(shù)學(xué)
