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

《湘潭大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)劉任任版離散數(shù)學(xué)課后習(xí)題答案---第二學(xué)期--圖論與組合數(shù)學(xué)》由會(huì)員分享，可在線閱讀，更多相關(guān)《湘潭大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)劉任任版離散數(shù)學(xué)課后習(xí)題答案---第二學(xué)期--圖論與組合數(shù)學(xué)（88頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、習(xí)題六 1 .設(shè)G是一個(gè)無(wú)回路的圖，求證：若G中任意兩個(gè)頂點(diǎn)間有惟一的通路，則G是樹. 證明：由假設(shè)知，G是一個(gè)無(wú)回路的連通圖，故 G是樹。 2 .證明：非平凡樹的最長(zhǎng)通路的起點(diǎn)和終點(diǎn)均為懸掛點(diǎn). 分析：利用最長(zhǎng)通路的性質(zhì)可證。 證明：設(shè)P是樹T中的極長(zhǎng)通路。若P的起點(diǎn)v滿足d(v) >1 ,則P不是T中極長(zhǎng)的通路。對(duì) 終點(diǎn)u也可同理討論。故結(jié)論成立。 3 .證明：恰有兩個(gè)懸掛點(diǎn)的樹是一條通路. 分析：因?yàn)闃涫沁B通沒有回路的，所以樹中至少存在一條通路P。因此只需證明恰有兩個(gè) 懸掛點(diǎn)的樹中的所有的點(diǎn)都在這條通路 P中即可。 證明：設(shè)u,v是樹T中的兩個(gè)懸掛點(diǎn)，即d(u) =d(v)

2、 =1。因T是樹，所以存在(u,v)-通路 P ： uwi…WkV, k之0。顯然，d(Wi)之2。若d(Wi) >2 ,則由T恰有兩個(gè)懸掛點(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個(gè)懸掛點(diǎn). 分析：由于A(G )2k ,所以G中至少存在一個(gè)頂點(diǎn)v的度〉k,于是至少有k個(gè)頂點(diǎn)與 鄰接，又G是樹，所以G中沒有回路，因此與v鄰接的點(diǎn)往外延伸出去的分支中，每個(gè) 分支的最后一個(gè)頂點(diǎn)必定是一個(gè)懸掛點(diǎn)，因此 G中至少有k個(gè)懸掛點(diǎn)。 證明

3、：設(shè)u WV(G),且d(u)之m之k 。于是，存在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個(gè)懸掛點(diǎn)。 5 .設(shè)G(p,q謔一個(gè)圖，求證：若q之p,則G中必含回路. 分析：利用樹是沒有回路且連通的圖，且樹中的頂點(diǎn)數(shù)和邊數(shù)的關(guān)系可證。 證明：設(shè) G(p, q)有 k 個(gè)分支：GM]=G1(p1,q)…，G[Vk] = Gk(Pk,qk)。顯然， p = Pi +…+ Pk, q =q[ +…+qk。

4、若G無(wú)回路，則每個(gè)Gi 2 ,qj均是樹，i = 1,…，k。 于是qi = Pi -1, i =1,…，k。從而 q = p—kp-1. 分析：樹應(yīng)該是具有p個(gè)頂點(diǎn)中邊數(shù)最少的連通圖，而樹中的邊數(shù) q=p-1可證。 證明：設(shè)G是連通圖。若G無(wú)

5、回路，則G是樹，于是q = p-1。若G有回路，則刪去G中 k a0條邊使之保持連通且無(wú)回路。于是 q -k = p -1, IP q = p-1 +k > p -1o 9 .遞推計(jì)算K2 3的生成樹數(shù)目. K2,3 e 10 .通過(guò)考慮樹中的最長(zhǎng)通路，直接驗(yàn)證有標(biāo)記的5個(gè)頂點(diǎn)的樹的總數(shù)為125. 分析：設(shè)樹中5個(gè)頂點(diǎn)的標(biāo)記分別為1, 2, 3, 4,

6、 5。而5個(gè)頂點(diǎn)的樹的最長(zhǎng)通路只能是 4、 3、2,如下（1） （2） （3）所示。 （i）。 0 o 0 0最長(zhǎng)通路長(zhǎng)度為4； （2） q 0 Q q 最長(zhǎng)通路長(zhǎng)度為 3; O (3) 最長(zhǎng)通路長(zhǎng)度為2。 對(duì)于（1），把每個(gè)頂點(diǎn)看作是一個(gè)空，不同的頂點(diǎn)序列對(duì)應(yīng)不同的樹，但由于對(duì)稱性12345和54321 所形成的樹應(yīng)該是同一棵樹，因此這種情況下所有有標(biāo)記的樹的數(shù)目為： 5! /2=60個(gè)； 對(duì)于（2）,把上面四個(gè)頂點(diǎn)分別看作一個(gè)空，在構(gòu)造樹的時(shí)候可以先構(gòu)造這四個(gè)頂點(diǎn)，剩下的一 個(gè)頂點(diǎn)只能放在下面，選擇上面四個(gè)頂點(diǎn)的數(shù)目應(yīng)為可以從所有有標(biāo)記的樹的數(shù)目為 4 C5 *4

7、!,但同樣由對(duì)稱性，如1234這樣的排列和頂點(diǎn)5構(gòu)成的樹與1235這樣的排列和4構(gòu) 成的數(shù)是一樣的。因此這種情況下所有有標(biāo)記的樹的數(shù)目為： C54 *4! /2=60個(gè)； 對(duì)于（3）,只要確定了中間度為4的頂點(diǎn)，這棵樹就構(gòu)造完了，所有這種情況下有標(biāo)記的樹的數(shù) 目為：C5 =5個(gè)； 解：有標(biāo)記的5個(gè)頂點(diǎn)的樹的總數(shù)為：60+60+5=125個(gè)。 11 .用T(n所示n個(gè)頂點(diǎn)的有標(biāo)記樹的個(gè)數(shù),求證: n _1 2 n -1T n 八 k n - k T k T n - k Ck k 1 由此得恒等式 n 1 k _1 n -k-1 k n _2 k n - k Cn = 2 n

8、-1 n k 4 分析：每個(gè)n階樹可由下面的方法構(gòu)造出來(lái)：先從這n個(gè)頂點(diǎn)中任取k個(gè)頂點(diǎn)構(gòu)造出一個(gè)k階樹， 對(duì)剩下的n-k個(gè)頂點(diǎn)構(gòu)造出一個(gè)n-k階樹，再將這兩個(gè)樹合并成一個(gè)樹，顯然這樣得到的樹是一 個(gè)n階的樹。又由定理6.2.4有i個(gè)頂點(diǎn)的無(wú)標(biāo)記的生成樹共有ii-2個(gè)，可得下面的證明。 證明：任取k個(gè)頂點(diǎn)白一棵k階樹與(n )個(gè)頂點(diǎn)構(gòu)成的n 階樹之間連接兩點(diǎn)就是一棵 n階樹， 這里有k (n -k)種連接。并注意到一來(lái)一往每條邊用了兩次，因此，k (n *) T(k) t (n -k)Cnk =2T(n)。 n -1 上式兩邊對(duì) k從 1 到 nT 求和，得 2(n—1)T(n) =

9、 k(n -k)T(k)T(n -k)C：。再將 T(n) = nn N k=1 T(k) = kk N T (n *)= (n *)n*N代入上式便可得恒等式: n 1 k 1 n4」k n -2 % k (n -k) Cn = 2(n -1)n k 1 12 .如何用Kruskal算法求賦權(quán)連通圖的權(quán)最大的生成樹(稱為最大樹)？ 證明：將Kruskal算法中的“小”改成“大”即可得到“最大樹” 13 .設(shè)G是一個(gè)賦權(quán)連通圖，V(G ) = "2,…，ntn至2.求證：按下列步驟(Prim算法)可 以得出G的一個(gè)最優(yōu)樹. (i )置U :=1,T :=0 ； (ii )選

10、取滿足條件i WU, jWV(G )—U且C(i,j垠小的(i, j)； (iii ) T:TU《,j[U :=UU{j}； (iv )若U #V(G )則轉(zhuǎn)(ii ),否則停止,T中的邊就是最優(yōu)樹的邊. . \ * ，一… … ? . * 、一 .. 解：(1)設(shè)T是按Prim算法得出的圖。由Prim算法的初值及終止條件，可知 T連通，且 * . . . * … * T為G的生成子圖。又由(ii)知 T無(wú)回路。故T是生成樹。 (2)設(shè)T(G) ={T |T是G的生成樹，T #T },仿定理6.3.1的證明，可證結(jié)論成立。 14 .按題13的Prim

11、算法，求出圖6. 9的最優(yōu)樹. 解：最優(yōu)樹如下。(權(quán)為20) 習(xí)題七 1.對(duì)圖7.7中的兩個(gè)圖，各作出兩個(gè)頂點(diǎn)割。 (b) 7.7 解： 對(duì)圖7.7增加加節(jié)點(diǎn)標(biāo)記如下圖所示, V11={a,b}； V21={u,v}： V12={c,d} V12={y} 5 2.求圖7.7中兩個(gè)圖的K(G刑MG ). 則(a)的兩個(gè)頂點(diǎn)割為: (b)的兩個(gè)頂點(diǎn)割為： 解：如上兩個(gè)圖，有 k(G1)=入(G1)=2, k(G2)=1,入(G2)=2 3.試作出一個(gè)連通圖G ,使之滿足：MG )= MG )="G ) 解：做連通圖G如下，于是有：k(G) = K(G) =

12、&(G) 4 .求證，若G(p,q誕k -邊連通的，則q之kp/2. 證明：設(shè)G是k一邊連通的，由定義有入(G)呈k.又由定理7.1.2知入(G)三 三入(G)三 2q/ 2q/ 即kw 2q/ ,從而 P q-kp2 17p 一 / p 5 .求證，若G是p階簡(jiǎn)單圖，且S(G心p-2,則它G)=譏G) 分析：由G是簡(jiǎn)單圖，且d(G )> p-2,可知G中的B (G)只能等于p-1或p-2； 如B(G戶p-1,則G是一個(gè)完全圖,根據(jù)書中規(guī)定，有 k(G戶p-1=B(G); 如B (G戶p-2,則從G中任取V (G)的子集V1 ,其中|V1|=3,則V(G)-V

13、1的點(diǎn)導(dǎo)出子圖是連 通的，否則在V1中存在一個(gè)頂點(diǎn)v,與其他兩個(gè)頂點(diǎn)都不連通。則在 G中，頂點(diǎn)v最多與 G中其他p-3個(gè)頂點(diǎn)鄰接，所以d(v)k-3,又根據(jù)定義7.1.1,鞏G譯(G), 有 k(G)=k-2。 證明：因?yàn)镚是簡(jiǎ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不鄰接，但對(duì)任意的wCV(G),有 u

14、w,vw CE(G).于是，對(duì)任意的 V1 JV(G), | V1|=p-3 ,G-V1 必連通. 因此必有 k(G)呈 p-2= B (G),但 k(G)三 B (G)。 故 k(G) = B (G)。 6.找出一個(gè)p階簡(jiǎn)單圖，使$(G)=p—3,但m(G)<6(G) 7 .設(shè)G為3 -正則簡(jiǎn)單圖，求證父(G)=MG) 分析：G是一個(gè)3 -正則簡(jiǎn)單圖，所以B(G)=3,根據(jù)定理7.1.1有m(GE尢(GE&(G),所以 K(G W能等于0, 1, 2, 3這四種情況。下面的證明中分別討論了這四種情況下 k(G即九(G ) 的關(guān)系。 證明：(1)若k(G戶0,則G不連通,

15、所以入(G戶K(G). (2)設(shè)K(G)=1,且u是G中的一個(gè)割點(diǎn)，G-u不連通曲于d(u)=3,從而至少存在一個(gè)分 支僅一邊與u相連，顯然這邊是G的割邊，故入(G)= 1 ,所以入(G戶K(G) (3 )設(shè)K(G)=2,且｛v1,v2｝為G的一個(gè)頂點(diǎn)割。G1=G-v1連通則v2是G1的割點(diǎn)且v2 在G1中的度小于等于3 ,類似于(2)知在G1中存在一割邊e2(關(guān)聯(lián)v2)使得G1-e2不連通.另 一方面由于入(G)>=K(G)=2故G-e2連通.由于G1-e2= (G-e2)-v1,故v1是G-e2的割點(diǎn)，且 v1在G-e2中的度小于等于3 ,于是類似于(2)知，在G-e2中存在一割邊el

16、,即 (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è)圖G是2-邊連通的當(dāng)且僅當(dāng)G的任意兩個(gè)頂點(diǎn)由至少兩條邊不重的通路所 連通. 分析：這個(gè)題的證明關(guān)鍵是理解2-邊連通的定義。 證明：(必要性)因?yàn)镚是2-邊連通的，所以G沒有割邊。設(shè)u, v是G中任意兩個(gè)頂點(diǎn)， 由G的連通性知u, v之間存在一條路徑P1,若還存在從u到v的與P1邊不重的路徑P2, 設(shè)C=P1UP2,則C中含u,v的回路，若從u到v的任意另外路徑和P1都有一

17、條(或幾條) 公共邊，也就是存在邊e在從u到v的任何路徑中，則從G中刪除e, G就不連通了，于是 e成了 G中一割邊，矛盾。 (充分性)假設(shè)G不是一個(gè)2-邊連通白1則G中有割邊，設(shè)e=(u,v)為G中一割邊，由已知 條件可知，u與v處于同一簡(jiǎn)單回路C中，于是e處在C中，因而從G中刪除e后G仍然連 通，這與G中無(wú)割邊矛盾。 9 .舉例說(shuō)明：若在2 -連通圖G中，P是一條 (u,u )-通路，則G不一定包含一條與P內(nèi)部不相 交的(u,u )-通路Q。 解如右圖G,易知G是2一連通的， 若取P為uv1v2v, 則G中不存在Q 了。 10 .證明：若G中無(wú)長(zhǎng)度為偶數(shù)的回路,則G的每個(gè)塊

18、或者是K2,或者是長(zhǎng)度為奇數(shù)的回 路. 分析：塊是G的一個(gè)連通的極大不可分子圖，按照不可分圖的定義，有G的每個(gè)塊應(yīng)該是沒 有割點(diǎn)的。因此，如果能證明G的某個(gè)塊如果既不是K2 ,也不是長(zhǎng)度為奇數(shù)的回路，再由 已知條件G中無(wú)長(zhǎng)度為偶數(shù)的回路，則可得出G的這個(gè)塊肯定存在割點(diǎn)，則可導(dǎo)出矛盾。本 題使用反證法。 證明：設(shè)K是G的一個(gè)塊，若k既不是K2也不是奇回路，則k至少有三個(gè)頂點(diǎn)，且存在 割邊e=uv于是u,v中必有一個(gè)是割點(diǎn)，此與k是塊相矛盾。 11 .證明：不是塊的連通圖G至少有兩個(gè)塊，其中每個(gè)塊恰含一個(gè)割點(diǎn). 分析：一個(gè)圖不是塊，按照塊的定義，這個(gè)圖肯定含有割點(diǎn) v,對(duì)圖分塊的時(shí)候也應(yīng)

19、該以割 點(diǎn)為標(biāo)準(zhǔn)進(jìn)行，而且分得的塊中必定含這個(gè)割點(diǎn)，否則所得到的子圖一定不是極大不可分子 圖，從而不會(huì)是一個(gè)塊。 證明：由塊的定義知，若圖G不是塊且連通，則G有割點(diǎn)，依次在有割點(diǎn)的地方將 G分解 成塊，一個(gè)割點(diǎn)可分成兩塊，每個(gè)塊中含 G中的一個(gè)割點(diǎn)。如下圖Go 易知u,v是割點(diǎn)，G可分成四個(gè)塊K1?K4。其中每個(gè)塊恰含一個(gè)割點(diǎn)。 12.證明：圖G中塊的數(shù)目等于 6(G )+ b (曄)-1) 其中，b(v廢示包含u的塊的數(shù)目. - V G 分析：一個(gè)圖G的非割點(diǎn)只能分布在G的一個(gè)塊中，即b(u)=1 (當(dāng)v是G的非割點(diǎn)時(shí))，且 每個(gè)塊至少包含一個(gè)割點(diǎn)。因此下面就從 G的割點(diǎn)入手

20、進(jìn)行證明。證明中使用了歸納法 證明：先考慮G是連通的情況(MGH1),對(duì)G中的割點(diǎn)數(shù)n用歸納法 由于對(duì)G的非割點(diǎn)v, b(v)=1 ,即b(v)-1 =0,故對(duì)n=0時(shí)，G的塊數(shù)為1 + (bu泊)結(jié)論 . V G 成立。 假設(shè)G中的割點(diǎn)數(shù)n0)時(shí)，結(jié)論成立。 對(duì)門=卜+1的情況，任取G的一個(gè)割點(diǎn)a,可將G分解為連通子圖G,使得a在Gi中不是割 點(diǎn)，a又是Gi的公共點(diǎn)。這樣，每一個(gè) G,有且僅有一個(gè)塊含有a,若這些G共有「?jìng)€(gè)，則 b(a戶r,又顯然G的塊也是G的塊，且Gi的割點(diǎn)數(shù)li

21、v)是Gi中含v的塊的塊數(shù)，注意到Gi中異于a的v, :V Gi b(v)= bi(v),而a在每一個(gè)Gi中均為非割點(diǎn)，故bi(a)(i=1,2「,r)。于是Gi的塊數(shù)為 1 % b -1 (i=1,2, ,r) 將所有Gi的塊全部加起來(lái)，則得到G的塊數(shù)為: 上:.biu )1 =r -- 期。卜1 =1+(r-1) 一 ;b。,； >-1 =1 -三二垃’；：卜1 v「VG 由歸納法可知，當(dāng)G連通時(shí)，結(jié)論成立。 當(dāng)G不連通時(shí)，對(duì)每個(gè)連通分支上述結(jié)論顯然成立。 因此有圖G中塊的數(shù)目等于 ，Gr廿 -1 13 .給出一個(gè)求圖的塊的好算法。 分析：設(shè)G是一個(gè)具有p個(gè)頂點(diǎn)，q條

22、邊，w個(gè)連通分支的圖。求圖G的塊可先求圖G的任 一生成森林F,且對(duì)每一邊e^F,求F+e中的唯一回路，設(shè)這些回路 C1, C2,…，Cq-p+w都 已求得，(這些都有好算法)。在此基礎(chǔ)上，我們注意到，兩個(gè)回路(或一個(gè)回路與一個(gè)塊) 若有多于1個(gè)公共點(diǎn)，則它們屬于同一塊。止匕外，由割邊的定義知， G的任一割邊不含于任 何回路中，且它們都是G的塊?；谶@些道理，可得如下求圖 G的塊的好算法。 解： 求圖的塊的算法： (1) 令 s=1, t=1, n=q-p+w (2)若n>0,輸入C1, C2,…，/ 否則，轉(zhuǎn)第4步。 (3)若|V(Cs)CV(Cs+)中,令Cs=Cs=Cs+，且

23、對(duì) i=s+t,…，n-1,令 Ci =Ci由，n =n-1 ,轉(zhuǎn)第4步；否則，t=t+1,轉(zhuǎn)第5步。 (4)若s

24、。設(shè)V是一個(gè)|V|<2r+1的任 一頂點(diǎn)子集，可分|V叫2r和|V|=2r兩種情形證明。 證明： (1)當(dāng)|V|<2r時(shí)，根據(jù)定理7.3.1的證明，V’不是H2r,p的頂點(diǎn)割集，當(dāng)然更不是在 H 2r 0上加些邊的H2r 的頂點(diǎn)割集。 A r , p r , p (2)當(dāng)|V|=2r時(shí)，設(shè)V是H 2fp的頂點(diǎn)割集，i，j屬于H2fp —V的不同分支。考 察頂點(diǎn)集合 S ={i,i 1,..., j -1, j} 和T ={j,j +1,...,i —1,i} 這里加法取模n 若S或T中有一個(gè)含V的頂點(diǎn)少于r個(gè)，則在H2td -V中存在從i到j(luò)的路。與V為 A r , p 頂點(diǎn)

25、割集矛盾。 若S和T中都有V的r個(gè)頂點(diǎn)，則： 若S或T中，有一個(gè)(不妨說(shuō)S)中V的r個(gè)頂點(diǎn)不是相繼連成段，則S-V中存在從 i到j(luò)的路。與V為頂點(diǎn)割集矛盾。 若S與T中，V的r個(gè)頂點(diǎn)都是相繼連成一段的。若S與T中至少有一個(gè)沒有被分 成兩段，則立即與V為頂點(diǎn)割集矛盾；若S-V被分成兩段：含i的記S1,含j的記S2 , 且T -V也被分為兩段：含i的記T1 ,含j的記T2。這樣，V -V被分為兩段：含i的 U T1 和含j的S2UT2。這兩段都是連通的，且含i段的中間點(diǎn)(或最靠近中間的一點(diǎn))i0與含j段 的類似點(diǎn)j。滿足： jo = * i0 i0 n + — 2 n 1

26、+ 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 (H m,n) = m.因止匕 m = k M 兒 M 6 = m. 故九(Hm,n)

27、=m. 16.試畫出 H48、H58 和 H59 . . ., 分析：根據(jù)書上第54頁(yè)構(gòu)造H m,n的方法可構(gòu)造出H48、H58和H59。 . . ., (i) H4.8: r = 2 ,p=8對(duì)任意 i,j € V( H4.8), I i- j i—j 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=7 H 4,8圖 (ii) H5.8圖：r =2,p=8,則在H 4.8中添加連接頂點(diǎn) i+p/2(mod p)的邊，其中 1

28、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 < i< (p-1) /2和(p+1) /2的邊，以及頂點(diǎn)i與 (p-1) /2. i =0, j =8,7 「= 9

29、j = 8,7 :0一4; 0 一5; 一 6； i = 1, j =8 『 二 10， j? = 8 2 一 7; 3 — 8. 則H5.9圖如下: 8 0 7 6 2 3 5 4 H 5,9圖 習(xí)題8 1、圖中8.10中哪些是E圖？哪些是半E圖? (a) (b) (c) 分析：根據(jù)歐拉定理及其推論，E圖是不含任何奇點(diǎn)的圖，半 E圖是最多含兩個(gè)奇點(diǎn)的圖。 解： (a)半E圖。(b) E圖。 (c)非半E圖和E圖 2、試作出一個(gè)E圖G(p,q),使得p與q均為奇數(shù)。能否作出一個(gè)E圖G(p,q),使得p為偶數(shù)，而q 為奇數(shù)

30、？如果是p為奇數(shù)，q為偶數(shù)呢？ 解：以下E圖中，p與q 的奇偶如下表 P q G1 奇數(shù) 奇數(shù) G2 偶數(shù) 奇數(shù) G3 奇數(shù) 偶數(shù) Gi G2 G3 3、求證：若G是E圖，則G 的每個(gè)塊也是 E圖。 分析：一個(gè)圖如果含有E回路，則該圖是E圖; 另一方面一個(gè)塊是G中不含割點(diǎn)的極大連通不可 分子圖，且非割點(diǎn)不可能屬于兩個(gè)或兩個(gè)以上的塊。這樣沿 G中的一條E回路遍歷G的所有邊 時(shí)，從一個(gè)塊到達(dá)另一個(gè)塊時(shí)，只能經(jīng)過(guò)割點(diǎn)才能實(shí)現(xiàn)。 證明：設(shè)B是G的塊，任取G中一條E回路C,由B中的某一點(diǎn)v出發(fā)，沿C前進(jìn)，C只有經(jīng) 過(guò)G的割點(diǎn)才能離開B,也就

31、是說(shuō)只有經(jīng)過(guò)同一個(gè)割點(diǎn)才能回到 B中，注意到這個(gè)事實(shí)后，我們 將C中屬于B外的一個(gè)個(gè)閉筆回路除去，最后回到 v時(shí)，我們得到的就是B上的一個(gè)E回路, 所以B也是E圖。 4、求證：若G無(wú)奇點(diǎn)，則G中存在邊互不重的回路 Ci, ，Cm使得 E(G) =E(Ci) - E(C2)- - E(Cm) 分析：G中無(wú)奇點(diǎn)，則除了孤立點(diǎn)后其他所有點(diǎn)的度至少為 2,而孤立點(diǎn)不與任何邊關(guān)聯(lián)，因此 在分析由邊構(gòu)成的回路時(shí)可以不加考慮；而如果一個(gè)圖所有的頂點(diǎn)的度至少為 2,則由第五章習(xí) 題18知該圖必含回路。 證明：將G中孤立點(diǎn)去掉以后得到圖 G1,顯然G1也是一個(gè)無(wú)奇點(diǎn)的E圖，且"G1)22。由第 五

32、章習(xí)題18知，G1必含有回路C1;在圖G1-C1中去掉孤立點(diǎn)，得圖 G2,顯然G2仍然是一個(gè) 無(wú)奇點(diǎn)的圖，且6(G2)及，于是G2中也必含回路C2,…如此直到Gm中有回路Cm,且Gm-Cm 全為孤立點(diǎn)為止，于是有： E(G) =E(G) 一 E&) 一 一 E(Cm) 5、求證：若G有2k>0個(gè)奇點(diǎn)，則G中存在k個(gè)邊互不重的鏈 Q1… Qk ,使得： 1 , , k E(G) =E(QJ .. E@)「一. E(Qk) 分析：一個(gè)圖的E回路去掉一條邊以后，將得到一條 E鏈。 證明：設(shè) V1V2,…，Vk,Vk書，…，V2k為G中的奇數(shù)度頂點(diǎn)，k> 1在Vi和Vi+k之間用新邊ei連

33、 接，i =1, 2….k,所得之圖記為G*,易知G*的每個(gè)頂點(diǎn)均為偶數(shù)，從而 G*存在E閉鏈C* 。 現(xiàn)從C*中刪去ei (i=1, 2….k),則C*被分解成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—連通圖，說(shuō)明MG^1 ,于是工⑸口或K(G)=0 ,如果K(G)=0,則說(shuō)明g 不連通，如G不連通，顯然G不是H圖，如K(G)=1則g中存在孤立點(diǎn)，因此有w(G-v)>2, 由定理8.2.1G不是H圖。若G是

34、二分圖 ,則X或Y中的任意兩個(gè)頂點(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|,如果x.丫，則有0 (G 一X)卡|鄧|或s (G -Y)平|>Y|成立。 無(wú)論哪個(gè)結(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| <|丫|.令$ = *,則 金(g - S) =|y|>|x| =|s| 即：切

35、(G -S) >|S. 因此G不是H圖. (G-S)^S 1. 7、證明:若 G是半H圖，則對(duì)于V(G)的每一個(gè)真子集S,有： 分析：圖G的權(quán)與它的生成子圖 G的連通分支數(shù)滿足： CO(G)"(G)因?yàn)橐粋€(gè)圖的生成子圖 是在該圖的基礎(chǔ)上去掉若干邊得到的，顯然去掉邊以后只能使該圖的連通分支增加。 對(duì)于圖G的一條H通路C,滿足任取Sc V , s(C -S) < S +1. 證明:設(shè)C是G的一條H通路，任取SUV,易知 (C -S) < S 1. 而 C-S 是 G-S 的生成子圖. 故②(G—S) Wco(C—S)w S+1.故與(G — S)〈S+1. 8、試述H圖

36、與E圖之間的關(guān)系。 分析：H圖是指存在一條從某個(gè)點(diǎn)出發(fā)經(jīng)過(guò)其他頂點(diǎn)有且僅有一次的回路；而 E圖是指從某點(diǎn)出 發(fā)通過(guò)圖中所有的邊一次且僅有一次的回路。 從定義可看出，這兩者之間沒有充分或必要的關(guān)系。 解：考慮如下四個(gè)圖： 易知G1是E圖，但非H圖；G2是H圖，但非E圖；G3既非E圖，又非H圖；G4既是E圖，也 是H圖。 9、作一個(gè)圖，它的閉包不是完全圖 分析：一個(gè)p階圖的閉包是指對(duì)G中滿足d(u)+d(v)> p的頂點(diǎn)u,v,若uv*E(G),則將邊uv力口至U G中，得到G+uv,如此反復(fù)加邊，直到滿足d(u)+d(v) >p的所有頂點(diǎn)均鄰接。由閉包的定義，如 果一個(gè)圖本身不存

37、在任何一對(duì)頂點(diǎn) u,v,滿足d(u)+d(v)>p,則它的閉包就是其自身。顯然可找到 滿足這種條件的非完全圖。 解：如右圖G, G=G,但G不是完全圖 10、若G的任何兩個(gè)頂點(diǎn)均由一條 H通路連接著，則稱G是H連通的。 一 一 一，， 一 一 1 (1)證明：若G是H連通的，且p之4,則q之.1(3p+1) 1 一、I (2)對(duì)于p皂4,構(gòu)造一個(gè)具有q = J (3p +1)的H連通圖Go 2 39 p p 分析：根據(jù)定理5.3.1有2q = d(vi),因此q = d(Vi)/2 i 1 i =1 P 而Z d(vi)之P* 6(G),所以q>p*S(G)

38、/2,因此如果能判斷S(G)>3,則有 i 4 1 q之pw 6(G)/2至3P/2之『(3p+1)下面的證明關(guān)鍵是判斷S(G)>3。 證明：(1)任取we V(G),由于G是連通的，所以d(w)>1o p> 4,所以G H通路與u與 若d(w)=1,則與w鄰接的頂點(diǎn)u與w之間不可能有一條H通路連接它們，否則因?yàn)?中除了 u與w外還有其他頂點(diǎn)，因此，如果 u與w之間有一條H通路的話，這條 w的連線就構(gòu)成了一個(gè)回路，這樣與 d(w)=1矛盾，所以d(w)w1； 同樣的道理，若d(w)=2,則與w鄰接的頂點(diǎn)u與v之間不存在H通路。 因此 8(G) >3o 從而 2q=Ed(u)>

39、3p, 即：2q>3p,也即 q > 3p/2 1- 八 ⑴若p為奇數(shù)，于是 q ^-(3p+1)； 1 (ii)若p為偶數(shù)，則3P為偶數(shù)，于是 q ^2(3p+1)； 綜合以上各種情況，有: 1 q 至 q(3p + 1)； (2) (i )當(dāng)p=偶數(shù)時(shí)，q=3p/2,滿足條件的圖如下圖(a); 40 圖(a) 11、證明：若G是一個(gè)具有p三28的連通簡(jiǎn)單圖，則 G有一條長(zhǎng)度至少是2 8的通路。 分析：使用反證法，假設(shè)G中沒有一條長(zhǎng)度大于或等于 2 8的通路。先找到圖G的一條最長(zhǎng)通路 P,設(shè)其長(zhǎng)度為m,由假設(shè)m<2 8。再在P的基礎(chǔ)

40、上構(gòu)造一條長(zhǎng)度為 m+1的回路C,顯然C中包 含的頂點(diǎn)數(shù)小<2 8,由于p皂28,所以圖G至少還有一個(gè)頂點(diǎn)v不在該圈中，又由于 G是連通 的，所以v到C上有一條通路P。于是P+C的長(zhǎng)度等于通路P的長(zhǎng)度的通路構(gòu)成了一條比 P更 長(zhǎng)的通路，這與P是G的一條最長(zhǎng)通路矛盾。從而本題可得到證明。 證明：(用反證法)設(shè) p =VV… 棟G的最長(zhǎng)通路 淇長(zhǎng)度為m,假設(shè)m<2 8。 由P是G的最長(zhǎng)通路，則V1,Vm+1只3與P中的頂點(diǎn)相鄰，注意到 G是簡(jiǎn)單圖 令S ={Vi V2 i E(G)}, T ={Vi vm a E(G)} ,二 S =d (vi)至 6,T =d (vm韋)>5o 由定義

41、知： vm +更S」T ,因止匕|sUT|wmM26 ,于是S^T#中， 事實(shí)上，= 2S A SJt = S + T -|s^t|^^ S> - SnT|=2^ - SnT 二怕口丁 卜 0,即 S^TQ。 設(shè)丫1三$1丁#我從而有G中的長(zhǎng)為 m+1的回路C： v1V2“ivivm41Vm…vi+v1. 因p >26, m+1 W26,所以，C外至少還有一個(gè)頂點(diǎn) v0 e V (G)。 由G連通可知，有一條 P外的通路與C連接。不妨設(shè) v0vj WE (G) ,1EjEm+1. 是有通路P ： V0VjVj 4…V1Vi書…VmVm由ViVi/…V1.且P I A P ,此與P的假

42、設(shè)矛盾！ 故結(jié)論成立。 12、設(shè)p(豺階簡(jiǎn)單圖G的度序列為：d1Wd2Wrqp.證明：若對(duì)任何m, 1 17W(p—1)/2,均有dm>m右p為奇數(shù)，還有d1P布與(p—1)則G是H圖。 分析：由定理824,如果p (>3)階簡(jiǎn)單圖G的各頂點(diǎn)度數(shù)序列 di京2W」玄p,而且又t任何m

p-m,貝UG是H圖。 卜面的證明就是利用這個(gè)定理來(lái)判斷當(dāng) m

m。從而G是H圖。 證明：對(duì)任何正整數(shù) m；E, 2 (1)若p為偶數(shù)(p之3),則必有：14mwB—1=E^<_p二1 2 2 2 即1

43、1)/2，由題設(shè)有dm >m,再由定理8.2.4知G為H圖 (2)若p為奇數(shù)，則m E p 1 (a)若m < p 1,則由題設(shè)有dm > m, 2 2 p -1 p-1 (b^m= ，地 p—m=p— = 2 2 1 口 r 于是 dp_m =d 1 > ( p -1)Wd p_m 至 (p 1) 2 2 L  2 p - p 1 p 1 2 一 2 1 (p—1)+1 = p — m,也即 dp_m 至 p — m, 2 從而，由定理8.2.4知，G是H圖。 13、在圖8-8中，如果分別去掉v3, v4和v5,則相應(yīng)得到的旅行推銷員問(wèn)題的解分別取什么下 界

44、估計(jì)值？ 分析：利用Kruskal算法可給出一個(gè)關(guān)于旅行推銷員問(wèn)題的的下界估計(jì)式: 任選賦權(quán)完全圖Kn的一個(gè)頂點(diǎn)v,用Kruskal算法求出Kn-v的最優(yōu)樹T,設(shè)C是最優(yōu)的 H回路，于是有C-v也是Kn-v的一個(gè)生成樹，因此有：w(T) < w(C-v) 設(shè)e1和e2是Kn中與v關(guān)聯(lián)的邊中權(quán)最小的兩條邊，于是： w(T)+w(e1)+w(e2)

45、+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)完全圖，其中對(duì)任意 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)過(guò)圖中每個(gè)頂點(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的權(quán)滿足

46、。因此只 42 8(C)%(C) E(O<2(T) 需證明G中存在一條H回路C,其權(quán) 即可，因此證明本題的關(guān)鍵是找到滿足這 個(gè)結(jié)論的H回路C。 證明：設(shè)T是G中的一棵最優(yōu)樹，將T的每邊加倍得到圖T,則T的每個(gè)頂點(diǎn)的度數(shù)均為偶數(shù)。 所以T有一歐拉回路Q,設(shè)Q=(v1, v2，…，vn,v1), (n>|v(G)|), Q中某些頂點(diǎn)可能有重復(fù)， 且 0 (Q)=28(T) 在Q中，從v3開始，凡前面出現(xiàn)過(guò)的頂點(diǎn)全部刪去，得到 G的|v(G)由頂點(diǎn)的一個(gè)排列兀。由 于G是完全的，所以?？梢钥醋鱃中的一個(gè)H回路。在兀中任意邊(u,v),在T中對(duì)應(yīng)存在唯一 的(u,v)-通路P,由權(quán)的三

47、角不等式有 切(u,v))由于將兀中的邊(u,v)用T中的P來(lái)代替時(shí)，就得到Q,因而 (冗)抬(Q)=2o(T澈G中的最優(yōu)H回路C的權(quán) 切(C)

48、。于是 Mi份M2 #中。易知邊導(dǎo)出子圖H =T[Mi M2]中的每個(gè)頂點(diǎn)v滿足dH(v) A 2。于是H 中存在回路，從而T中有回路。此與T是樹矛盾，故結(jié)論成立。 2 .證明：樹G有完美匹配當(dāng)且僅當(dāng)對(duì)任意 vWV(G),均有O(G—v) = 1 分析：一方面，由定理9.1.3圖G存在完美匹配當(dāng)且僅當(dāng)對(duì)任意 SUV(G),有O(G—S)E|S|,所 以如果樹G有完美匹配，則O(G-v)4v}|=1 ；而G有完美匹配，說(shuō)明|V(G) =偶數(shù)，所以 O(G -v)之 1 ；從而有 O(G -v) =1。 另一方面，如果對(duì)任意v^V(G),均有O(G -v) =1 ,則對(duì)v而言，可利用這個(gè)這

49、個(gè)奇分 支找到v關(guān)聯(lián)的唯一邊，從而構(gòu)造出 G的一個(gè)完美匹配。 證明：必要性 設(shè)G有完美匹配。 由定理9.1.3,取S ={v},則 O(G -v) =O(G -S) M|S| = 1 又?「G有完美匹配，|V(G)上偶數(shù)。于是M(G—v)|=奇數(shù)。 故 O(G—v)*.從而 O(G—v)=1. 充分性 設(shè)對(duì)任意v ^V(G),有O(G —v) =1. 即G —v恰有一個(gè)奇分支Co(v),因G是樹，故v只能與Co(v)中的一個(gè)頂點(diǎn)鄰接。設(shè)v與Co(v) 的關(guān)聯(lián)邊為e(v)KuWE(G)。顯然v確定以后，uv是唯一確定的，且易知Co(u)=uv。因?yàn)镚-v 只有一個(gè)奇分支Co(v),

50、則G-u以后，v應(yīng)該與G-v的其他偶分支在一個(gè)連通分支中，而這個(gè)分 支的頂點(diǎn)數(shù)顯然是奇數(shù)，從而構(gòu)成G-u的唯一一個(gè)奇分支Co(u),而u與這個(gè)奇分支中的頂點(diǎn)顯 然也只有與v鄰接，所以Co(u)=uv。于是對(duì)任意vW(G),按這樣的方法構(gòu)造其關(guān)聯(lián)邊 e(v), 所的的匹配 M ={e(v) |v WV(G)}就是G的一個(gè)完美匹配 3 .設(shè)k >1是奇數(shù)。舉出沒有完美匹配的k -正則簡(jiǎn)單圖的例子。 分析：作G如下：取2k-1個(gè)頂點(diǎn)v1,2」’,v2ki,在奇足標(biāo)頂點(diǎn)和偶足標(biāo)頂點(diǎn)間兩兩連以邊外， 再連以V1V3,V5v7： ,V2k_5V2k工邊，所得圖記為G0,顯然G0除V2k」外其余頂點(diǎn)的

51、度均為k,而V2k」 的度為k-1,取k個(gè)兩兩不相交的Go的拷貝和一個(gè)新頂點(diǎn)V0,并把每個(gè)Go拷貝中對(duì)應(yīng)于V2k」的 頂點(diǎn)與Vo相連以邊。最后所得的圖記為G,顯然G是k-正則的簡(jiǎn)單圖。又由于Go含2k-1個(gè)頂點(diǎn)， 則G的頂點(diǎn)數(shù)為：k*(2k-1)+1。所以如果G有一個(gè)完美匹配M的話，則 k*(2k-1) 1 , 2 k-1 |M|= -- = k 。 2 2 假設(shè)M是G的一個(gè)完美匹配，則其邊應(yīng)來(lái)自 k個(gè)獨(dú)立的Go,和跟Vo相關(guān)聯(lián)的一條邊。 而每個(gè)Go,其包含的頂點(diǎn)數(shù)為2k-1,所以Go能提供給M的邊最多為k-1條，k個(gè)這樣的Go能提 2 2 k-1 供給M的邊最多為k*(

52、k-1),因此M最多包含的邊為k*(k-1)+1=k 2-(k-1)< k ——,因此G不可 2 能有完美匹配。 解：令k=3,得到的圖Go及G如下： 4 .設(shè)k A o為偶數(shù)，舉出沒有完美匹配的 k-正則簡(jiǎn)單圖的例子. 分析：當(dāng)k為偶數(shù)時(shí)，取G=Kk+1,則G的頂點(diǎn)數(shù)為k+1 ,顯然G的頂點(diǎn)數(shù)為奇數(shù)，所以G無(wú)完 美匹配。 解：令k=2時(shí)，可構(gòu)造出無(wú)完美匹配的 2-正則圖K3 o 5 .兩人在圖G上進(jìn)行對(duì)奕雙方分別執(zhí)黑子和白子，輪流向 G的不同頂點(diǎn)Vo,Vi,V2,… 下子，要 求當(dāng)i >0時(shí)，Vi與v」鄰接，并規(guī)定最后可下子的一方獲勝。若規(guī)定執(zhí)黑子者先下子，試證明執(zhí)

53、 黑子的一方有取勝的策略當(dāng)且僅當(dāng) G無(wú)完美匹配。 分析：假設(shè)G有完美匹配，則G的每個(gè)頂點(diǎn)都是M-飽和點(diǎn)，這樣先下者無(wú)論取哪個(gè)頂點(diǎn)，后下 者都可取其相鄰的M-飽和點(diǎn)，這樣先下的人必輸；因此先下的人如要贏的話，G中肯定無(wú)完美匹 配。 反過(guò)來(lái)，如果G中無(wú)完美匹配，由于任何圖都有最大匹配，則可找到 G的一個(gè)最大匹配 M,由 于M不是完美匹配，因此 G中存在M-非飽和點(diǎn)v,先下的黑方就可找到這個(gè)點(diǎn)下，則與 v相鄰 的下一個(gè)點(diǎn)必是M-飽和點(diǎn)，不然，M U{uv}就是一個(gè)更大的匹配，與M是最大匹配矛盾。同理G 中不存在M可增廣路，故黑方所選vi必是M飽和點(diǎn)，如此下去，最后必是白方無(wú)子可下，故黑 方必勝。

54、 證明：必要性(反證法) 若G中存在一個(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)，如此下去，最后必是白方無(wú)子可下，故黑方必勝。 6 .證明：二分圖G有完美匹配當(dāng)且僅當(dāng)對(duì)任何 S v(G),有 |s.|Ng(s)| 成立 舉例說(shuō)明若G不是二分圖，則上述條件未必充分。 分析：由

55、定理9.1.2Hall定理，對(duì)于具有二劃分(X,Y)的二分圖，G有飽和X中每個(gè)頂點(diǎn)的匹配 當(dāng)且僅當(dāng)對(duì)任意的SX ,<|S|<|Ng(S),顯然如果G有完美匹配M的話，則M既飽和X, 也飽和Y。但當(dāng)G不是二分圖時(shí)，這個(gè)結(jié)論不一定成立，如 K2n+1對(duì)任意的S=V(G)滿足 |S閆Ng(S)|,但它無(wú)完美匹配。 證明：必要性.設(shè)G有完美匹配M ,則M飽和X及Y ,由Hall定理和對(duì)任何S X或 SY ,有 |S|-|Ng(s)| 今任取S=V(G),有$ = & = $2,& =X, S21Y于是有 |S|=|S - S2|=|S| |S|-|Ng(S)| |Ng(S2)| 二|Ng(S

56、i - S2)|=|Ng(S)| 46 充分性：設(shè)對(duì)任何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)都是完美匹配。 當(dāng)G不是二分圖時(shí)，條件不充分，如 G = K3。 7 . 2n個(gè)學(xué)生做化學(xué)實(shí)驗(yàn)，每?jī)蓚€(gè)人一組，如果每對(duì)學(xué)生只在一起互作一次實(shí)驗(yàn)，試作出一個(gè)安 排，使任意兩個(gè)學(xué)生都在一起做過(guò)實(shí)驗(yàn)。 分析：該題可轉(zhuǎn)化為對(duì)具有2n個(gè)頂點(diǎn)(可分別記為0, 1, 2,…，2n-1)的完全圖構(gòu)造其不同的 2n-1

57、個(gè)完美匹配，使得(0, 1) (0, 2)…(0, 2n-1), (1, 2) (1, 3),…，(1, 2n-1)…， (2n-2,2n-1)在這2n-1個(gè)匹配中出現(xiàn)且僅出現(xiàn)一次。 解： 共安排2n-1次實(shí)驗(yàn)，可使任意兩個(gè)學(xué)生都在一起做過(guò)實(shí)驗(yàn)。安排如下： 第 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

58、-1; 8 .試證明：任何一個(gè)(0,1)矩陣中，包含元素1的行或列的最小數(shù)目，等于位于不同行不同列 的1的最大數(shù)目。 分析：由定理922,對(duì)二分圖G,均成立a (G) = P(G)(其中a,(G)為G的最大匹配數(shù)，P(G) 為G的點(diǎn)覆蓋數(shù))。將給定的(0, 1)矩陣表示成一個(gè)二分圖G(V1,V2,E) V1 ={U1,…，un} , V2 ={V1,…，vn}.其中 M(i, j) =1 當(dāng)且僅當(dāng)(u,Vj)w E(G) 該題轉(zhuǎn)化為了判斷G的0(G)和a (G)的關(guān)系。 證明： 設(shè)M m>n是一個(gè)(0,1)矩陣.將M m沏表示成一個(gè)二分圖G(V1,V2 ,E), V1 ={u1,…，

59、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的數(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個(gè)1父2的長(zhǎng)方表將圖9-13中的10個(gè)1父1正方形完全遮蓋?。? 圖 9-13 分析：按如下方法作出G圖：在圖9-13的每個(gè)正方形格子中放一個(gè)頂點(diǎn)，U與

60、V鄰接當(dāng)且僅當(dāng)U 與V所在的方格有公共邊。則該問(wèn)題等價(jià)于判斷相應(yīng)圖 G是否有完美匹配， 解：按照分析，構(gòu)造圖G如下：則有O(G1={u}|,由定理9.1.3可判斷它沒有完美匹 配。因此不能用5個(gè)1父2的長(zhǎng)方表將圖9-13中的10個(gè)1父1正方形完全遮蓋住。 1 10 .試證明：G是二分圖當(dāng)且僅當(dāng)對(duì) G的每個(gè)子圖H均有 a(H ) >- |V(H) |o 2 分析：若6= (X,Y)是二分圖，顯然X和Y都構(gòu)成G的點(diǎn)獨(dú)立集，所以G的最大獨(dú)立數(shù)ct(G)>|X| , 且u(G)平|;而二分圖的每個(gè)子圖顯然也是二分圖。 證明：必要性.設(shè)G是二分圖，于是 G的任何子圖 H也是二

61、分圖，設(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 是二分圖。 48 11 .試證明：G是二分圖當(dāng)且僅當(dāng)對(duì) G的每個(gè)適合6(H ) >0的子圖H ,均有a(H) = P(H). 分析：ot(G)是指G的最大獨(dú)立集，P

62、,因此如果能證明 P,(H )=max(|X|,|Y|),則對(duì)不含孤立點(diǎn)的二分圖 G,有a(G)=P，(G) 證明：必要性.設(shè)G是二分圖。 HWG, 6(H) >0 ,即H無(wú)孤立點(diǎn)。顯然H也是二分圖， 設(shè)H =(X,Y),且| X以丫 |。于是， u(H ) =|X |。而一條邊最多覆蓋一個(gè)頂點(diǎn)，故 pH) >|X |o 但由于 H 無(wú)孤立點(diǎn)，因此，P(H) <|X| ,故 P(H )=|X | = u(H)。 充分性.若G不是二分圖，則G含奇回路C = H。設(shè)|V(H)|=2n+1, n之1。于是 a(H) =n ,而 P(H) =n +1 >s(H)。矛盾。故 G 必為二分圖。 1

63、2 .設(shè)G是具有劃分(X, Y)的二分圖。證明：若對(duì)于任何 uw X,vWY.均有d(u)之d(v), 則G有飽和X中每一頂點(diǎn)的匹配。 分析：根據(jù)定理9.1.2,二分圖G有飽和X中每個(gè)點(diǎn)的匹配當(dāng)且僅當(dāng)對(duì)任何 S= X，有|S四Ng(S)| 根據(jù)這個(gè)結(jié)論，如果能說(shuō)明滿足條件的二分圖 G中不存在任何SG X ,有|S|>|Ng(S)| ,則題目 得證。 證明：由題意知，對(duì)VuWX, d(u)之1。 若G中不存在飽和X的匹配，則由Hall定理，存在S= X ,使|S|>| Ng(S)|。 設(shè) S={u1 J ,um}, Ng (S) ={Vj …，％ },其中 m > n o 1 , n

64、 由對(duì)任何uWX,vWY, d(u)之d(v),得 d(u)至d d(v),但由于S中的點(diǎn)關(guān)聯(lián)的邊 u S v三Ng (S) 都是Ng (S)的點(diǎn)關(guān)聯(lián)的邊，因此d d(u)< d d(v),因此有 d(u)= d d(v),但m〉n, u S v=Ng (S) u S v三Ng(S) 因此在Ng (S)中總存在一點(diǎn)，有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è)圖G是二分圖

65、，則u(G) = P(G) , a(a)是G的最大匹配數(shù)， P(G)是G的最小覆蓋。因此如果能說(shuō)明 mjn{|X-S|[Ng(S)|}等于目(G)的話，則本題得以 證明。 s x 證明：由于{X —S}「Ng(S)H,所以 |X—S|+|Ng(S)| = {X—S}j{Ng(S)}| 顯然{ X —S}3{Ng (S)}是G的一個(gè)覆蓋，而G的任意一個(gè)覆蓋都可以寫成{ X —S}={ N g (S)}的 形式，所以 FG) = min{|X-S| |Ng(S)|} 因此有：(G) = -(G)=xmin{|X-S| |Ng(S)|} S x 49 14 .證明：在無(wú)孤立點(diǎn)的二

66、分圖 G中，最大獨(dú)立集的頂點(diǎn)集“(G)等于最小邊覆蓋數(shù)P (H)。 證明：參見題11 15 .在9個(gè)人的人群中，假設(shè)有一個(gè)人認(rèn)識(shí)另外兩個(gè)人，有兩個(gè)人每人認(rèn)識(shí)另外 4個(gè)人，有4個(gè) 人認(rèn)識(shí)另外5個(gè)人，余下的兩個(gè)人每人認(rèn)識(shí)另外的 6個(gè)人。證明：有3個(gè)人，他們?nèi)炕ハ? 認(rèn)識(shí)。 分析：將該題中的人用圖中的節(jié)點(diǎn)表示，兩個(gè)節(jié)點(diǎn)有連線當(dāng)且僅當(dāng)兩個(gè)人認(rèn)識(shí)，則該題轉(zhuǎn)化為求 證滿足上述條件的圖G含有一個(gè)K3。 要判斷一個(gè)圖是否含有 K3,我們先要了解以下概念和定理： T2, p：具有p個(gè)頂點(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定理(托蘭定理)的推論：若簡(jiǎn)單圖 G不含K3,則E(G)< E(T2,p),且當(dāng)E(G)=E(T2,p)時(shí)， 有G三T2, p 該定理的嚴(yán)格內(nèi)容為：若簡(jiǎn)單圖G不含Km+1,則E(G)WE(Tm，p)