第10章習題答案

習題101.(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條邊，由握手定理得2m＝＝2＋2＋3＋3＋4＝14，所以G的邊數7條。(2)由于這兩個序列中有奇數個是奇數，由握手定理的推論知，它們都不能成為圖的度數列。(3)由握手定理得＝2m＝24，度數為3的結點有6個占去18度，還有6度由其它結點占有，其余結點的度數可為0、1、2，當均為2時所用結點數最少，所以應由3個結點占有這6度，即圖G中至多有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(mod2)，所以(1)、(2)、(3)、(5)能構成無向圖的度數列。(1)、(2)、(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。在圖同構意義下，試求：(1)G的所有子圖。(2)G的所有生成子圖。解(1)G的所有子圖如圖所示。(2)圖(8)(18)是G的所有生成子圖?！?.(1)試給出一個五個結點的自補圖。【(2)是否有三個結點或六個結點的自補圖。(3)一個圖是自補圖，則其對應的完全圖的邊數必是偶數。(4)一個自補圖的結點數必是4k或4k＋1。解(1)五個結點的圖G與它的補圖如圖所示。對G與建立雙射：，，，，。顯然這兩個圖保持相應點邊之間的對應的關聯(lián)關系，故G。因此，G是五個結點的自補圖。(3)設圖G是自補圖，有m條邊，G對應的完全圖的邊數為s，則G對應的補圖的邊數為s－m。因為G，故邊數相等，即有m＝s－m，s＝2m，因此G對應的完全圖的邊數s為偶數。](2)由(3)知，自補圖對應的完全圖的邊數為偶數。n個結點的完全圖6時，的邊數為奇數，因此不存在三個結點或六個結點的自補圖。的邊數為n(n－1)，當n＝3或n＝(4)設G為n階自補圖，則需n(n－1)能被2整除，因此n必為4k或4k＋1形式。8.一個n(n≥2)階無向簡單圖G中，n為奇數，已知G中有r個奇數度結點，問G的補圖中有幾個奇數度結點解由G的補圖的定義可知，G∪為，由于n為奇數，所以中各頂點的度數n－1為偶數。對于圖＝n－1，由于n－1為偶數，所G的任意結點，應有也是的頂點，且＋＝以和奇偶性相同，因此若G中有r個奇數度結點，則中也有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為偶數。12.設G為至少有兩個結點的簡單圖，證明：G中至少有兩個結點度數相同。證明若G中孤立結點的個數大于2，結論顯然成立。若G中有1個孤立結點，則G中至少有3個結點，因而不考慮孤立結點，就是說G中每個結點的度數都大于等于1。又因為G為簡單圖，所以每個結點的度數都小于等于n-1。因而G中結點的度的取值只能是1，2，…，n-1這n個數。由抽屜原理可知，取n-1個值的n個結點的度至少有兩個是相同的?！?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。(