圖論與代數結構第一二三章習題解答

1、習題一1. 一個工廠為一結點；若兩個工廠之間有業(yè)務聯(lián)系，則此兩點之間用邊相聯(lián)；這樣就得到一個無向圖。若每點的度數為3，則總度數為27，與圖的總度數總是偶數的性質矛盾。若僅有四個點的度數為偶數，則其余五個點度數均為奇數，從而總度數為奇數，仍與圖的總度數總是偶數的性質矛盾。（或者利用度數為奇數的點的個數必須為偶數個）2. 若存在孤立點，則m不超過Kn-1的邊數, 故m <= (n-1)(n-2)/2, 與題設矛盾。3. 4. 用向量(a1,a2,a3)表示三個量杯中水的量, 其中ai為第i杯中水的量, i = 1,2,3. 以滿足a1+a2+a3 = 8 (a1,a2,a3為非負整數)的所有

2、向量作為各結點, 如果(a1,a2,a3)中某杯的水倒?jié)M另一杯得到 ( a1, a2, a3 ) , 則由結點到結點畫一條有向邊。這樣可得一個有向圖。本題即為在此圖中找一條由( 8, 0, 0 )到( 4, 4, 0 )的一條有向路，以下即是這樣的一條：( 8, 0, 0 )( 5, 3, 0 )( 5, 0, 3 )( 2, 3, 3 )( 2, 5, 1 )(7, 0, 1 )( 7, 1, 0 )( 4, 4, 0 )( 4, 1, 3 )5. 可以。V1V3V2V5V4V6V1V2V4V3V6V56 若9個人中沒有4個人相互認識，構造圖G，每個點代表一個點，兩個人相互認識則對應的兩個點

3、之間有邊。1） 若可以找到點v，d(v)>5，則與v相連的6個點中，要么有3個相互認識，要么有3個相互不認識（作K6并給邊涂色:紅=認識，藍=不認識，只要證圖中必有同色三角形。v1有5條邊，由抽屜原則必有三邊同色(設為紅)，這三邊的另一頂點設為v2, v3, v4。若v2v3v4有一邊為紅，則與v1構成紅色，若v2v3v4的三邊無紅色，則構成藍色）。若有3個人相互認識，則這3個人與v相互認識，這與假設沒有4個人相互認識矛盾，所以這6個人中一定有3個人相互不認識2） 若可以找到點v，d(v)<5，不與v相連的點至少有4個，由于沒有4個人相互認識，所以這4個人中至少有2個人相互不認識，

4、這兩個人與v共3個人相互不認識3） 若每個點的度數都為5，則有奇數個度數為奇數的點，不可能。7. 同構。同構的雙射如下： vV1V2V3V4V5V6f (v)bacedf8. 記e1= (v1,v2), e2= ( v1,v4), e3= (v3,v1), e4= (v2,v5), e5= (v6,v3), e6= (v6,v4), e7= (v5,v3), e8= (v3,v4), e9 = (v6,v1),則鄰接矩陣為：關聯(lián)矩陣為：邊列表為：A= (1,1,3,2,6,6,5,3,6), B= (2,4,1,5,3,4,3,4,1).正向表為：A= (1,3,4,6,6,7,10), B=

5、 (2,4,5,1,4,3,3,4,1). 習題二1. 用數學歸納法。k=1時，由定理知結論成立。設對于k命題成立。對于k+1情形，設前k個連通支的結點總個數為n1, 則由歸納假設，前k個連通支的總邊數m1<= ( n1k+1)( n1k)/2。最后一個連通支的結點個數為nn1, 其邊數m2<= ( nn1)( nn11)/2，所以，G的總邊數m= m1+ m2<= ( n1k+1)( n1k)/2 + ( nn1)( nn11)/2n1=n1時，m<= ( (n-1)k+1)( (n-1)k)/2 +0= ( (nk)( (nk1)/2, 命題成立。n1= n2時，由

6、于 n1<=k, 故m<= ( (n2)k+1)( n1k)/2 + ( nn1)( nk1)/2( nk)( nk1)/2 ,命題成立。2若G連通，則命題已成立；否則， G至少有兩個連通支。任取結點v1, v2，若G的補圖中邊(v1, v2)不存在，則(v1, v2)是G中邊，v1, v2在G的同一個連通支（假設為G1）中。設G2是G的另一連通支，取v3ÎG2,則v1® v3 ®v2是補圖中v1到v2的一條道路，即結點v1, v2在補圖中有路相通。由v1, v2的任意性，知補圖連通。3設L1,L2是連通圖G的兩條最長路，且L1,L2無公共結點。設L1

7、,L2的長度(邊數)為p. 由于G是連通的，故L1上必有一結點v1與L2上一結點v2有道路L相通。結點v1將L1分為兩部分，其中一部分的長度 ³ p/2 , 記此部分道路為L3。同樣，結點v2將L2分為兩部分，其中一部分L4的長度 ³ p/2 。這樣，L3LL4就是G的一條新的道路，且其長度大于p, 這與G的最長路(L1)的長度是p的假設矛盾。4. 對結點數n作歸納法。（1）n= 4時m5. 若有結點的度1, 則剩下的三結點的度數之和4，不可能。于是每個結點的度2，從而存在一個回路。若此回路為一個三角形，則還有此回路外的一結點，它與此回路中的結點至少有二條邊，從而構成一個新

8、的含全部四個結點的回路，原來三角形中的一邊（不在新回路中）即是新回路的一條弦。若此回路為含全部四個結點的初等回路，則至少還有一邊不在回路上，此邊就是該回路的一條弦。（2）設n-1情形命題已成立。 對于n情形：若有結點的度1, 則去掉此結點及關聯(lián)邊后，依歸納假設命題成立。若有結點v的度=2, 設v關聯(lián)的兩結點為s,t，則去掉結點v及關聯(lián)邊、將s,t合并為一個結點后，依歸納假設命題成立。若每個結點的度3，由書上例2.1.3的結果知命題成立。5 a)對于任意邊(u,v),由于不存在三角形，所以d(u)+d(v)<=n，對所有m條邊求和，不等式左邊每個d(v)被計算了d(v)次b) 對n歸納，設

9、小于n時不等式成立，當|V|=n時，刪去邊(u,v)及點u，v以及相關的邊得到G'，由歸納假設，G'最多(n-2)2/4條邊，由于(u,v)與G'不構成三角形，因此由G'變回G時最多增加(n-2)+1條邊，所以G的邊最多(n-2)2/4+(n-2)+1=n2/4注：此題與三角形的存在性無關設最大度數為k，且d(v)=k，令E0=與v相連的邊，E1=不與v相連的邊，則|E0|=k，|E1|<=(n-k-1)*k，其中n-k-1表示去除了v及其鄰點，這些點的度數都小于等于km=|E0|+|E1|<=nk-k2<= n2/46問題可化為求下列紅線表示

10、的圖是否存在一條歐拉道路的問題：存在歐拉道路！7 設C是H道路，當S中頂點在C上不相鄰時，C-S最多被分成|S|+1段，而當S中頂點有相鄰時段數將更少，而C是G的生成子圖，所以t<=|S|+18由推論2.4.1, 只需驗證G的任意一對結點的度數之和大于或等于n即可。 若存在結點v1, v2滿足deg(v1)+deg(v2)<n, 則Gv1, v2 的邊數<= Kn-2的邊數= (n-2)(n-3)/2 . 另一方面，由題設知G v1, v2 的邊數m（deg(v1)+deg(v2)）(n-1)(n-2)/2+2n= (n-2)(n-3)/2 ,與上式矛盾。9 對n進行數學歸納

11、法，設n小于等于k時命題成立，則當n=k+1時對任意頂點v，G-v得到的G'仍是有向完全圖，由歸納假設存在H道路v1v2vk若G中存在邊(v,v1)或(vk,v)則命題成立否則G中存在邊(v1,v)和(v,vk)，這也意味著可以找到i，1<=i<k，有邊(vi,v)和(v,vi+1)此時v1v2vivvi+1.vk為H道路10 對于任意的點u,v，若u與v認識，則d(u)+d(v)=(n-2)+2=n若u不認識v，則從V-u,v中讓取一點w，w認識u和v否則若w不認識u，則v和w都不認識u，v和w合起來只能最多認識n-3個人，矛盾。由w的任意性，d(u)+d(v)>=

12、2(n-2)，當n>=4時，2(n-2)>=n所以對任意兩個點度數和大于等于n11 對于這q條邊，每條邊的兩個端點壓縮合并為一個點，并去掉重邊得到G'G'各點度數均大于等于n/2，所以存在H回路，該回路中q個新點恢復成原2q個點，則所代表的q條邊仍在此H回路中注：q不能超過n/212 構造圖G，每個小立方體對應一個點，兩個立方體之間有公共面則對應頂點間有邊設最左上角點為黑色，依據相鄰點不同色的原則給所有點著色，則黑色點有14個，白色點有13個，若所要求路徑存在，則意味著從黑色點開始遍歷這27個點到達白色點，這不可能131）將邊按權值由小到大排序：邊： a23 a35

13、 a15 a13 a34 a45 a24 a12 a25 a14權： 26 27 29 33 34 35 38 42 49 52 2)分支定界： S1: a23 a35 a15 a13 a34 , 非H回路,d (S1)=149;將a34置換為其后的a45, a24，a12，a25，a14，也全都是非H回路； S2: a23 a35 a15 a34 a45, 非H回路,d(S2)=151;將a45置換為其后的a24，a12，a25，a14，也全都是非H回路； S3: a23 a35 a15 a45 a24 , 非H回路,d (S8)=155;將a24置換為其后的a12，a25，a14，也全都是

14、非H回路；S4: a23 a35 a15 a24 a12 , 非H回路,d (S4)=162;S5: a23 a35 a15 a24 a25 , 非H回路,d (S5)=169;S6: a23 a35 a15 a24 a14 , H回路,d0:=172;S7: a23 a35 a15 a12 a25 , 非H回路,d (S7)=173;S8: a23 a35 a13 a34 a45 , 非H回路,d (S8)=155;將a34 , a45置換為其后的數，也全都是非H回路；S9: a23 a35 a34 a45 a24 , 非H回路,d (S9)=160;將a45 , a24置換為其后的數，也全

15、都是非H回路；S10: a23 a35 a45 a24 a12 , 非H回路,d (S10)=168;將a12置換為其后的a25 , a14，也全都是非H回路；S11: a23 a35 a45 a12 a25 , 非H回路,d (S11)=179;將a12 ,a25置換為其后的數，其路長差于d0，故不必考慮；S12: a23 a35 a24 a12 a25, 非H回路,d (S12)=182;將a24 ，a12 ，a25,置換為其后的數，其總長差于d0，故不必考慮； 繼續(xù)下去所得組長度會比S6差，故可終止計算。所以，H回路為S6, 路長為172。14. 這是一個旅行商問題(具體計算略)：(0,

16、0)(2,5)(6,6)(9,3)(8,9)7951017125671215. 這是一個最短路問題(具體計算略)：5+115+116+65+35+38+17+16+15+15+17+35+65+66+35+172V6V3V2V1V5V4329214853V1V2V3V5V42542984516. 29V3V2V6V4V1V5333627343023. 習題三1 因為n個結點的樹的邊有n-1條，故其總度數為 2 (n-1)，故度為1的結點個數為2 (n-1)2n23n3knk .2. 設L是樹T的一條最長路，L中的結點依次為v1, v2 , , vk。因為L中各結點都有邊相連，所以它們的度數均大

17、于或等于1。若deg (v1)>1, 則除了邊(v1, v2)外，還存在邊(v1, v) 。因為樹中不存在回路，故vÏ v1, v2 , , vk ，于是，(v,v1, v2 , , vk)是T的一條新的路，其長度比L更長。這與L是T的最長路矛盾。所以deg (v1)1，類似可證deg (vk)1。4(a) 直接根據圖確定B5B5T可得樹的棵數： (b) 去掉邊(v1, v5)，則直接根據圖確定B5B5T可得不含邊(v1, v5)的樹的棵數：于是，含邊(v1, v5)的樹的棵數為：1017526。(c) 去掉邊(v4, v5)，則直接根據圖確定B5B5T可得不含邊(v1, v5

18、)的樹的棵數：5. (a) 因為(b) 去掉邊(v1, v5)后，有(c) 去掉到v3的其它全部邊(v4, v3)、(v5, v3)后，有10. (1) 余樹為e1, e2, e5, e 8, 重排B5的各列得余樹樹T(2) 由定理3.4.8, 基本割集矩陣為14(a) 這是一個求最優(yōu)二叉樹的問題。各字符出現次數為：s t a e c 空格 3451 1 44481123554451123511244354481123551011235510448180100001111所以最優(yōu)二進制編碼為：e: 1100 c: 1101 s: 111 t: 00 空格：01 a: 10此時字符串的二進制編碼

19、總長度為43 .(b) 去掉空格，類似(a)計算。e4e6e5e3e2e115. 將圖中各邊進行編號得右圖。取參考支撐樹t0= e1, e2, e3, e5 .(1) 因為S e1(t0)= e1, e4, e6 , S e2(t0)= e2, e4, e6 ,S e3(t0)= e3, e6 , S e5(t0)= e5, e6 , 所以Te1= e4, e2, e3, e5, e6, e2, e3, e5= t1, t2,Te2= e1, e4, e3, e5, e1, e6, e3, e5= t3, t4,Te3= e1, e2, e6, e5= t5,Te5= e1, e2, e3,

20、e6= t6,從而T1 t1, t2, t3, t4, t5, t6 .(2) 因為S e2(t1)= e2, e1 , S e3(t1)= e3, e6 , S e5(t1)= e5, e6 ,S e2(t2)= e2, e1 , S e3(t2)= e3, e1, e4 , S e5(t2)= e1, e4, e5 , S e3(t3)= e3, e6 , S e5(t3)= e6, e5 ,S e3(t4)= e3, e2, e4 , S e5(t4)= e2, e4, e5 , S e5(t5)= e5, e3 ,所以S e2(t0) ÇS e2(t1) e2 , S e2(t0) ÇS