離散數(shù)學(xué)答案劉玉珍 劉永梅

1、習(xí)題11.11 若n個(gè)頂點(diǎn)的簡(jiǎn)單無向圖G中至少有2個(gè)孤立點(diǎn)，則結(jié)論自然成立；若G中只有一個(gè)孤立點(diǎn)，而，則G中至少有3個(gè)頂點(diǎn)，其中至少有2個(gè)非孤立點(diǎn)，可不考慮孤立點(diǎn)；若G中無孤立點(diǎn)，則G中n個(gè)頂點(diǎn)度數(shù)均不小于1.現(xiàn)設(shè)G中n個(gè)頂點(diǎn)的度數(shù)均不小于1，又G為簡(jiǎn)單圖，故所有頂點(diǎn)的度數(shù)均不大于n-1，即n個(gè)頂點(diǎn)的度數(shù)的取值只能是1，2，n-1,由鴿舍原理知，結(jié)論成立。2 設(shè)G有x個(gè)頂點(diǎn)，則故所證不等式成立。5.（1）非同構(gòu)的4個(gè)頂點(diǎn)的自補(bǔ)圖只有一個(gè)；非同構(gòu)的5個(gè)頂點(diǎn)的自補(bǔ)圖有2個(gè)（2）為自補(bǔ)圖與的邊數(shù)相同，設(shè)均為m，又與的邊數(shù)之和為的邊數(shù)，即=2m，亦即=4m，故n為4的倍數(shù)，即n=4k，或n-1為4的倍

2、數(shù)，即n=4k+1，6.（1）<0,1,1,2,3,3>,<3,3,3,3>均為可圖解的，其對(duì)應(yīng)圖為<1,3,3,3>非可圖解，否則，設(shè)，由于要構(gòu)成無向簡(jiǎn)單圖，故，之間必定有邊關(guān)聯(lián)，這與矛盾，< 2，3，4，4，5>,<2,2,4>非可圖解，以為簡(jiǎn)單圖中所有頂點(diǎn)的度數(shù)多為n-1。<1,2,2,3,4,5>z中有奇數(shù)個(gè)，故非可圖解。（2）充分性：<, ,>可圖解添加度數(shù)為的頂度，與度數(shù)為, ,的頂點(diǎn)相鄰<, >可圖解。必要性：<, >可圖解，設(shè)度數(shù)為的頂點(diǎn)與度數(shù)分別為，的頂點(diǎn)相鄰，刪去度數(shù)

3、為的頂點(diǎn)<, ,>可圖解。7.設(shè)的頂點(diǎn)為，隨意用紅色和藍(lán)色涂的邊，則由引出的5條邊中至少有3條同色邊，不妨設(shè)存在3條紅色邊，且該3條邊的另一端點(diǎn)分別為，。若，構(gòu)成的中的邊再有一條，比如（，）為紅色邊，則，構(gòu)成的為紅色；若，的邊全為藍(lán)色，則結(jié)論已成立。習(xí)題11.21. 強(qiáng)分圖為：?jiǎn)蜗蚍謭D為：弱分圖為：2.（1）G弱連通G對(duì)應(yīng)的無向圖連通至少需要n-1條邊連接n個(gè)頂點(diǎn)n-1m.G為簡(jiǎn)單圖m=n(n-1),故（2）G強(qiáng)聯(lián)通，由定理11.2.3知，G至少有n條邊，故3.若G非基本回路，又G連通，則G中必有頂點(diǎn)的度數(shù)不等于2，矛盾。4設(shè)e含于兩個(gè)不同的基本回路，與中，則不含于回路中，由推論1

4、1.2.2知，存在從到的基本回路，且不含于該基本回路中。5.設(shè)G不連通，且有個(gè)連通分支，其中有個(gè)頂點(diǎn)，=1，2，k。則。即，矛盾，故G連通。步驟依次對(duì)應(yīng)為1，3，2，5，4，9，6，7，8，11，12，10，13=1=2，=2，=4=3，=8，=5=5，=6，=9，=9，=9，=10長(zhǎng)度分別為4，5，4，6，5習(xí)題11.31.（1）令（2）由知，到的長(zhǎng)度為4的通路有4條。（3）由知，到自身的長(zhǎng)度為3的回路有3條。（4）由知，長(zhǎng)度不超過4的通路條數(shù)為中元素之和為72，其中回路的條數(shù)為中對(duì)角線元素之和19。2.（1）令故可達(dá)矩陣3（1）習(xí)題11.41.（1）如（2）如（3）如（4）如2.(a) 通

5、路為(b) 回路為3.(a) 是圖，有一個(gè)回路為(b)非圖，取則。4.設(shè)G中存在與不相鄰，且，令，則為n-2個(gè)頂點(diǎn)的簡(jiǎn)單圖，且其邊數(shù)，與為簡(jiǎn)單圖矛盾，故G中任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和均不小于n，因此，G為圖。左圖中有4個(gè)頂點(diǎn)，條邊，但非圖。5若G中有不相鄰的兩個(gè)頂點(diǎn)，則它們的度數(shù)之和不小于nG為圖。，左圖中有3個(gè)頂點(diǎn)，且，但非圖。6，（1）acbeda 18(2)aedbca,acbdea,16習(xí)題11.51. 設(shè)，則2. 構(gòu)造偶圖G=<,>，其中，適合，則G如右圖所示按照中度數(shù)小的頂點(diǎn)，優(yōu)先于中度數(shù)小的頂點(diǎn)匹配的原則，得一匹配也是最大匹配和完備匹配。習(xí)題11.61 若G不連通

6、，則可適當(dāng)添加邊但不增加面，得連通圖，設(shè)的頂點(diǎn)數(shù)、邊數(shù)、面數(shù)分別為,，G的邊數(shù)為m，則=n, >m, =k。由Euler公式知-+=2m<=n+k-2，由定理11.6.3知3n-6，故n+k-23n-6，即k2n-4。若G連通，則n-m+k=2，又m3n-6，故k2n-4。2 如G： ，則： G, 均為平面圖。3 設(shè)G與均為平面圖，且均連通，G與的邊數(shù)分別為m與，則m3n-6,3n-6(若G與不連通，則可適當(dāng)添加邊使之為連通平面圖，不等式仍成立)。而，矛盾，故G或非平面圖。4 不妨設(shè)G連通，否則，G的每個(gè)連通分支的邊數(shù)均應(yīng)小于30，則可對(duì)G的每個(gè)分支進(jìn)行討論。若G中無回路，則G必為

7、樹，結(jié)論顯然成立。若G中有回路，則簡(jiǎn)單圖G中每個(gè)面至少由3條邊圍成，故G至少有3個(gè)頂點(diǎn)，從而。若G中所有頂點(diǎn)的度數(shù)均不小于5，則，與矛盾，故結(jié)論成立。5 （1）設(shè)G不連通，且有個(gè)連通分支,，設(shè)的頂點(diǎn)數(shù)為，邊數(shù)為，i=1,2,k。若，則k=2，因?yàn)榇藭r(shí)G為一個(gè)平面圖，并上一個(gè)才能使其邊數(shù)為15，但含子圖，故為非平面圖，與G為平面圖矛盾；若，則簡(jiǎn)單圖中至多只有一條邊，另外5個(gè)頂點(diǎn)構(gòu)成時(shí)邊數(shù)最多，但也只有10條邊，與G有15條邊矛盾。故，從而，將m=15,n=7代入，得,與矛盾，故G為連通圖。（2）簡(jiǎn)單圖G的每個(gè)面至少由3條邊圍成，設(shè)G中至少有一個(gè)面由4條或4條以上的邊圍成，則2m>3m，即k

8、<10，而由Euler公式知，n-m+k=2即k=10，矛盾，故G的每個(gè)面均由3條邊圍成。6（a）非平面圖， V6 V5 V2 V7 V3 V4因?yàn)楹訄D。 V1 V4 V6 V5（b）非平面圖，因?yàn)楹哂?V2 V7的子圖（右圖中刪去即同構(gòu)）。 V3 7 （a），虛線所示即為對(duì)偶圖。 （b），虛線所示為對(duì)偶圖。8（1）如第7題（a）所示。（2）G為平面圖，且為平面圖。連通G連通，設(shè)G的面數(shù)為k，則n=的頂點(diǎn)數(shù)=k。由Euler公式知，n-m+n=2,即m=2n-2。9（a）由第10題知，色數(shù)為2。（b）中含長(zhǎng)度為奇數(shù)的基本回路，該回路上的頂點(diǎn)需3種色，而3種色夠用，故色數(shù)為3。（c）

9、中含長(zhǎng)度為奇數(shù)的基本回路，該回路上的頂點(diǎn)需3種色，而該基本回路外另有一度數(shù)為5的頂點(diǎn)與該基本回路上每個(gè)頂點(diǎn)相鄰，故至少需4種，而4種夠用，故色數(shù)為4。10充分性：G中無奇數(shù)長(zhǎng)度的基本回路G為偶圖，記作G=<,E>，給中頂點(diǎn)著第一種色，中頂點(diǎn)著第二種色，則G為2可著色的。必要性：G為2可著色的，第一種色的頂點(diǎn)集記為，第二種色的頂點(diǎn)集記為，則中頂點(diǎn)互不相鄰，中頂點(diǎn)也互不相鄰，故G=<,>為偶圖。習(xí)題11.71 設(shè)有x個(gè)1度頂點(diǎn)，則2m=2(2+1+3+x-1)=x×1+2×2+1×3+3×4x=9。2 當(dāng)n=2時(shí)，,，且+=2

10、5;2-2，則=1，存在一棵頂點(diǎn)度數(shù)分別為1，1的樹 ，結(jié)論成立。設(shè)n=k>2時(shí)，結(jié)論成立，則n=k+1時(shí)，,中至少有一個(gè)大于1。不妨設(shè)>1，否則=，則=k+12(k+1)-2，且,中至少有2個(gè)為1。不妨設(shè)=1，否則2k+1，故2(k+1)-2。由歸納假設(shè)知，存在一棵頂點(diǎn)度數(shù)分別為-1, ,1的無向樹。在該樹上添加一個(gè)度數(shù)為1的頂點(diǎn)，它只與度數(shù)為D的頂點(diǎn)相鄰，則得一棵頂點(diǎn)度數(shù)分別為, ,1,1，即, ,的無向數(shù)。3 樹中無回路樹中無奇數(shù)長(zhǎng)度的基本回路樹為偶圖。4 設(shè)G中有k棵樹，其中第i棵樹的頂點(diǎn)數(shù)為，邊數(shù)為，則=-1，i=1，k，故m=-k=n-k。5 設(shè)G中無回路，則G的k1個(gè)連通分支也無回路，故連通分支均為樹，由第4題知m=n-k<n，與mn矛盾，故G中必有回路。6 （a） （b）7 不一定，如右圖 5個(gè)頂點(diǎn)只有1頂點(diǎn)入度為0，其余頂點(diǎn)入度為1，但非有向樹。8 設(shè)T中頂點(diǎn)數(shù)為n，其中有k個(gè)分支點(diǎn)，由二元正則樹的定義知，n=k+t,m=2k,m=n-1m=2t-2。9 （1）、（3）非前綴碼，（2）為前綴碼。