《圖論與代數(shù)結(jié)構(gòu)》(戴一奇,清華大學(xué)出版社)習(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ì)矛盾。2. 若存在孤立點(diǎn)，則m不超過(guò)K邊的邊數(shù)，故m (nl)(n2)/2,與題設(shè)矛盾。記磴為結(jié)點(diǎn)兒的正度數(shù)，石為結(jié)點(diǎn)叫的負(fù)度數(shù)，則onnnn3-Z<2 二仇-1)-町'二如-1)?-2(”-1)2X吃亍，i-1i-1i“ i>l因?yàn)槠蚨?C： = (-1)/2,所以 2ai+ 2 =Sa2°il

2、i-1i-14.用向量(alza2/a3)表示三個(gè)量杯中水的量，其中a：為第i杯中 水的量,i = 1,2,3.以滿足a!+a2+a3= 8 (alza2/a3為非負(fù)整數(shù))的所有向量作為各 結(jié)點(diǎn)，如果&屜冇)中某杯的水倒?jié)M另一杯得到(, 則由結(jié)點(diǎn)到結(jié)點(diǎn)畫(huà)一條有向邊。這樣可得一個(gè)有向圖。本題即為在此圖中找一條由(8, 0, 0 )到(4, 4, 0 )的一條有向路，以下即是這樣的一條:(8,0,0) (5,0,3) > (5,3,0) > (2,3,3) (7, 0,1)5.可以。 (7, 1,0) (4,4,0)7. 同構(gòu)。同構(gòu)的雙射如下:VViv2v3v4v5v6f(v)

3、bacedf8記 61=(V1M), 02= ( V1ZV4), 63=(V3M), 64=(V2N5), 65= (V6/V3)/二(V6,V4), e7=(V5M), e8= (v3/v4)/e9 = Mm),0 10 10 0 0 010 0 10 0 0 00 0 10鄰接矩陣0 1 10 01 00 00 00 00 011 -1 000 00 -1-10 0 10000000 10-10-1100-1 0 00-10-1000 0 -1001000關(guān)聯(lián)矩陣為：11001邊列表為：A= (3,2,66536), B= (2,4,1,53,4,3,4,1).正向表為：A= (13466

4、/10), B= (2,4,5,14334,1).1.用數(shù)學(xué)歸納法。k=l時(shí)，由定理知結(jié)論成立。設(shè)對(duì)于k命 題成立。對(duì)于k+1情形，設(shè)前k個(gè)連通支的結(jié)點(diǎn)總個(gè)數(shù)為nlz則由歸納 假設(shè)，前k個(gè)連通支的總邊數(shù)mi<= (nik+l)( nxk)/2o最后一 個(gè)連通支的結(jié)點(diǎn)個(gè)數(shù)為n-g其邊數(shù)m2<= ( n nj( n ni1)/2,所以，G的總邊數(shù)m= rrh+ m2<= ( g k+l)( nx k)/2 + ( n nj( n n】一1)/2ni=n1 時(shí)，m<= (n-l)k+l)( (n-1)k)/2 +0= (nk)( (nk 一 1)/2,命題成立。m<二n

5、2時(shí)，由于gv二k,故m<= (n2) k+l)( gk)/2 + ( nni)( n k1)/2 =(n k)( n k1)/2 ,命題成立。2若G連通，罌命題已成立；看則，G至少有兩個(gè)連通支。任取結(jié)點(diǎn)vn v2g,若邊(5 V2)不在g,則vn V2在G的同一個(gè)連通妾(堆設(shè)為G】)中。設(shè)G2是G的另一連通支，取 V3gG2/則V1TV3TV2是 中Vi到V2的一條道路,即結(jié)點(diǎn)5 V2 在中有路相通。由Vi, V2的任意性，知 連通。3. 設(shè)JL2是連通圖G的兩條最長(zhǎng)路，且SS無(wú)公共結(jié)點(diǎn)。設(shè) 5丄2的長(zhǎng)度(邊數(shù))為P-由于G是連通的，故S上必有一結(jié)點(diǎn)與1_2上一結(jié)點(diǎn)巾 有道路匕相通。結(jié)

6、點(diǎn)V】將L分為兩部分，其中一部分的長(zhǎng)度>p/2,記此 部分道路為L(zhǎng)?。同樣，結(jié)點(diǎn)V2將L2分為兩部分，其中一部分S 的長(zhǎng)度 p/2。這樣，L3 + C + L4就是G的一條新的道路，且其長(zhǎng)度大于p,這 與G的最長(zhǎng)路（LJ的長(zhǎng)度是p的假設(shè)矛盾。4. 對(duì)結(jié)點(diǎn)數(shù)n作歸納法。（1）n= 4時(shí)m5.若有結(jié)點(diǎn)的度W1,則剩下的三結(jié)點(diǎn)的度數(shù) 之和M4,不可能。于是每個(gè)結(jié)點(diǎn)的度$2,從而存在一個(gè)回路。若此回路為一個(gè)三角形，則還有此回路外的一結(jié)點(diǎn)，它與此 回路中的結(jié)點(diǎn)至少有二條邊，從而構(gòu)成一個(gè)新的含全部四個(gè)結(jié)點(diǎn) 的回路，原來(lái)三角形中的一邊（不在新回路中）即是新回路的一 條弦。若此回路為含全部四個(gè)結(jié)點(diǎn)的初等

7、回路，則至少還有一邊不 在回路上，此邊就是該回路的一條弦。（2）設(shè)nl情形命題已成立。對(duì)于n情形：若有結(jié)點(diǎn)的度W1,則去掉此結(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,由書(shū)上例2.1. 3的結(jié)果知命題成立。6.問(wèn)題可化為求下列紅線表示的圖是否存在一條歐拉道路的8. 由推論2.4.1,只需驗(yàn)證G的任意一對(duì)結(jié)點(diǎn)的度數(shù)之和大于 或等于n即可。若存在結(jié)點(diǎn)5 V2滿足deg(vi)+deg(v2)<n/貝！|G-vlz v2的邊數(shù)v二 Kn-2 的邊數(shù)二(n-2)(n-

8、3)/2 .另一方面，由題設(shè)知G vX/ v2的邊數(shù)=m ( deg(vx)+deg(v2) >(n-l)(n-2)/2+2-n= (n-2)(n-3)/2,與上式矛盾。131）將邊按權(quán)值由小到大排序:邊：a23 65 31531334345243123 25a丄4權(quán)：26 27 293334 353842 49522）分支定界：S1： 23 335 315 31334 /非 H 回路,d (Sl)=149;將a34置換為其后的a45, a24, a12, a25> a14»也全都是非H回路；S2： 82335a 1534a45,非 H 回路,d(S2)=151;將a45

9、置換為其后的a?" an，a25，a，也全都是非H路；S3: a23a35a 15a 45a24/ 非 H 回路,d (S8)=155;將324置換為其后的au，a25> a14>也全都是非H回路;S4: a233531524a12/ 非 H 回路,d(S4)“62;S5：巧335a 1524a25/ 非 H 回路,d(S5)“69;S6: 82335a 1524a14/H 回路,d0：=172;S7: 32335a 15312a25/ 非 H 回路,d(S7)=173;S8： 8233531334a45,非 H 回路,d (S8)=155;將334山45置換為其后的數(shù)，

10、也全都是非H回路；S9: a2335a34345a24/ 非 H 回路,d (S9)=160;將a45 z a24置換為其后的數(shù)，也全都是非H回路;SlOi 823835845324312 / H 回路,d(S10)=16&將a】2置換為其后的a25/a14,也全都是非H回路；Sil* 82383534531225 /非 H 回路,d(Sll)=179j312 用25 M.換為其后的數(shù),其路長(zhǎng)差于6,故不必考慮;S12： 23 65324 312 325；非 H 回路,d (S12)=182;將a24 , a12 , am置換為其后的數(shù)，其總長(zhǎng)差于d0,故不必考慮；繼續(xù)下去所得組長(zhǎng)度會(huì)

11、比S6差，故可終止計(jì)算。所以，H回路為S6,路長(zhǎng)為172。這是一個(gè)旅行商問(wèn)題（具體計(jì)算略）:這是一個(gè)最短路問(wèn)題（具體計(jì)算略）:5+17an23.習(xí)題三1.因?yàn)閚個(gè)結(jié)點(diǎn)的樹(shù)的邊有n-l條，個(gè)數(shù)為故其總度數(shù)為2 (n-l),故度為1的結(jié)點(diǎn)2 (nl) 2n23n3km 2.設(shè)L是樹(shù)T的一條最長(zhǎng)路丄中的結(jié)點(diǎn)依次為V】，v :vko因?yàn)長(zhǎng)屮各結(jié)點(diǎn)都有邊相連，所以它們的度數(shù)均大于或等 于1。若deg (Vi)>l,則除了邊(vi, V2)外，還存在邊(Vi, v，) o 因?yàn)闃?shù)中不存在回路，故v'住Vi, V2,，vk,于是，(V , Vi, v2 ,，vj是T的一條新的路，其長(zhǎng)度比L更長(zhǎng)

12、。這與L是T 的最長(zhǎng)路矛盾。所以 deg (vi)=l,類似可證 deg (vj=l。4. (a)直接根據(jù)圖確定B5BJ可得樹(shù)的棵數(shù):3-100-2= 101.-104-1-14=60=60(b)去掉邊( V5),則直接根據(jù)圖確定&噱可得不含邊(Vi, V5)的樹(shù)的棵數(shù):7-10-1-14-100-14-2-10-74于是，含邊(5V5)的樹(shù)的棵數(shù)為：101 75=26。=60=60(c)去掉邊(J V則直接根據(jù)圖確定BsBj可得不含邊仏v5)的樹(shù)的棵數(shù):=60=6034det(B5B)= -1-14-100-14-2-10-23=605. (a)因?yàn)?8.=8.-1000001-1勵(lì)

13、=00-100-100-1000000-1d =00-100-1001-10000001-1-1000-110-1-1100110-10000000-1-1000-100-1-100000因此以氣為根的根樹(shù)的個(gè)數(shù)為200-13-1det（B；B）=1 10-13-1-1= 24.-1-10 0（b）去掉邊（Vi, V5）后，有0 11-10 0 00-10 0 1 -1 -11 0 0 0 - 1 1 00 0 -1 1 0 0 1-1 0 0 0 -1 0 0 00-10-10 00 0 -1 -10-10000-1100一 1000 -1 00000因此以H為根且不含邊（兒5）的根樹(shù)的個(gè)數(shù)

14、為0 -1-1 -13-1=8.(c)去掉到V3的其它全部邊(V" V3)、(v5, V3)后，有1 =0 -1-1 000-100-1000-1011-10000-100-10000-1-10 00100-1-1101-10 00000-1-1000因此以耳為根且含邊(兒3)的根樹(shù)的個(gè)數(shù)為-10 01 0-1 30 0-10=9.-1210. (1)余樹(shù)為% e2, e5, e 8,重排的各列得110010100 10000 1=00100100100111003=(BnBn).余樹(shù)-1 10則Bn =1 010 100 0由定理344,-1Cfl2 = -Br=-100基本回路矩

15、陣為 0001100_0,B2 =0011 100樹(shù)T100 '0010 _0-10110-110-1000-100-1100-1-1001一1110-1-1-10000一13C4SC7-1-11 100-1 -10-10 0100 -1(2)由定理3.4.8,基木割集矩陣為1)=001101008-100v7000114- (a)這是一個(gè)求最優(yōu)二叉樹(shù)的問(wèn)題。各字符出現(xiàn)次數(shù)為:a e c空格2所以最優(yōu)二進(jìn)制編碼為：e: 1100 c： 1101 s： 111 t： 00 空格：01 a： 10此時(shí)字符串的二進(jìn)制編碼總長(zhǎng)度為43(b)去掉空格，類似(R計(jì)算。15.將圖中各邊進(jìn)行編號(hào)得右圖

16、。取參考支撐樹(shù)to= ei, e2, e3, I大| 為 S .1 (to) = Cl, 04, & , S §to)二S *3 (to) = Cs, & , S «5 (to) = C5, & ,所以T*1= e4,62,C3,C5,ce,e2, C3,c = ti,t2),T"2= Ci,563,65,ci, 63,& = ts,tj,T*3= ei, 62, C6, 65= ts,T*5= e2, e3, & = t«,從而 T= tl, t2, t3,七4, ts, te(2)因?yàn)?S «2(tl

17、) = ©2, Cl , S «3 (tl)= 03, 6s , S5 (tl) = C5, C6 ,S 2(t2)= C2, Cl , S 3(t2)= 63, Cl, 64 > S «5 (t2)= Cl,e4, es ,S «3 (ts)= C3, S .5 (ts) = 6, C5 ,S «3(t4)= C3, 62, 64 , S «5 (tO = C2, C4, C5 ,S 右(ts) = 65,3 ,所以S .2 (to) CS «2(tl) = e2) , S 92 (to) CS 2(t2)= 62,

18、 從而 rle2=0；S «3 (to) rS .3 (tl) = e3, & , S «3 (to) (S .3 (t2)= 63,從而 T*1 *3 = e4,跆 Ce, & = t?;S «5 (to) r>S <5 (ti) = C5, a , S»5 (to) r>S 話(t2)= c ,S «3 (to) CS .3 (t3)= 63, & , S <3 (to) CS «3 (tj = 63 , 從而 T*2 = 61, 64, Cfi, es = te；S «5

19、 (to) CS t5 (七3)= &, & , S «5 (to) CS t5 (tj = 65 ,從而 T*2 = Ci, e4, 63, & = tio):S (to) cS .5 (t5)= C5,從而 T*3 "=0；于是 可以驗(yàn)證 T112 t3=T113 t5=T<213 e5=0,所以 T 3 = 0.最后，由以上計(jì)算可知，全部生成樹(shù)為 to , tb t2, t3,tg, tio 16.用Kruskal算法。先將權(quán)排序，而后按權(quán)由小到大選邊8-1條（構(gòu)成回路時(shí)所選邊不放入），可得一棵最小生成樹(shù)（總權(quán)為22）：習(xí)題!1.因?yàn)?d

20、=m-n+2<l2,所以 m-n<10.如果命題不成立，則每個(gè)域的邊界數(shù)M5,于是有5dW2m。利用d= m-n+2,得3m+105n 結(jié)合 m-n<10,可得 m<3n/2.另一方面，由于 3n W S d(Vj) W 2mz 知 m3n/2, 矛盾。2.設(shè)G是一個(gè)結(jié)點(diǎn)個(gè)數(shù)34的極大平面圖，但G中至少有一個(gè)結(jié)點(diǎn)v的度W2由于G是一個(gè)平面圖,及其關(guān)聯(lián)的全部邊(至多兩條)在G-v中某個(gè)區(qū)域D中。因?yàn)镚-v是一個(gè)簡(jiǎn)單圖，故沒(méi)有重邊和環(huán)，因此區(qū)域D至少有三條邊。如果D是一個(gè)內(nèi)部域，則D的邊界上必有二亍、 結(jié)點(diǎn)與v可用一條不與其它邊相交的邊相連，,惹與幸 y 極大平面圖的題設(shè)相

21、矛盾。如果D是一個(gè)外部域，同樣可以在D的邊界上找一結(jié)點(diǎn)與V用一條不與其它邊相交的邊相連，仍與G是 極大平面圖的題設(shè)相矛盾。以上矛盾說(shuō)明G的每個(gè)結(jié)點(diǎn)的度至少是3。3.用反證法。若G和均為可平面的，設(shè)它們的邊數(shù)分別是則有rriiW3n6, rri2W3n6,于是 mi+ m26n-12,即 n(n-l)/26n-12# 其中 nll. 考慮函數(shù) f(x)=x(x-l)/2-6x+12# xll因?yàn)?f(ll)=l>0, r(x)>O(x>ll)/ 故 f(x)在也+oo范圍內(nèi)嚴(yán)格遞增，所以ffnO.nll.這與剛得到的不等式n(n-l)/26n-12 相矛盾。13.因?yàn)閳D中含有一

22、個(gè)矗子圖，故其色數(shù)至少為3。又因?yàn)橛萌N顏色可以為此圖結(jié)點(diǎn)著色，故其色數(shù)等于3。由于所以色數(shù)多項(xiàng)式f(G, t)=f(K5/t)+3 f(K4/t)+f(K3/t)=t(t-l) (t-2) (t-3) (t-4)+3 t(t-l) (t-2) (t-3)+ t(t-l)(t-2)=t(t-l) (t-2) (t2-4t+4).14.顯然中心點(diǎn)的顏色與回路上各點(diǎn)的均不同，而回路上 結(jié)點(diǎn)數(shù)為偶數(shù)時(shí)色數(shù)為2,結(jié)點(diǎn)數(shù)為奇數(shù)時(shí)色數(shù)為3,故整個(gè)圖 Wn當(dāng)n為為偶數(shù)時(shí)色數(shù)為1+3,結(jié)點(diǎn)數(shù)為奇數(shù)時(shí)色數(shù)為"2。因?yàn)閷?duì)于回路G,已知其色數(shù)多項(xiàng)式f(Cn/ t)=(t-l)n+(-l)n(t-l),所以

23、f(G, t)=t f(C“ tl)=t(t2嚴(yán)+(£嚴(yán)治2)14. G當(dāng)均為偶數(shù)時(shí)色數(shù)為2,其它情形時(shí)色數(shù)為3。因?yàn)?f(C“ t)= f(G, t)+ f(G； t),其中&為下圖：根據(jù)色數(shù)多項(xiàng)式的定義，直接可知f(G： t)=max f(Cm/1), f(Cn/1)= f(Ck/1),其中 k=maxm/n/ 故f(G, t)= f( j t) - f(G； t)習(xí)題五1. 一個(gè)最大匹配是:(xi,y5), (x2/yi), (x3/y2), (x4/y3), (x 胡d2. 這可以看成是以下二分圖是否存在完美匹配的問(wèn)題：abe紅線表示的是一個(gè)完美匹配。所以:字符串be

24、可以用b表示，字符串ed可以用e表示，字符串a(chǎn)c可以用c表示，字符串bd可以用d表示，字符串a(chǎn)be可以用a表示。8.每行中用此行的最大數(shù)減去此行的每一個(gè)數(shù)，得到一個(gè)等價(jià)的最小成本問(wèn)題:3 4 3 5 3 0_3 4 2 2 （V） 0_3 7 4 4 4 037314 3 15 7 0每列減去列最小數(shù)4 3（0）2 4 00 4 5 3 8 91u->0 4 4 QOJ 5 91 0 4 5 3 21 （0） 3 2 0 20 3 4 5 3 2 ©33202由于可選出每行每列恰有一個(gè)零元素的方案，故此方案即 為最優(yōu)方案.9. 每行中減去此行的最小數(shù):212025'0）11025'4 0 3 3 3 72（0）2 3 3 73 4 6 2 0 7每列減去列最小數(shù)1 4 5 2（0）79 5 4 61 07 5 3 61 （。4 51 0 2 32 5（0）0 2 35 21 0 2 3 3 2 0（0）2 3由于可選出每行每列恰有一個(gè)零元素的方案，故此方案即 為最優(yōu)方案.11-增加一個(gè)虛擬總發(fā)點(diǎn)S和一個(gè)虛擬總收點(diǎn)和t,則問(wèn)題變?yōu)閼?yīng)用Ford-Fulkerson算法，可得一個(gè)最大流(如上圖)，最大 流量為21.在最后圖中，可得到標(biāo)號(hào)的全部結(jié)點(diǎn)為s,s“S2,b,其 余結(jié)點(diǎn)