《图论与代数结构》(戴一奇,清华大学出版社)习题解答

1、习题一1. 一个工厂为一结点；若两个工厂之间有业务联系，则此两 点之间用边相联；这样就得到一个无向图。若每点的度数为3, 则总度数为27,与图的总度数总是偶数的性质矛盾。若仅有四 个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为 奇数，仍与图的总度数总是偶数的性质矛盾。2. 若存在孤立点，则m不超过K边的边数，故m (nl)(n2)/2,与题设矛盾。记磴为结点儿的正度数，石为结点叫的负度数，则onnnn3-Z<2 二仇-1)-町'二如-1)?-2(”-1)2X吃亍，i-1i-1i“ i>l因为乞叮=C： = (-1)/2,所以 2ai+ 2 =Sa2°il

2、i-1i-14.用向量(alza2/a3)表示三个量杯中水的量，其中a：为第i杯中 水的量,i = 1,2,3.以满足a!+a2+a3= 8 (alza2/a3为非负整数)的所有向量作为各 结点，如果&屜冇)中某杯的水倒满另一杯得到(, 则由结点到结点画一条有向边。这样可得一个有向图。本题即为在此图中找一条由(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. 同构。同构的双射如下: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关联矩阵为：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.用数学归纳法。k=l时，由定理知结论成立。设对于k命 题成立。对于k+1情形，设前k个连通支的结点总个数为nlz则由归纳 假设，前k个连通支的总边数mi<= (nik+l)( nxk)/2o最后一 个连通支的结点个数为n-g其边数m2<= ( n nj( n ni1)/2,所以，G的总边数m= rrh+ m2<= ( g k+l)( nx k)/2 + ( n nj( n n】一1)/2ni=n1 时，m<= (n-l)k+l)( (n-1)k)/2 +0= (nk)( (nk 一 1)/2,命题成立。m<二n

5、2时，由于gv二k,故m<= (n2) k+l)( gk)/2 + ( nni)( n k1)/2 =(n k)( n k1)/2 ,命题成立。2若G连通，罂命题已成立；看则，G至少有两个连通支。任取结点vn v2g,若边(5 V2)不在g,则vn V2在G的同一个连通妾(堆设为G】)中。设G2是G的另一连通支，取 V3gG2/则V1TV3TV2是 中Vi到V2的一条道路,即结点5 V2 在中有路相通。由Vi, V2的任意性，知 连通。3. 设JL2是连通图G的两条最长路，且SS无公共结点。设 5丄2的长度(边数)为P-由于G是连通的，故S上必有一结点与1_2上一结点巾 有道路匕相通。结

6、点V】将L分为两部分，其中一部分的长度>p/2,记此 部分道路为L?。同样，结点V2将L2分为两部分，其中一部分S 的长度 p/2。这样，L3 + C + L4就是G的一条新的道路，且其长度大于p,这 与G的最长路（LJ的长度是p的假设矛盾。4. 对结点数n作归纳法。（1）n= 4时m5.若有结点的度W1,则剩下的三结点的度数 之和M4,不可能。于是每个结点的度$2,从而存在一个回路。若此回路为一个三角形，则还有此回路外的一结点，它与此 回路中的结点至少有二条边，从而构成一个新的含全部四个结点 的回路，原来三角形中的一边（不在新回路中）即是新回路的一 条弦。若此回路为含全部四个结点的初等

7、回路，则至少还有一边不 在回路上，此边就是该回路的一条弦。（2）设nl情形命题已成立。对于n情形：若有结点的度W1,则去掉此结点及关联边后，依归纳假设命 题成立。若有结点v的度二2,设v关联的两结点为s,t,则去掉结点v及 关联边、将s,t合并为一个结点后，依归纳假设命题成立。若每个结点的度$3,由书上例2.1. 3的结果知命题成立。6.问题可化为求下列红线表示的图是否存在一条欧拉道路的8. 由推论2.4.1,只需验证G的任意一对结点的度数之和大于 或等于n即可。若存在结点5 V2满足deg(vi)+deg(v2)<n/贝！|G-vlz v2的边数v二 Kn-2 的边数二(n-2)(n-

8、3)/2 .另一方面，由题设知G vX/ v2的边数=m ( deg(vx)+deg(v2) >(n-l)(n-2)/2+2-n= (n-2)(n-3)/2,与上式矛盾。131）将边按权值由小到大排序:边：a23 65 31531334345243123 25a丄4权：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置换为其后的数，

10、也全都是非H回路；S9: a2335a34345a24/ 非 H 回路,d (S9)=160;将a45 z a24置换为其后的数，也全都是非H回路;SlOi 823835845324312 / H 回路,d(S10)=16&将a】2置换为其后的a25/a14,也全都是非H回路；Sil* 82383534531225 /非 H 回路,d(Sll)=179j312 用25 M.换为其后的数,其路长差于6,故不必考虑;S12： 23 65324 312 325；非 H 回路,d (S12)=182;将a24 , a12 , am置换为其后的数，其总长差于d0,故不必考虑；继续下去所得组长度会

11、比S6差，故可终止计算。所以，H回路为S6,路长为172。这是一个旅行商问题（具体计算略）:这是一个最短路问题（具体计算略）:5+17an23.习题三1.因为n个结点的树的边有n-l条，个数为故其总度数为2 (n-l),故度为1的结点2 (nl) 2n23n3km 2.设L是树T的一条最长路丄中的结点依次为V】，v :vko因为L屮各结点都有边相连，所以它们的度数均大于或等 于1。若deg (Vi)>l,则除了边(vi, V2)外，还存在边(Vi, v，) o 因为树中不存在回路，故v'住Vi, V2,，vk,于是，(V , Vi, v2 ,，vj是T的一条新的路，其长度比L更长

12、。这与L是T 的最长路矛盾。所以 deg (vi)=l,类似可证 deg (vj=l。4. (a)直接根据图确定B5BJ可得树的棵数:3-100-2= 101.-104-1-14=60=60(b)去掉边( V5),则直接根据图确定&噱可得不含边(Vi, V5)的树的棵数:7-10-1-14-100-14-2-10-74于是，含边(5V5)的树的棵数为：101 75=26。=60=60(c)去掉边(J V则直接根据图确定BsBj可得不含边仏v5)的树的棵数:=60=6034det(B5B)= -1-14-100-14-2-10-23=605. (a)因为=8.=8.-1000001-1励

13、=00-100-100-1000000-1d =00-100-1001-10000001-1-1000-110-1-1100110-10000000-1-1000-100-1-100000因此以气为根的根树的个数为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）的根树的个数

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)的根树的个数为-10 01 0-1 30 0-10=9.-1210. (1)余树为% e2, e5, e 8,重排的各列得110010100 10000 1=00100100100111003=(BnBn).余树-1 10则Bn =1 010 100 0由定理344,-1Cfl2 = -Br=-100基本回路矩

15、阵为 0001100_0,B2 =0011 100树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)这是一个求最优二叉树的问题。各字符出现次数为:a e c空格2所以最优二进制编码为：e: 1100 c： 1101 s： 111 t： 00 空格：01 a： 10此时字符串的二进制编码总长度为43(b)去掉空格，类似(R计算。15.将图中各边进行编号得右图

16、。取参考支撑树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)因为 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；于是 可以验证 T112 t3=T113 t5=T<213 e5=0,所以 T 3 = 0.最后，由以上计算可知，全部生成树为 to , tb t2, t3,tg, tio 16.用Kruskal算法。先将权排序，而后按权由小到大选边8-1条（构成回路时所选边不放入），可得一棵最小生成树（总权为22）：习题!1.因为 d

20、=m-n+2<l2,所以 m-n<10.如果命题不成立，则每个域的边界数M5,于是有5dW2m。利用d= m-n+2,得3m+105n 结合 m-n<10,可得 m<3n/2.另一方面，由于 3n W S d(Vj) W 2mz 知 m3n/2, 矛盾。2.设G是一个结点个数34的极大平面图，但G中至少有一个结点v的度W2由于G是一个平面图,及其关联的全部边(至多两条)在G-v中某个区域D中。因为G-v是一个简单图，故没有重边和环，因此区域D至少有三条边。如果D是一个内部域，则D的边界上必有二亍、 结点与v可用一条不与其它边相交的边相连，,惹与幸 y 极大平面图的题设相

21、矛盾。如果D是一个外部域，同样可以在D的边界上找一结点与V用一条不与其它边相交的边相连，仍与G是 极大平面图的题设相矛盾。以上矛盾说明G的每个结点的度至少是3。3.用反证法。若G和均为可平面的，设它们的边数分别是则有rriiW3n6, rri2W3n6,于是 mi+ m26n-12,即 n(n-l)/26n-12# 其中 nll. 考虑函数 f(x)=x(x-l)/2-6x+12# xll因为 f(ll)=l>0, r(x)>O(x>ll)/ 故 f(x)在也+oo范围内严格递增，所以ffnO.nll.这与刚得到的不等式n(n-l)/26n-12 相矛盾。13.因为图中含有一

22、个矗子图，故其色数至少为3。又因为用三种颜色可以为此图结点着色，故其色数等于3。由于所以色数多项式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.显然中心点的颜色与回路上各点的均不同，而回路上 结点数为偶数时色数为2,结点数为奇数时色数为3,故整个图 Wn当n为为偶数时色数为1+3,结点数为奇数时色数为"2。因为对于回路G,已知其色数多项式f(Cn/ t)=(t-l)n+(-l)n(t-l),所以

23、f(G, t)=t f(C“ tl)=t(t2严+(£严治2)14. G当均为偶数时色数为2,其它情形时色数为3。因为 f(C“ t)= f(G, t)+ f(G； t),其中&为下图：根据色数多项式的定义，直接可知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)习题五1. 一个最大匹配是:(xi,y5), (x2/yi), (x3/y2), (x4/y3), (x 胡d2. 这可以看成是以下二分图是否存在完美匹配的问题：abe红线表示的是一个完美匹配。所以:字符串be

24、可以用b表示，字符串ed可以用e表示，字符串ac可以用c表示，字符串bd可以用d表示，字符串abe可以用a表示。8.每行中用此行的最大数减去此行的每一个数，得到一个等价的最小成本问题:3 4 3 5 3 0_3 4 2 2 （V） 0_3 7 4 4 4 037314 3 15 7 0每列减去列最小数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由于可选出每行每列恰有一个零元素的方案，故此方案即 为最优方案.9. 每行中减去此行的最小数:212025'0）11025'4 0 3 3 3 72（0）2 3 3 73 4 6 2 0 7每列减去列最小数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由于可选出每行每列恰有一个零元素的方案，故此方案即 为最优方案.11-增加一个虚拟总发点S和一个虚拟总收点和t,则问题变为应用Ford-Fulkerson算法，可得一个最大流(如上图)，最大 流量为21.在最后图中，可得到标号的全部结点为s,s“S2,b,其 余结点