第10章習(xí)題答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上習(xí)題10 1.(1)圖G的度數(shù)列為2、2、3、3、4，則G的邊數(shù)是多少？(2)3、3、2、3和5、2、3、1、4能成為圖的度數(shù)列嗎？為什么？(3)圖G有12條邊，度數(shù)為3的結(jié)點(diǎn)有6個(gè)，其余結(jié)點(diǎn)的度數(shù)均小于3，問圖G中至多有幾個(gè)結(jié)點(diǎn)？為什么？解 (1)設(shè)G有m條邊，由握手定理得2m2233414，所以G的邊數(shù)7條。(2)由于這兩個(gè)序列中有奇數(shù)個(gè)是奇數(shù)，由握手定理的推論知，它們都不能成為圖的度數(shù)列。(3) 由握手定理得2m24，度數(shù)為3的結(jié)點(diǎn)有6個(gè)占去18度，還有6度由其它結(jié)點(diǎn)占有，其余結(jié)點(diǎn)的度數(shù)可為0、1、2，當(dāng)均為2時(shí)所用結(jié)點(diǎn)數(shù)最少，所以應(yīng)由3個(gè)結(jié)點(diǎn)占有這6度，即圖G

2、中至多有9個(gè)結(jié)點(diǎn)。2.若有n個(gè)人，每個(gè)人恰有3個(gè)朋友，則n必為偶數(shù)。證明 設(shè)、表示任給的n個(gè)人，以、為結(jié)點(diǎn)，當(dāng)且僅當(dāng)兩人為朋友時(shí)其對應(yīng)的結(jié)點(diǎn)之間連一條邊，這樣得到一個(gè)簡單圖G。由握手定理知3n必為偶數(shù)，從而n必為偶數(shù)。3.判斷下列各非負(fù)整數(shù)列哪些是可圖化的？哪些是可簡單圖化的？(1)(1，1，1，2，3)。(2)(2，2，2，2，2)。(3)(3，3，3，3)。(4)(1，2，3，4，5)。(5)(1，3，3，3)。解 由于非負(fù)整數(shù)列d(d1，d2，dn)是可圖化的當(dāng)且僅當(dāng)0(mod 2)，所以(1)、(2)、(3)、(5)能構(gòu)成無向圖的度數(shù)列。(1)、(2)、(3)是可簡單圖化的。其對應(yīng)的無

3、向簡單圖如圖所示。(5)是不可簡單圖化的。若不然，存在無向圖G以為1，3，3，3度數(shù)列，不妨設(shè)G中結(jié)點(diǎn)為、，且d()1，d()d()d()3。而只能與、之一相鄰，設(shè)與相鄰，于是d()d()3不成立，矛盾。4.試證明圖10-48中的兩個(gè)無向圖是不同構(gòu)的。證明 因?yàn)閮蓤D中都有4個(gè)3度結(jié)點(diǎn)，左圖中每個(gè)3度結(jié)點(diǎn)均與2個(gè)2度結(jié)點(diǎn)鄰接，而右圖中每個(gè)3度結(jié)點(diǎn)均只與1個(gè)2度結(jié)點(diǎn)鄰接，所以這兩個(gè)無向圖是不同構(gòu)的。5.在圖同構(gòu)意義下，試畫出具有三個(gè)結(jié)點(diǎn)的所有簡單有向圖。解 具有三個(gè)結(jié)點(diǎn)的所有非同構(gòu)的簡單有向圖共16個(gè)，如圖所示，其中(8)(16)為其生成子圖。6.給定無向完全圖G<V，E>，且|V|4

4、。在圖同構(gòu)意義下，試求：(1)G的所有子圖。(2)G的所有生成子圖。解 (1)G的所有子圖如圖所示。(2)圖(8)(18)是G的所有生成子圖。7.(1)試給出一個(gè)五個(gè)結(jié)點(diǎn)的自補(bǔ)圖。(2)是否有三個(gè)結(jié)點(diǎn)或六個(gè)結(jié)點(diǎn)的自補(bǔ)圖。(3)一個(gè)圖是自補(bǔ)圖，則其對應(yīng)的完全圖的邊數(shù)必是偶數(shù)。(4)一個(gè)自補(bǔ)圖的結(jié)點(diǎn)數(shù)必是4k或4k1。解 (1)五個(gè)結(jié)點(diǎn)的圖G與它的補(bǔ)圖如圖所示。對G與建立雙射：®，®，®，®，®。顯然這兩個(gè)圖保持相應(yīng)點(diǎn)邊之間的對應(yīng)的關(guān)聯(lián)關(guān)系，故G。因此，G是五個(gè)結(jié)點(diǎn)的自補(bǔ)圖。(3)設(shè)圖G是自補(bǔ)圖，有m條邊，G對應(yīng)的完全圖的邊數(shù)為s，則G對應(yīng)的補(bǔ)圖的

5、邊數(shù)為sm。因?yàn)镚，故邊數(shù)相等，即有msm，s2m，因此G對應(yīng)的完全圖的邊數(shù)s為偶數(shù)。(2)由(3)知，自補(bǔ)圖對應(yīng)的完全圖的邊數(shù)為偶數(shù)。n個(gè)結(jié)點(diǎn)的完全圖的邊數(shù)為n(n1)，當(dāng)n3或n6時(shí)，的邊數(shù)為奇數(shù)，因此不存在三個(gè)結(jié)點(diǎn)或六個(gè)結(jié)點(diǎn)的自補(bǔ)圖。(4)設(shè)G為n階自補(bǔ)圖，則需n(n1)能被2整除，因此n必為4k或4k1形式。8.一個(gè)n(n2)階無向簡單圖G中，n為奇數(shù)，已知G中有r個(gè)奇數(shù)度結(jié)點(diǎn)，問G的補(bǔ)圖中有幾個(gè)奇數(shù)度結(jié)點(diǎn)？解 由G的補(bǔ)圖的定義可知，G為，由于n為奇數(shù)，所以中各頂點(diǎn)的度數(shù)n1為偶數(shù)。對于圖G的任意結(jié)點(diǎn)，應(yīng)有也是的頂點(diǎn)，且n1，由于n1為偶數(shù)，所以和奇偶性相同，因此若G中有r個(gè)奇數(shù)度結(jié)點(diǎn)

6、，則中也有r個(gè)奇數(shù)度結(jié)點(diǎn)。9.畫出4階無向完全圖K4的所有非同構(gòu)的生成子圖，并指出自補(bǔ)圖來。解 下圖中的11個(gè)圖是K4的全部的非同構(gòu)的生成子圖，其中(7)為自補(bǔ)圖。10.設(shè)圖G中有9個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的度不是5就是6。試證明G中至少有5個(gè)6度結(jié)點(diǎn)或至少有6個(gè)5度結(jié)點(diǎn)。證明 由握手定理的推論可知，G中5度結(jié)點(diǎn)數(shù)只能是0、2、4、6、8五種情況（此時(shí)6度結(jié)點(diǎn)數(shù)分別為9、7、5、3、1）。以上五種情況都滿足至少5個(gè)6度結(jié)點(diǎn)或至少6個(gè)5度結(jié)點(diǎn)的情況。11.證明3度正則圖必有偶數(shù)個(gè)結(jié)點(diǎn)。證明 設(shè)G為任一3度正則圖，有n個(gè)結(jié)點(diǎn)、，則所有結(jié)點(diǎn)度數(shù)之和3n。若n為奇數(shù)，則3n也為奇數(shù)，與握手定理矛盾。故n為偶數(shù)

7、。12.設(shè)G為至少有兩個(gè)結(jié)點(diǎn)的簡單圖，證明：G中至少有兩個(gè)結(jié)點(diǎn)度數(shù)相同。證明 若G中孤立結(jié)點(diǎn)的個(gè)數(shù)大于2，結(jié)論顯然成立。若G中有1個(gè)孤立結(jié)點(diǎn)，則G中至少有3個(gè)結(jié)點(diǎn)，因而不考慮孤立結(jié)點(diǎn)，就是說G中每個(gè)結(jié)點(diǎn)的度數(shù)都大于等于1。又因?yàn)镚為簡單圖，所以每個(gè)結(jié)點(diǎn)的度數(shù)都小于等于n-1。因而G中結(jié)點(diǎn)的度的取值只能是1，2，n-1這n個(gè)數(shù)。由抽屜原理可知，取n-1個(gè)值的n個(gè)結(jié)點(diǎn)的度至少有兩個(gè)是相同的。13.給定無向圖G<V，E>如圖10-49所示，試求：(1)從a到d的所有基本路。(2)從a到d的所有簡單路。(3)長度分別是最小和最大的基本回路。(4)長度分別是最小和最大的簡單回路。(5)從a到

8、d的距離。(6)g(G)、l(G)、d(G)、D(G)分別是多少？解 (1)從a到d的所有基本路共有10條：abd，abcd，abed，abced，abecd，afed，afecd，afebd，afebcd，afecbd。(2)從a到d的所有簡單路共有14條：除（1）中的10條外還有abcebd，abecbd，afebced，afecbed。(3)長度最小的基本回路共4個(gè)：bceb，bdeb，cdec，bcdb。長度最大的基本回路共1個(gè)：abdcefa。(4)長度最小的簡單回路共4個(gè)：bceb，bdeb，cdec，bcdb。長度最大的簡單回路2個(gè)：abcebdefa，afebcedba。(5)

9、從a到d的距離為2。(6)g(G)2，l(G)2，d(G)2，D(G)4。14.給定有向圖G<V，E>如圖10-50所示，試求：(1)各結(jié)點(diǎn)的出度、入度和度。(2)從a到d的所有基本路和簡單路。(3)所有基本回路和簡單回路。解 (1)d+(a)2，d-(a)1，d+(b)1，d-(b)2，d+(c)1，d-(c)1，d+(d)2，d-(d)2，d+(e)1，d-(e)1。(2)從a到d的基本路2條：ad，abd。從a到d的簡單路5條：ad，abd，adcbd，adead，adeabd。(3)基本回路共3個(gè)abdea，adea，bdcb.簡單回路共4個(gè)：abdea，adea，bdcb

10、，adcbdea。15.(1)若無向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，則這兩個(gè)結(jié)點(diǎn)一定是連通的。(2)若有向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，它們一個(gè)可達(dá)另一個(gè)結(jié)點(diǎn)或互相可達(dá)嗎？證明 (1)設(shè)無向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)和。從開始構(gòu)造一條回路，即從出發(fā)經(jīng)關(guān)聯(lián)結(jié)點(diǎn)的邊到達(dá)結(jié)點(diǎn)，若為偶數(shù)，則必可由再經(jīng)關(guān)聯(lián)的邊到達(dá)結(jié)點(diǎn)，如此繼續(xù)下去，每條邊只取一次，直到另一個(gè)奇數(shù)度結(jié)點(diǎn)為止，由于圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，故該結(jié)點(diǎn)或是或是。如果是，那么從到的一條路就構(gòu)造好了。如果仍是，該回路上每個(gè)結(jié)點(diǎn)都關(guān)聯(lián)偶數(shù)條邊，而是奇數(shù)，所以至少還有一條邊關(guān)聯(lián)結(jié)點(diǎn)的邊不在該回路上。繼續(xù)從出發(fā)，沿著該邊到達(dá)另一個(gè)結(jié)點(diǎn)，依次下去直到另一個(gè)奇數(shù)度結(jié)點(diǎn)

11、停下。這樣經(jīng)過有限次后必可到達(dá)結(jié)點(diǎn)，這就是一條從到的路。(2)若有向圖G中只有兩個(gè)奇數(shù)度結(jié)點(diǎn)，它們一個(gè)可達(dá)另一個(gè)結(jié)點(diǎn)或互相可達(dá)不一定成立。下面有向圖中，只有兩個(gè)奇數(shù)度結(jié)點(diǎn)和，和之間都不可達(dá)。16.若無向圖G是不連通的，證明G的補(bǔ)圖是連通的。證明 設(shè)無向圖G是不連通的，其k個(gè)連通分支為、。任取結(jié)點(diǎn)、G，若和不在圖G的同一個(gè)連通分支中，則，不是圖G的邊，因而，是圖的邊；若和在圖G的同一個(gè)連通分支中，不妨設(shè)其在連通分支（1）中，在不同于的另一連通分支上取一結(jié)點(diǎn)，則，和，都不是圖G的邊，因而，和，都是的邊。綜上可知，不管那種情況，和都是可達(dá)的。由和的任意性可知，是連通的。17.完成定理10.11的證明

12、。證明 充分性：若連通圖G中存在結(jié)點(diǎn)u和w，使得連接u和w的每條路都經(jīng)過，則在子圖G中u和w必不可達(dá)，故是G的割邊。必要性：若是G的割邊，則G至少有兩個(gè)連通分支G1<V1，E1>和G2<V2，E2>。任取uV1，wV2，因?yàn)镚連通，故在G中必有連接u和w的路G，但u、w在G中不可達(dá)，因此G必通過，即u和w之間的任意路必經(jīng)過。18.完成定理10.16的證明。證明 先證任一結(jié)點(diǎn)至少位于一個(gè)單向分圖中。任給一結(jié)點(diǎn)，若是孤立結(jié)點(diǎn)，則含的平凡圖即為單向分圖。若不是孤立結(jié)點(diǎn)，則必有一個(gè)結(jié)點(diǎn)，使得與有一弧與它們聯(lián)結(jié)。此時(shí)若有單向分圖，|3，使，且，那么結(jié)論成立；若不存在這樣的，則由，

13、和就構(gòu)成一個(gè)單向分圖。因此，任何結(jié)點(diǎn)至少位于一個(gè)單向分圖中。其次證明，任何一條弧至少位于一個(gè)單向分圖中。任給一弧，其關(guān)聯(lián)的結(jié)點(diǎn)和。若存在一單向分圖，|3，使，且，那么結(jié)論成立。否則，和就構(gòu)成一個(gè)單向分圖。綜上可知，任一弧至少位于一個(gè)單向分圖中。19.完成定理10.17的證明。證明 顯然任一結(jié)點(diǎn)和任一弧都位于一個(gè)弱分圖中。假設(shè)有一結(jié)點(diǎn)位于兩個(gè)不同的弱分圖和中，即。由于略去弧的方向后，中所有結(jié)點(diǎn)與可達(dá)，中所有結(jié)點(diǎn)也與可達(dá)，故與中所有結(jié)點(diǎn)可達(dá)，這與和為弱分圖矛盾，故任一結(jié)點(diǎn)不可能包含于不同的弱分圖中，即任一結(jié)點(diǎn)能且只能位于一個(gè)弱分圖中。假設(shè)一弧位于兩個(gè)不同的弱分圖中，該弧所關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)也位于兩個(gè)不

14、同的弱分圖中，這是不可能的，因此任一弧也只能位于一個(gè)弱分圖中。20.給出3個(gè)4階有向簡單圖D1、D2、D3，使得D1為強(qiáng)連通圖；D2為單向連通圖但不是強(qiáng)連通圖；D3是弱連通圖但不是單向連通圖，當(dāng)然更不是強(qiáng)連通圖。解 圖中得（a）為強(qiáng)連通圖；（b）為單向連通圖但不是強(qiáng)連通圖；（c）是弱連通圖但不是單向連通圖，當(dāng)然更不是強(qiáng)連通圖。21.一個(gè)有向圖D是單向連通圖，當(dāng)且僅當(dāng)它有一條經(jīng)過每一個(gè)結(jié)點(diǎn)的路。證明 充分性。給定有向圖D<V，E>，如果D有一條經(jīng)過每一個(gè)結(jié)點(diǎn)的路為，這時(shí)V，E，ÍE，邊（11）以為起點(diǎn)，以為終點(diǎn)。任給兩個(gè)結(jié)點(diǎn)、V，不妨設(shè)，則就是從結(jié)點(diǎn)到的路，故D是單向連通的

15、。必要性。對結(jié)點(diǎn)數(shù)進(jìn)行歸納。當(dāng)1或2時(shí)，單向連通圖顯然有一條經(jīng)過每一個(gè)結(jié)點(diǎn)的路。設(shè)時(shí)，有一條經(jīng)過每一個(gè)結(jié)點(diǎn)的路，其中結(jié)點(diǎn)可能有重復(fù)，這條路的下標(biāo)只表示該路所經(jīng)過結(jié)點(diǎn)的次序，顯然。當(dāng)1時(shí)，取一結(jié)點(diǎn)，在圖中刪去結(jié)點(diǎn)，使D還是單向連通圖。根據(jù)歸納假設(shè)，D有一條經(jīng)過每一個(gè)結(jié)點(diǎn)的路。令max|到有路，min|到有路。假如1，則必有滿足。由于圖D是單向連通的，與之間必有路。如果該路是從到，則與max|到有路矛盾。如果該路是從到，則與min|到有路矛盾。故而1不可能，只能是1。當(dāng)1時(shí)，有經(jīng)過每個(gè)結(jié)點(diǎn)的路。當(dāng)時(shí)，有經(jīng)過每個(gè)結(jié)點(diǎn)的路。22.設(shè)e為圖G<V，E>中的一條邊，w(G)為G的連通分支數(shù)，證

16、明w(G)w(Ge)w(G)1。證明 設(shè)e為圖G的第個(gè)連通分支的一條邊。若e不是的割邊，則e仍然連通，因而G的連通分支數(shù)不變，即w(G)w(Ge) （1）若e是的割邊，則e有且僅有兩個(gè)連通分支，因而Ge比G多一個(gè)支連通分支，即w(G)1w(Ge) （2）由（1）和（2）可得w(G)w(Ge)w(G)1。23.設(shè)G是n階無向簡單圖，有m條邊，p個(gè)連通分支，證明npm(np)(np1)/2。證明 （1）首先證明npm。對邊數(shù)m做歸納法。m0時(shí)，G為零圖，pn，np0，此時(shí)結(jié)論顯然成立。設(shè)mk（k1）時(shí)結(jié)論成立，要證m3時(shí)結(jié)論成立。在G中找一個(gè)邊割集，不妨設(shè)這個(gè)邊割集中的邊為，（1），設(shè)G1G，則G

17、1的連通分支數(shù)為p1，邊數(shù)為m1m（1），由歸納假設(shè)得n（p1）mm1，于是npm。（2）再證m(np)(np1)/2。為證明此不等式，不妨設(shè)G的各連通分支都是完全圖，因?yàn)樵谶@種情況下邊數(shù)最多。而在1個(gè)連通分支都是完全圖的情況下，又以p1個(gè)為（平面圖），一個(gè)np1階完全圖時(shí)邊數(shù)最多，此時(shí)的邊數(shù)為(np)(np1)/2。為此只需證明下面事實(shí)：設(shè)和是G的兩個(gè)連通分支（1）。用和分別代替和，所得圖的結(jié)點(diǎn)數(shù)和連通分支數(shù)沒變，但邊數(shù)增加了。證明如下：(1)(1)(2)(1)(1)10綜上所述就證明了結(jié)論。24.設(shè)G<V，E>為非平凡有向圖，若對V的任一非空子集S，G中起始結(jié)點(diǎn)在S中，終止結(jié)點(diǎn)

18、在VS中的有向邊都至少有k條，則稱G是k條邊連通的。證明：非平凡有向圖G是強(qiáng)連通Û它是1邊連通的。證明 必要性。設(shè)G是強(qiáng)連通的，此時(shí)若從S到VS沒有有向邊，則S中的任一結(jié)點(diǎn)u到VS中的任一結(jié)點(diǎn)v均沒有有向路，從而與G是強(qiáng)連通的矛盾。所以從S到VS至少有一條有向邊。故G是1邊連通的。充分性。設(shè)G是1邊連通的。任意u、vV，u到Vu至少有一條邊，設(shè)為uu1，而u，u1到Vu，u1至少有一條邊uu2或u1u2。無論那種情況都有從u到u2的有向路。因G中結(jié)點(diǎn)有限，所以通過如上遞歸地求解，一定有u到v的有向路。故G是強(qiáng)連通的。25.證明在n個(gè)結(jié)點(diǎn)的連通圖G中，至少有n1條邊。證明 不妨設(shè)G是無

19、向連通圖（若G為有向圖，可略去邊的方向討論對應(yīng)的無向圖）。設(shè)G中結(jié)點(diǎn)為、。由連通性，必存在與相鄰的結(jié)點(diǎn)，不妨設(shè)它為（否則可重新編號），連接和，得邊，還是由連通性，在、中必存在與或相鄰的結(jié)點(diǎn)，不妨設(shè)為，將其連接得邊，續(xù)行此法，必與、中的某個(gè)結(jié)點(diǎn)相鄰，得新邊，由此可見G中至少有n1條邊。26.試給出|V|n，|E|(n1)(n2)的簡單無向圖G<V，E>是不連通的例子。解 下圖滿足條件但不連通。27.一個(gè)n階連通圖G最少有幾個(gè)割點(diǎn)？最多有幾個(gè)割點(diǎn)？解 一個(gè)n階連通圖G為樹時(shí)割點(diǎn)最少，只有一個(gè)；為完全圖時(shí)割點(diǎn)最多，有n1個(gè)。28.求完全圖Kn中任兩點(diǎn)之間長為k的路的數(shù)目。解 設(shè)E為元素全

20、為1的n階矩陣，I為階單位矩陣，于是Kn的鄰接矩陣為AEI。Kn中長度為k的路的數(shù)目由決定。由于(EI)k所以，。29.有向圖D如圖10-51所示：(1)求D的鄰接矩陣A。(2)D中v1到v4長度為4的路有多少？(3)D中v1到自身長度為3的回路有多少？(4)D中長度為4的路數(shù)為多少？其中有幾條回路？(5)D中長度小于等于4的路有多少？其中有多少條回路？(6)D是哪類連通圖？解 (1) 求D的鄰接矩陣為：且有 (2)由中可知，D中v1到v4長度為4的路有4條，分別為：、。(3)由中可知，D中v1到自身長度為3的回路只有1條，為。(4)D中長度為4的路總數(shù)為，其中對角元素之和為3，說明長度為4的

21、回路為3條。(5)D中長度小于等于4的路總數(shù)為、中全體元素之和：710131646，其中回路數(shù)為：13138。(6)由可知，D是單向連通圖。30.有向圖G如圖10-52所示，試求：(1)求G的鄰接矩陣A。(2)求出A2、A3和A4，v1到v4長度為1、2、3和4的路有多少？(3)求出ATA和AAT，說明ATA和AAT中的第(2，2)元素和第(2，3)元素的意義。(4)求出可達(dá)矩陣P。(5)求出強(qiáng)分圖。解 (1)求G的鄰接矩陣為：(2)由于 所以v1到v4長度為1、2、3和4的路的個(gè)數(shù)分別為1、1、2、3。(3)由于 再由定理10.19可知，所以ATA的第(2，2)元素為3，表明那些邊以為終結(jié)點(diǎn)

22、且具有不同始結(jié)點(diǎn)的數(shù)目為3，其第(2，3)元素為0，表明那些邊既以為終結(jié)點(diǎn)又以為終結(jié)點(diǎn)，并且具有相同始結(jié)點(diǎn)的數(shù)目為0。AAT中的第(2，2)元素為2，表明那些邊以為始結(jié)點(diǎn)且具有不同終結(jié)點(diǎn)的數(shù)目為2，其第(2，3)元素為1，表明那些邊既以為始結(jié)點(diǎn)又以為始結(jié)點(diǎn)，并且具有相同終結(jié)點(diǎn)的數(shù)目為1。(4)因?yàn)?，所以求可達(dá)矩陣為。(5)因?yàn)?，所以，?gòu)成G的強(qiáng)分圖。31.畫一個(gè)無向歐拉圖，使它具有：(1)偶數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊。(2)奇數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊。(3)偶數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊。(4)奇數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊。解 (1)n（n為偶數(shù)，且n2）階圈都是偶數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊的無向歐拉圖。(2)n（n為奇數(shù)，且n1

23、）階圈都是奇數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊的無向歐拉圖。(3)在(1)中的圈上任選一個(gè)頂點(diǎn)，在此頂點(diǎn)處加一個(gè)環(huán)，所得圖為偶數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊無向歐拉圖。(4)在(3)中的圈上任選一個(gè)頂點(diǎn)，在此頂點(diǎn)處加一個(gè)環(huán)，所得圖為奇數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊無向歐拉圖。32.畫一個(gè)無向圖，使它是：(1)既是歐拉圖，又是哈密爾頓圖。(2)是歐拉圖，但不是哈密爾頓圖。(3)是哈密爾頓圖，但不是歐拉圖。(4)既不是歐拉圖，也不是哈密爾頓圖。解 (1)n（n3）階圈，它們都是歐拉圖，又是哈密爾頓圖。(2)給定k（k2）個(gè)長度大于等于3的初級回路，即圈，。將中某個(gè)頂點(diǎn)和中的某個(gè)頂點(diǎn)重合，但邊不重合，中某個(gè)頂點(diǎn)和中的某個(gè)頂點(diǎn)重合，但邊不重

24、合，續(xù)行此法，直到將中某個(gè)頂點(diǎn)和中的某個(gè)頂點(diǎn)重合，但邊不重合，設(shè)最后得到的連通圖為，則是歐拉圖，但不是哈密爾頓圖。(3)在n（n4）階圈中，找兩個(gè)不相鄰的頂點(diǎn)，在它們之間加一條邊，所得圖是哈密爾頓圖，但不是歐拉圖。(4)在(2)中的圖中，設(shè)存在長度大于等于4的圈，比如，在中找，兩個(gè)不相鄰的頂點(diǎn)，在它們之間加一條邊，然后按照（2）的方法構(gòu)造圖，則既不是歐拉圖，也不是哈密爾頓圖。33.(1)n為何值時(shí)，無向完全圖Kn是歐拉圖？n為何值時(shí)，Kn僅存在歐拉路而不存在歐拉回路？(2)什么樣的完全二部圖是歐拉圖？(3)n為何值時(shí)，輪圖Wn為歐拉圖？解 (1)一般情況下，我們不考慮。n（n2）為奇數(shù)時(shí)，無向

25、完全圖Kn是歐拉圖。Kn各結(jié)點(diǎn)的度均為n1，若使Kn為偶拉圖，n1必為偶數(shù)，因而必n為奇數(shù)。K2僅存在歐拉路而不存在歐拉回路。(2)設(shè)為完全二部圖，當(dāng)、均為偶數(shù)時(shí)，為歐拉圖。(3)設(shè)Wn（n4）為輪圖，在Wn中，有n1個(gè)結(jié)點(diǎn)的度數(shù)為3，因而對于任何取值的n（n4），輪圖Wn都不是歐拉圖。34.證明：完全圖K9中至少存在彼此無公共邊的兩條哈密爾頓回路和一條哈密爾頓通路。證明 設(shè)為K9中一條哈密爾頓回路。令為K9刪除中全部邊之后的圖，則中每個(gè)結(jié)點(diǎn)的度均為6。由定理10.26可知仍是哈密爾頓圖，因而存在中的哈密爾頓回路（顯然也是K9中的哈密爾頓回路，并且與無公共邊）。再設(shè)為中刪除中的全部邊后所得圖，

26、為4正則圖。由定理10.26可知具有哈密爾頓通路。設(shè)為中的一條存在哈密爾頓通路，顯然、無公共邊。事實(shí)上，可以證明在K9中存在4條邊不重的哈密爾頓回路?？梢宰C明：在K3中存在一條邊不重合的哈密爾頓回路，K5中存在兩條邊不重合的哈密爾頓回路，K7中存在3條邊不重合的哈密爾頓回路，一般情況下，K2k+1(k1)中最多可存在條邊不重合的哈密爾頓回路。35.已知a、b、c、d、e、f、g 7個(gè)人中，a會講英語；b會講英語和漢語；c會講英語、意大利語和俄語；d會講漢語和日語；e會講意大利語和德語；f會講俄語、日語和法語；g會講德語和法語。能否將他們的座位安排在圓桌旁，使得每個(gè)人都能與他身邊的人交談？解 用

27、a、b、c、d、e、f、g 7個(gè)結(jié)點(diǎn)代表7個(gè)人，若兩人能交談（會講同一種語言），就在代表它們的結(jié)點(diǎn)之間連無向邊，所得無向圖如下圖（1），此圖中存在哈密爾頓回路：，如圖（2）粗邊所示，于是按圖（3）所示的順序安排座位即可。36.證明：對于每個(gè)競賽圖D，至多改變一條邊的方向后就可以變成哈密爾頓圖。證明 由定理10.26可知D中存在哈密爾頓通路，設(shè)D為n（n3）階競賽圖，為中的一條哈密爾頓通路，若邊<，>在D中，則為D中一條哈密爾頓回路，故D為哈密爾頓圖。否則邊<，>在D中，將改變方向得到邊<，>，于是D就變成了哈密爾頓圖。37.給定簡單無向圖G<V，E&g

28、t;，且|V|m，|E|n。試證：若n2，則G是哈密爾頓圖。證明 若n2，則2nm23m6 （1）。若存在兩個(gè)不相鄰結(jié)點(diǎn)、使得d()d()m，則有2nm(m2)(m3)mm23m6，與（1）矛盾。所以，對于G中任意兩個(gè)不相鄰結(jié)點(diǎn)、都有d()d()m。由定理10.26可知，G是哈密爾頓圖。38.設(shè)G是無向連通圖，證明：若G中有割點(diǎn)或割邊，則G不是哈密爾頓圖。證明 若G中有割點(diǎn)，則G中至少有兩個(gè)連通分支，從而w(G)|，由定理10.25可知，G不是哈密爾頓圖。若G中有割邊，當(dāng)G只有兩個(gè)結(jié)點(diǎn)時(shí)，顯然G不是哈密爾頓圖。當(dāng)G的結(jié)點(diǎn)數(shù)多余2時(shí)，從G中刪除割邊e之后至少有兩個(gè)連通分支，其中一個(gè)連通分支含有割

29、邊e的一個(gè)端點(diǎn)且其結(jié)點(diǎn)個(gè)數(shù)大于1，于是w(G)|，由定理10.25可知，G不是哈密爾頓圖。39.某次會議有20人參加，其中每個(gè)人都至少有10個(gè)朋友，這20人圍一圓桌入席，要想使與每個(gè)人相鄰的兩位都是朋友是否可能？根據(jù)什么？解 可能。依題意，若用結(jié)點(diǎn)代表人，兩人是朋友時(shí)相應(yīng)結(jié)點(diǎn)之間連一條邊，則得到一個(gè)無向圖G<V，E>，該題轉(zhuǎn)化為求哈密爾頓回路問題。由于對任意、V，有d()d(v)101020，根據(jù)定理10.26，G為哈密爾頓圖，G中存在哈密爾頓回路，按此回路各點(diǎn)位置入席即為所求。40.設(shè)G是具有k(k0)個(gè)奇數(shù)度結(jié)點(diǎn)的無向連通圖，證明G中邊不重合的簡單通路的最小數(shù)目是，它們包含G的

30、全部邊。證明 由握手定理的推論可知，k是偶數(shù)。對k做歸納法。(1)當(dāng)k2時(shí)，由定理10.22可知，G中存在偶拉路，結(jié)論得證。(2)設(shè)k2r（r2）時(shí)結(jié)論成立，要證k為2r2時(shí)結(jié)論成立。設(shè)，為G中任意二奇度結(jié)點(diǎn)，由G的連通性可知，從到存在路徑，刪除上的全部邊，得連通分支，。這些連通分支共含2r個(gè)奇度結(jié)點(diǎn)，設(shè)中含個(gè)奇度結(jié)點(diǎn)，則22r（1rs），且2r。由歸納假設(shè)可知，中存在條邊不重合的簡單通路，它們含中的所有邊。于是G中共含11r條邊不重合的簡單通路，它們含G中的全部邊。41.甲、乙、丙、丁四位教師，分配他們教數(shù)學(xué)、物理，電工和計(jì)算機(jī)原理四門課。甲能教物理和電工，乙能教數(shù)學(xué)和計(jì)算機(jī)原理，丙能教數(shù)學(xué)

31、、物理和電工，丁只能教電工，對他們的工作怎樣分配？解 設(shè).甲、乙、丙、丁四位教師分別用、表示，數(shù)學(xué)、物理，電工和計(jì)算機(jī)原理四門課分別用、表示，。若能教，令<，>。所作圖G<V1，V2，E>，則G為二部圖，如下圖所示。易證滿足“相異性條件”，且|，所以，存在到的完全匹配。圖中粗線所示就是其一種分配方案。42.某雜志發(fā)表了7個(gè)征求答案的題目，當(dāng)從讀者寄來的解答中挑選每題的兩個(gè)解答時(shí)，編者發(fā)現(xiàn)所有14個(gè)選出來的解答恰好是7個(gè)讀者提出來的，而且每個(gè)人正好提出了兩個(gè)答案。試證明：編輯可以這樣發(fā)表每道題的一個(gè)解答，使得在發(fā)表的解答中，這7個(gè)讀者每個(gè)人都恰有一個(gè)解答。解 7個(gè)位讀者分

32、別用、表示，7個(gè)題目分別用、表示，。若為做解答，令<，>。所作圖G<V1，V2，E>，則G為二部圖。由已知條件可知中每個(gè)結(jié)點(diǎn)關(guān)聯(lián)兩條邊，中每個(gè)結(jié)點(diǎn)也關(guān)聯(lián)兩條邊，即G滿足t2的“t條件”，所以存在到的完備匹配，又因?yàn)閨，因而對于任意的到的完備匹配M，不存在M-非飽和點(diǎn)，故M也是完全匹配。即使得7個(gè)題目的7個(gè)解答分別由7個(gè)讀者給出是辦得到的。43.給定二部圖G<V1，V2，E>，且|V1V2|m，|E|n，證明nm2/4。證明 設(shè)|V1|m1，則|V2|mm1，于是nm1(mm1)m1m。因?yàn)椋?，所以nm2/4。44.設(shè)G是面數(shù)r小于12的簡單平面圖，G中每個(gè)

33、結(jié)點(diǎn)的度數(shù)至少為3。(1)證明G中存在至多由4條邊圍成的面。(2)給出一個(gè)例子說明，若G中的面數(shù)為12，且每個(gè)結(jié)點(diǎn)的度至少為3，則(1)的結(jié)論不成立。證明 1)不妨設(shè)G是連通的，否則可以對它的每個(gè)連通分支進(jìn)行討論（因?yàn)槊總€(gè)連通分支均滿足條件）。因而由偶拉公式有nmr2， （1）又由已知條件得r12且nm， （2）將（2）其代入（1）得2mm12，m30。 （3）若所有的面均至少由5條邊圍成，則5r2m，rm， （4）將（2）、（4）代入（1）得2mmm，m30。 （5）（3）與（5）是矛盾的，因而必存在至多由4條邊圍成的面。2)十二面體圖有12個(gè)面，每個(gè)結(jié)點(diǎn)均為3度，每個(gè)面由5條邊圍成，并沒有

34、4條邊圍成的面。45.把平面分成b個(gè)區(qū)域，每兩個(gè)區(qū)域都相鄰，問b最大為幾？解 在每個(gè)區(qū)域放一個(gè)結(jié)點(diǎn)，當(dāng)兩區(qū)域相鄰時(shí)就在相應(yīng)的兩個(gè)結(jié)點(diǎn)之間連一條線，如此構(gòu)造了一個(gè)平面圖且是完全圖，而最大的平面完全圖為，所以b最大為4。46.設(shè)簡單平面圖G中結(jié)點(diǎn)數(shù)n7,邊數(shù)m15，證明G是連通的。證明 反證法。設(shè)G為非連通的，具有k2個(gè)連通分支,。設(shè)的結(jié)點(diǎn)數(shù)為，邊數(shù)為，1，2，。若存在1，則必為2，因?yàn)橹挥写藭r(shí)G為一個(gè)平凡圖并上一個(gè)才能使其邊數(shù)為15，可是不是平凡圖，這矛盾于G為平面圖這個(gè)事實(shí)，所以不存在1。若存在2，中至少有一條邊（因?yàn)镚為簡單圖），另外5個(gè)結(jié)點(diǎn)構(gòu)成時(shí)邊數(shù)最多，但充其量為10條邊，這與G有15條

35、邊矛盾。綜上所述，必大于等于3，1，2，。由定理10.37可知，3（2）36，1，2，。求和得36 （1）將n7,m15代入（1）得15216，于是1，這與k2矛盾。至此證明了G必為連通圖。47.設(shè)G是邊數(shù)m小于30的簡單平面圖，試證明G中存在結(jié)點(diǎn)v使得d(v)4。解 不妨設(shè)G是連通的，否則因?yàn)樗拿總€(gè)連通分支的邊數(shù)都應(yīng)小于30，因此可對它的每個(gè)連通分支進(jìn)行討論，所以可設(shè)G是連通的。若G中無回路，則G必為樹，結(jié)論顯然成立。若G中有回路，由于G為簡單圖，因而G中每個(gè)面至少由3個(gè)邊圍成，由定理10.37有m3n6。下面用反證法證明結(jié)論。若不然，G中所有結(jié)點(diǎn)的度數(shù)均大于等于5，由握手定理可知2m5n

36、，所以nm，將其代入m3n6得m3×m6，于是m30，與m30矛盾，所以一定存在結(jié)點(diǎn)v使得d(v)4。48.設(shè)G為有k(k2)個(gè)連通分支的平面圖，G的平面圖的每個(gè)面至少由f(f3)條邊圍成，則m(nk1)。解 設(shè)G的各面的邊界長度之和為。G的每條邊在計(jì)算時(shí)，均提供2，又因?yàn)镚的平面圖G¢ 的每個(gè)面至少由f條邊圍成，所以f2m。又因?yàn)閗1mn，將其代入f2m得f(k1mn)2m，整理得m(nk1)。49.證明：平面圖G的對偶圖G*是歐拉圖ÛG中每個(gè)面的次數(shù)均為偶數(shù)。證明 顯然G*是連通圖，設(shè)為G*的任一結(jié)點(diǎn)，位于G的面R中，由于R由偶數(shù)邊圍成，所以d()為偶數(shù)，由的

37、任意性可知，G*是歐拉圖。50.在由6個(gè)結(jié)點(diǎn)，12條邊構(gòu)成的連通平面圖G中，每個(gè)面由幾條邊圍成？為什么？解 每個(gè)面由3條邊圍成。因圖中結(jié)點(diǎn)數(shù)和邊數(shù)分別為n6，m12。根據(jù)歐拉公式nmr2得r8。又因?yàn)?m24，而簡單連通平面圖的每個(gè)面至少由3條邊圍成，所以G中每個(gè)面由3條邊圍成。51.給定連通簡單平面圖G<V，E，F(xiàn)>，且|V|6，|E|12。證明：對任意fF，d(f)3。證明 由偶拉公式得|V|E|F|2，所以|F|2|V|E|8，又由定理10.31得2|E|24。若存在fF，使得d(f)3，則3|F|2|E|24，于是|F|8，與|F|8矛盾。故對任意fF，d(f)3。52.證

38、明：不存在具有5個(gè)面，每兩個(gè)面都共享一條公共邊的平面圖G。證明 若存在這樣的平面圖G，設(shè)G的對偶圖為G*，則G*也是平面圖。由于G有5個(gè)面，所以G*具有5個(gè)結(jié)點(diǎn)。設(shè)為G*的任一結(jié)點(diǎn)，設(shè)它位于G的面R中。由于R與其余4個(gè)面均有公共邊，所以與其余面中的結(jié)點(diǎn)均相鄰，于是d()4，而且G*為簡單圖，所以G*必為，可是為非平面圖，這與G*為平面圖矛盾。53.已知一棵無向樹T有三個(gè)3度結(jié)點(diǎn)，一個(gè)2度結(jié)點(diǎn)，其余的都是1度結(jié)點(diǎn)。(1)T中有幾個(gè)1度結(jié)點(diǎn)？(2)試畫出兩棵滿足上述度數(shù)要求的非同構(gòu)的無向樹。解 (1)設(shè)T中有x個(gè)1度結(jié)點(diǎn)，則T中結(jié)點(diǎn)數(shù)n31x，T中邊數(shù)m31x13x。T中各結(jié)點(diǎn)度數(shù)之和3×

39、;32×11×x11x。由握手定理得11x2m62x，于是x5。所以T中有5個(gè)1度結(jié)點(diǎn)。(2)下圖中所示的兩棵樹均滿足要求，但它們是不同構(gòu)的。54.一棵無向樹T有ni個(gè)度數(shù)為i的結(jié)點(diǎn)，i2，3，k，問有多少個(gè)1度結(jié)點(diǎn)？解 設(shè)T中有x個(gè)1度結(jié)點(diǎn)，則T中結(jié)點(diǎn)數(shù)nx，T中邊數(shù)mx1。T中各結(jié)點(diǎn)度數(shù)之和1×xx。由握手定理得2(x1)x，于是x222。所以T中有2個(gè)1度結(jié)點(diǎn)。55.證明恰有兩個(gè)結(jié)點(diǎn)的度數(shù)為1的樹必為一條通路。證明 設(shè)T為一棵具有兩個(gè)1度結(jié)點(diǎn)的樹（n，m），則mn1且有2m2(n1)。又T連通且除兩個(gè)1度結(jié)點(diǎn)外，其他結(jié)點(diǎn)度數(shù)均大于等于2，而2，有2(n1)2

40、，故2(n1)。因此n2個(gè)分支結(jié)點(diǎn)的度數(shù)都恰為2，即T為一條通路。56.設(shè)無向圖G是由k(k2)棵樹構(gòu)成的森林，至少在G中添加多少條邊才能使G成為一棵樹？解 設(shè)G的k個(gè)連通分支為、，設(shè)結(jié)點(diǎn)，i1，2，k。在G中添加邊(，)，i1，2，k，設(shè)所得圖為，則連通且無回路，因而是樹。所以邊的添加數(shù)k1是使得G為樹的最小數(shù)目。57.試畫出4個(gè)結(jié)點(diǎn)和5個(gè)結(jié)點(diǎn)的所有非同構(gòu)的無向樹。解 4個(gè)結(jié)點(diǎn)的所有非同構(gòu)的無向樹有2棵，如圖（1）和（2）所示。5個(gè)結(jié)點(diǎn)的所有非同構(gòu)的無向樹有3棵，如圖（3）、（4）和（5）所示。58.設(shè)G<V，E>是連通圖且eE，試證明：e是G的割邊Ûe包含在G的每棵生

41、成樹中。證明 Ü設(shè)e包含在G的每棵生成樹中，但e不是G的割邊。在圖G中刪去e得圖G¢，G¢ 仍是連通圖。對G來說必有一棵生成樹T，T中不包含邊e，與假設(shè)矛盾。Þ設(shè)邊e不是G的割邊，刪去e，G就分成兩個(gè)互不連通的子圖G1和G2。對于G的任一一棵生成樹T，由于T是連通圖，故連結(jié)G1和G2之間的唯一邊e必在T中。59.如何由有向圖G的鄰接矩陣A判定G是否是根樹，若是根樹，如何定出它的樹根和樹葉。解 一個(gè)有向圖G為根樹，它的鄰接矩陣A必須滿足：1）所有主對角元素為0；2）矩陣中有一列元素全為0，所有其它列中都恰有一個(gè)1。如果一個(gè)鄰接矩陣對應(yīng)的有向圖是根樹，那么全

42、0列對應(yīng)的結(jié)點(diǎn)為根。而全0行對應(yīng)的結(jié)點(diǎn)為樹葉。60.設(shè)T為任意一棵正則二叉樹，m為邊數(shù)，t為樹葉數(shù)，試證明m2t2，其中t2。證明 設(shè)T中結(jié)點(diǎn)數(shù)為n，分支結(jié)點(diǎn)數(shù)為i，根據(jù)正則二叉樹的定義得下面等式成立：nit (1)m2i (2)mn1 (3)由以上三式整理得m2t2。61.證明一棵完全二叉樹必有奇數(shù)個(gè)結(jié)點(diǎn)。證明 設(shè)完全二叉樹T有n個(gè)結(jié)點(diǎn)，m條邊。依定義，T中每個(gè)分支點(diǎn)都關(guān)聯(lián)兩條邊，所以m必為偶數(shù)。又由T是樹，有nm1，故n為奇數(shù)。因此，完全二叉樹必有奇數(shù)個(gè)結(jié)點(diǎn)。62.畫出所有不同構(gòu)的高為2的二叉樹，其中有多少棵正則二叉樹？有多少棵滿二叉樹？解 高為2的所有不同構(gòu)的二叉樹有7棵，如圖所示。其中

43、有2棵正則二叉樹，如圖(5)和(7)；1棵滿二叉樹如圖(7)。63.求帶權(quán)2、3、5、7、8的最優(yōu)二叉樹及其權(quán)，并求該二叉樹對應(yīng)的2元前綴碼。解 (1)構(gòu)造最優(yōu)二叉樹的全部過程如圖所示。樹的權(quán)為(23)×3(578)×255。(2)該二叉樹對應(yīng)的2元前綴碼為000，001，01，10，11。64.(1)求帶權(quán)為1、1、2、3、3、4、5、6、7的最優(yōu)三叉樹。(2)求帶權(quán)為1、1、2、3、3、4、5、6、7、8的最優(yōu)三叉樹。解 求最優(yōu)叉樹的Huffman算法：為分支數(shù)，t為樹葉數(shù)，(1)若為整數(shù)，求最優(yōu)叉樹的算法與求最優(yōu)2叉樹的算法類似，只是每次取個(gè)最小的權(quán)。(2)若-1除t-1余數(shù)s不為0，1s-1，將s+1個(gè)較小的權(quán)對應(yīng)的樹葉為兄弟放在最長的通路上，然后的算法同(1)。(1)所求樹的樹葉數(shù)t9，分支數(shù)3。4，說明所求3叉樹為正則3叉樹。由Huffman算法得3叉樹如圖所示。(2) 所求樹的樹葉數(shù)t10，分支數(shù)3。，于是-1除t-1余數(shù)為1，由Huffman算法得3叉樹如圖所示。65.在下面給出的3個(gè)符號串集合中，哪些是前綴碼？哪些不是前綴碼？若是前綴碼，構(gòu)造二叉樹，其樹葉代表二進(jìn)制編碼。若不是前綴碼，則說明理由。(1)0，10，110，1111。(2)1，01，001，000。(3)1，11，101，00