第10章習題答案

習題101.(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é)點有6個，其余結(jié)點的度數(shù)均小于3，問圖G中至多有幾個結(jié)點為什么解(1)設G有m條邊，由握手定理得2m＝＝2＋2＋3＋3＋4＝14，所以G的邊數(shù)7條。(2)由于這兩個序列中有奇數(shù)個是奇數(shù)，由握手定理的推論知，它們都不能成為圖的度數(shù)列。(3)由握手定理得＝2m＝24，度數(shù)為3的結(jié)點有6個占去18度，還有6度由其它結(jié)點占有，其余結(jié)點的度數(shù)可為0、1、2，當均為2時所用結(jié)點數(shù)最少，所以應由3個結(jié)點占有這6度，即圖G中至多有9個結(jié)點。2.若有n個人，每個人恰有3個朋友，則n必為偶數(shù)。證明設、、…、表示任給的n個人，以、、…、為結(jié)點，當且僅當兩人為朋友時其對應的結(jié)點之間連一條邊，這樣得到一個簡單圖G。由握手定理知＝3n必為偶數(shù)，從而n必為偶數(shù)。3.判斷下列各非負整數(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)。解由于非負整數(shù)列d＝(d1，d2，…，dn)是可圖化的當且僅當≡0(mod2)，所以(1)、(2)、(3)、(5)能構(gòu)成無向圖的度數(shù)列。(1)、(2)、(3)是可簡單圖化的。其對應的無向簡單圖如圖所示。)(5)是不可簡單圖化的。若不然，存在無向圖G以為1，3，3，3度數(shù)列，不妨設G中結(jié)點為、、、，且d()＝1，d()＝d()＝d()＝3。而只能與、、之一相鄰，設與相鄰，于是d()＝d()＝3不成立，矛盾。4.試證明圖10-48中的兩個無向圖是不同構(gòu)的。%證明因為兩圖中都有4個3度結(jié)點，左圖中每個3度結(jié)點均與2個2度結(jié)點鄰接，而右圖中每個3度結(jié)點均只與1個2度結(jié)點鄰接，所以這兩個無向圖是不同構(gòu)的。5.在圖同構(gòu)意義下，試畫出具有三個結(jié)點的所有簡單有向圖。解具有三個結(jié)點的所有非同構(gòu)的簡單有向圖共16個，如圖所示，其中(8)(16)為其生成子圖。6.給定無向完全圖G＝<V，E>，且|V|＝4。在圖同構(gòu)意義下，試求：(1)G的所有子圖。(2)G的所有生成子圖。解(1)G的所有子圖如圖所示。(2)圖(8)(18)是G的所有生成子圖。—7.(1)試給出一個五個結(jié)點的自補圖?！?2)是否有三個結(jié)點或六個結(jié)點的自補圖。(3)一個圖是自補圖，則其對應的完全圖的邊數(shù)必是偶數(shù)。(4)一個自補圖的結(jié)點數(shù)必是4k或4k＋1。解(1)五個結(jié)點的圖G與它的補圖如圖所示。對G與建立雙射：，，，，。顯然這兩個圖保持相應點邊之間的對應的關(guān)聯(lián)關(guān)系，故G。因此，G是五個結(jié)點的自補圖。(3)設圖G是自補圖，有m條邊，G對應的完全圖的邊數(shù)為s，則G對應的補圖的邊數(shù)為s－m。因為G，故邊數(shù)相等，即有m＝s－m，s＝2m，因此G對應的完全圖的邊數(shù)s為偶數(shù)。](2)由(3)知，自補圖對應的完全圖的邊數(shù)為偶數(shù)。n個結(jié)點的完全圖6時，的邊數(shù)為奇數(shù)，因此不存在三個結(jié)點或六個結(jié)點的自補圖。的邊數(shù)為n(n－1)，當n＝3或n＝(4)設G為n階自補圖，則需n(n－1)能被2整除，因此n必為4k或4k＋1形式。8.一個n(n≥2)階無向簡單圖G中，n為奇數(shù)，已知G中有r個奇數(shù)度結(jié)點，問G的補圖中有幾個奇數(shù)度結(jié)點解由G的補圖的定義可知，G∪為，由于n為奇數(shù)，所以中各頂點的度數(shù)n－1為偶數(shù)。對于圖＝n－1，由于n－1為偶數(shù)，所G的任意結(jié)點，應有也是的頂點，且＋＝以和奇偶性相同，因此若G中有r個奇數(shù)度結(jié)點，則中也有r個奇數(shù)度結(jié)點。9.畫出4階無向完全圖K4的所有非同構(gòu)的生成子圖，并指出自補圖來。解下圖中的11個圖是K4的全部的非同構(gòu)的生成子圖，其中(7)為自補圖。;10.設圖G中有9個結(jié)點，每個結(jié)點的度不是5就是6。試證明G中至少有5個6度結(jié)點或至少有6個5度結(jié)點。證明由握手定理的推論可知，G中5度結(jié)點數(shù)只能是0、2、4、6、8五種情況（此時6度結(jié)點數(shù)分別為9、7、5、3、1）。以上五種情況都滿足至少5個6度結(jié)點或至少6個5度結(jié)點的情況。11.證明3度正則圖必有偶數(shù)個結(jié)點。證明設G為任一3度正則圖，有n個結(jié)點、、…、，則所有結(jié)點度數(shù)之和＝3n。若n為奇數(shù)，則3n也為奇數(shù)，與握手定理矛盾。故n為偶數(shù)。12.設G為至少有兩個結(jié)點的簡單圖，證明：G中至少有兩個結(jié)點度數(shù)相同。證明若G中孤立結(jié)點的個數(shù)大于2，結(jié)論顯然成立。若G中有1個孤立結(jié)點，則G中至少有3個結(jié)點，因而不考慮孤立結(jié)點，就是說G中每個結(jié)點的度數(shù)都大于等于1。又因為G為簡單圖，所以每個結(jié)點的度數(shù)都小于等于n-1。因而G中結(jié)點的度的取值只能是1，2，…，n-1這n個數(shù)。由抽屜原理可知，取n-1個值的n個結(jié)點的度至少有兩個是相同的?！?3.給定無向圖G＝<V，E>如圖10-49所示，試求：(1)從a到d的所有基本路。(2)從a到d的所有簡單路。(3)長度分別是最小和最大的基本回路。(4)長度分別是最小和最大的簡單回路。(5)從a到d的距離。(6)(G)、(G)、(G)、(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。(