第10章習題答案

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

2、中至多有9個結點。2.若有n個人，每個人恰有3個朋友，則n必為偶數。證明 設、表示任給的n個人，以、為結點，當且僅當兩人為朋友時其對應的結點之間連一條邊，這樣得到一個簡單圖G。由握手定理知3n必為偶數，從而n必為偶數。3.判斷下列各非負整數列哪些是可圖化的？哪些是可簡單圖化的？(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)。解 由于非負整數列d(d1，d2，dn)是可圖化的當且僅當0(mod 2)，所以(1)、(2)、(3)、(5)能構成無向圖的度數列。(1)、(2)、(3)是可簡單圖化的。其對應的無

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

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

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

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

7、。12.設G為至少有兩個結點的簡單圖，證明：G中至少有兩個結點度數相同。證明 若G中孤立結點的個數大于2，結論顯然成立。若G中有1個孤立結點，則G中至少有3個結點，因而不考慮孤立結點，就是說G中每個結點的度數都大于等于1。又因為G為簡單圖，所以每個結點的度數都小于等于n-1。因而G中結點的度的取值只能是1，2，n-1這n個數。由抽屜原理可知，取n-1個值的n個結點的度至少有兩個是相同的。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個：bceb，bdeb，cdec，bcdb。長度最大的基本回路共1個：abdcefa。(4)長度最小的簡單回路共4個：bceb，bdeb，cdec，bcdb。長度最大的簡單回路2個：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)各結點的出度、入度和度。(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個abdea，adea，bdcb.簡單回路共4個：abdea，adea，bdcb

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

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

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

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

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

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

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

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

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

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

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

21、回路為3條。(5)D中長度小于等于4的路總數為、中全體元素之和：710131646，其中回路數為：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)求出可達矩陣P。(5)求出強分圖。解 (1)求G的鄰接矩陣為：(2)由于 所以v1到v4長度為1、2、3和4的路的個數分別為1、1、2、3。(3)由于 再由定理10.19可知，所以ATA的第(2，2)元素為3，表明那些邊以為終結點

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

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

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

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

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

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

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

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

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

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

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

33、結點的度數至少為3。(1)證明G中存在至多由4條邊圍成的面。(2)給出一個例子說明，若G中的面數為12，且每個結點的度至少為3，則(1)的結論不成立。證明 1)不妨設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個面，每個結點均為3度，每個面由5條邊圍成，并沒有

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

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

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

37、任意性可知，G*是歐拉圖。50.在由6個結點，12條邊構成的連通平面圖G中，每個面由幾條邊圍成？為什么？解 每個面由3條邊圍成。因圖中結點數和邊數分別為n6，m12。根據歐拉公式nmr2得r8。又因為2m24，而簡單連通平面圖的每個面至少由3條邊圍成，所以G中每個面由3條邊圍成。51.給定連通簡單平面圖G<V，E，F>，且|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*，則G*也是平面圖。由于G有5個面，所以G*具有5個結點。設為G*的任一結點，設它位于G的面R中。由于R與其余4個面均有公共邊，所以與其余面中的結點均相鄰，于是d()4，而且G*為簡單圖，所以G*必為，可是為非平面圖，這與G*為平面圖矛盾。53.已知一棵無向樹T有三個3度結點，一個2度結點，其余的都是1度結點。(1)T中有幾個1度結點？(2)試畫出兩棵滿足上述度數要求的非同構的無向樹。解 (1)設T中有x個1度結點，則T中結點數n31x，T中邊數m31x13x。T中各結點度數之和3×

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

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

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

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

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