圖論與代數(shù)結(jié)構(gòu)第一二三章習(xí)題解答

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

2、向量作為各結(jié)點(diǎn), 如果(a1,a2,a3)中某杯的水倒?jié)M另一杯得到 ( a1, a2, a3 ) , 則由結(jié)點(diǎn)到結(jié)點(diǎn)畫一條有向邊。這樣可得一個(gè)有向圖。本題即為在此圖中找一條由( 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個(gè)人中沒有4個(gè)人相互認(rèn)識(shí)，構(gòu)造圖G，每個(gè)點(diǎn)代表一個(gè)點(diǎn)，兩個(gè)人相互認(rèn)識(shí)則對(duì)應(yīng)的兩個(gè)點(diǎn)

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

4、這兩個(gè)人與v共3個(gè)人相互不認(rèn)識(shí)3） 若每個(gè)點(diǎn)的度數(shù)都為5，則有奇數(shù)個(gè)度數(shù)為奇數(shù)的點(diǎn)，不可能。7. 同構(gòu)。同構(gòu)的雙射如下： 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),則鄰接矩陣為：關(guān)聯(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). 習(xí)題二1. 用數(shù)學(xué)歸納法。k=1時(shí)，由定理知結(jié)論成立。設(shè)對(duì)于k命題成立。對(duì)于k+1情形，設(shè)前k個(gè)連通支的結(jié)點(diǎn)總個(gè)數(shù)為n1, 則由歸納假設(shè)，前k個(gè)連通支的總邊數(shù)m1<= ( n1k+1)( n1k)/2。最后一個(gè)連通支的結(jié)點(diǎn)個(gè)數(shù)為nn1, 其邊數(shù)m2<= ( nn1)( nn11)/2，所以，G的總邊數(shù)m= m1+ m2<= ( n1k+1)( n1k)/2 + ( nn1)( nn11)/2n1=n1時(shí)，m<= ( (n-1)k+1)( (n-1)k)/2 +0= ( (nk)( (nk1)/2, 命題成立。n1= n2時(shí)，由

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

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

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

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

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

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

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

13、 a15 a13 a34 a45 a24 a12 a25 a14權(quán)： 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置換為其后的數(shù)，也全都是非H回路；S9: a23 a35 a34 a45 a24 , 非H回路,d (S9)=160;將a45 , a24置換為其后的數(shù)，也全

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置換為其后的數(shù)，其路長(zhǎng)差于d0，故不必考慮；S12: a23 a35 a24 a12 a25, 非H回路,d (S12)=182;將a24 ，a12 ，a25,置換為其后的數(shù)，其總長(zhǎng)差于d0，故不必考慮； 繼續(xù)下去所得組長(zhǎng)度會(huì)比S6差，故可終止計(jì)算。所以，H回路為S6, 路長(zhǎng)為172。14. 這是一個(gè)旅行商問題(具體計(jì)算略)：(0,

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

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

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

19、總長(zhǎng)度為43 .(b) 去掉空格，類似(a)計(jì)算。e4e6e5e3e2e115. 將圖中各邊進(jìn)行編號(hào)得右圖。取參考支撐樹t0= e1, e2, e3, e5 .(1) 因?yàn)镾 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) 因?yàn)镾 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