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

习题一

1. 一个工厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。若每点的度数为3，则总度数为27，与图的总度数总是偶数的性质矛盾。若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。 2. 若存在孤立点，则m不超过Kn-1的边数, 故 m <= (n-1)(n-2)/2, 与题设矛盾。 记a 为结点v的正度数，a－为结点v的负度数，则

iiii

3. a　　　

4. 用向量(a1,a2,a3)表示三个量杯中水的量, 其中ai为第i杯中水的量, i = 1,2,3.

以满足a1+a2+a3 = 8 (a1,a2,a3为非负整数)的所有向量作为各结点, 如果(a1,a2,a3)中某杯的水倒满另一杯得到 ( a’1, a’2, a’3 ) , 则由结点到结点画一条有向边。这样可得一个有向图。

本题即为在此图中找一条由( 8, 0, 0 )到( 4, 4, 0 )的一条有向

i 1

nn

2

i

2

[(n 1) a] n(n 1) 2(n 1) a＋ a－i，

2

i

2

－ i

i 1

i 1

i 1

2n

n

2i

2

a－i。i 1n

n

n

n

因为　　 a C n(n 1)/2，　所以　　 a

－

ii 1

i 1

路，以下即是这样的一条：

5. 可以。

7. 同构。同构的双射如下：

v f (v)

V1 b

V2 a

V3 c

V4 e

V5 d

V6 f

( 8, 0, 0 )

( 5, 0, 3 ) (7, 0, 1 )

( 5, 3, 0 ) ( 7, 1, 0 )

( 2, 3, 3 ) ( 4, 1, 3 )

( 2, 5, 1 ) ( 4, 4, 0 )

8. 记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), 则

010100

1

1 100000

000010 10010000 10

0100

0010 10 11 000000 ,

0 1000 10 11000

邻接矩阵为：

00 101 1 0 0

000 10010 0关联矩阵为：000

1100

边列表为：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= (2,4,5,1,4,3,3,4,1).

习题二

1. 用数学归纳法。k=1时，由定理知结论成立。设对于k命题成立。

对于k+1情形，设前k个连通支的结点总个数为n1, 则由归纳假设，前k个连通支的总边数m1<= ( n1－k+1)( n1－k)/2。最后一个连通支的结点个数为n－n1, 其边数

m2<= ( n－n1)( n－n1－1)/2，

1 0 0 0 0 1

所以，G的总边数

m= m1+ m2<= ( n1－k+1)( n1－k)/2 + ( n－n1)( n－n1－1)/2

n1=n－1时，m<= ( (n-1)－k+1)( (n-1)－k)/2 +0= ( (n－k)( (n－k－1)/2, 命题成立。

n1＜= n－2时，由于 n1<=k, 故

m<= ( (n－2)－k+1)( n1－k)/2 + ( n－n1)( n－k－1)/2＝( n－k)( n－k－1)/2 , 命题成立。

2．若G连通， G至少有两个连通支。

G

任取结点v1, v2 ，若边(v1, v2)不在 则v, v在G 12G1）中。设G2是G的另一连通支，取G v3 G2, 则v1 v3 v2 是 中v1到v2的一条道路，即结点v1, v2在 中有路相通。

由v1, v2的任意性，知 连通。

3．设L1,L2是连通图G的两条最长路，且L1,L2无公共结点。设L1,L2的长度(边数)为p.

由于G是连通的，故L1上必有一结点v1与L2上一结点v2有道路L’相通。

结点v1将L1分为两部分，其中一部分的长度 p/2 , 记此

部分道路为L3。同样，结点v2将L2分为两部分，其中一部分L4的长度 p/2 。

这样，L3＋L’＋L4就是G的一条新的道路，且其长度大于p, 这与G的最长路(L1)的长度是p的假设矛盾。

4. 对结点数n作归纳法。

（1）n= 4时m≥5. 若有结点的度≤1, 则剩下的三结点的度数之和≥4，不可能。于是每个结点的度≥2，从而存在一个回路。

若此回路为一个三角形，则还有此回路外的一结点，它与此回路中的结点至少有二条边，从而构成一个新的含全部四个结点的回路，原来三角形中的一边（不在新回路中）即是新回路的一条弦。

若此回路为含全部四个结点的初等回路，则至少还有一边不在回路上，此边就是该回路的一条弦。

（2）设n-1情形命题已成立。 对于n情形：

若有结点的度≤1, 则去掉此结点及关联边后，依归纳假设命题成立。

若有结点v的度=2, 设v关联的两结点为s,t，则去掉结点v及关联边、将s,t合并为一个结点后，依归纳假设命题成立。 若每个结点的度≥3，由书上例2.1.3的结果知命题成立。

6．问题可化为求下列红线表示的图是否存在一条欧拉道路的问题：存在欧拉道路！

8．由推论2.4.1, 只需验证G的任意一对结点的度数之和大于或等于n即可。

若存在结点v1, v2满足 deg(v1)+deg(v2)<n, 则

G－{v1, v2} 的边数<= Kn-2的边数= (n-2)(n-3)/2 .

另一方面，由题设知

G－{ v1, v2} 的边数＝m－（deg(v1)+deg(v2)）＞[(n-1)(n-2)/2+2]－

n= (n-2)(n-3)/2 ,

与上式矛盾。

13．1）将边按权值由小到大排序：

边： a23 a35 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，也全都是非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置换为其后的数，也全都是非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，故不必考虑；

继续下去所得组长度会比S6差，故可终止计算。 所以，H回路为S6, 路长为172。

14. 这是一个旅行商问题(具体计算略)： (2,5)

(0,0)

(6,6)

7

15. 这是一个最短路问题(具体计算略)： 16.

6+6

5+17

V2

V1

V3

V6

V3

V3

V2

23.

习题三

1．

因为n个结点的树

的边有n-1条，故其总度数为 2 (n-1)，故度为1的结点个数为

2 (n-1)－2n2－3n3－……－knk .

2. 设L是树T的一条最长路，L中的结点依次为 v1, v2 , …,

vk。因为L中各结点都有边相连，所以它们的度数均大于或等于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可得树的棵数：

3

1

det(B5B5T)

0 1

14 10

0 14 2

10

101. 24

(b) 去掉边(v1, v5)，则直接根据图确定B5B5T可得不含边(v1, v5)的树的棵数：

2 10 1

14 10

0 14 2

10 24

T

det(B5B5)

75,

于是，含边(v1, v5)的树的棵数为：101－75＝26。

(c) 去掉边(v4, v5)，则直接根据图确定B5B5T可得不含边(v1, v5)的树的棵数：

3

det(B5B)

T

5

14 10

0 14 2

10 23 60

10 1

.

5. (a) 因为

1 0B1

0 0 1 0*

B1

0 0

000 1000 1

00 1000 10

1 1000 100

100 1000 1

1001 1000

01 1000 10

0 1100 100

0 1010 100

0 0 , 1 1 0 0 , 1 0

因此以v1为根的根树的个数为

2

T

det(B*B11)

03

10

0 130

1 1

24. 12

10 1

.

(b) 去掉边(v1, v5)后，有

11 10000 10

0 0 1001 1 10 ,B1

0 1000 110 1 000 110011

00 10000 10

0 0 1000 1 10* ,B1

0 1000 100 1

00 100000 0

因此以v1为根且不含边(v1,v5)的根树的个数为

2

1

1

03

10

0 130

1 1

8. 11

det(B*BT)

10 1

.

(c) 去掉到v3的其它全部边(v4, v3)、(v5, v3)后，有

011 100 10

0 00 10010 ,B1 00 1000 1 1

0 1101 0 10

000 100 10

0 00 10000* ,B1 00 1000 1 1 0 100 1000

因此以v1为根且含边(v2,v3)的根树的个数为

2

T det(B*1B1)

01

10

0030

10

9. 12

10 1

.

10. (1) 余树为｛e1, e2, e5, e 8｝, 重排B5的各列得

e1e2e5e8e3e4e6e7

00

0010 -11

1 0100100

B5 ＝ ( B11 B12 ) ,

0-100-100-1 00-1-11-100

余树

树T

00 10 -11 00 1 01 01000

则　B11 , B12 ,

0-10 -100 0-1 00-1-11-100

由定理3.4.4,

1 1 0 0

e201001010e500100 100e8

0 0

10 1 0

1 1e3

e4 10 10

0100e61 1001000e7

1 1 .0 1 0 1

0 1

1 0 1 1

10 10

1 100

1 1 ,0 1

T 1 T

Cf12 B11B12

基本回路矩阵为 e1 1 0

Cf ( I Cf12 )

0 0

0 100 0011

(2) 由定理3.4.8, 基本割集矩阵为

e1 1 1

T

Sf ( Sf11 I ) ( -Cf12 I )

-1 -1

e20011e50100

e8

e3

e40100e60010

e7

0

0 .0

1

-1100 0010

14．(a) 这是一个求最优二叉树的问题。

各字符出现次数为： s t a e c 空格 3 4 5 1 1 4

所以最优二进制编码为：

e: 1100 c: 1101 s: 111 t: 00 空格：01 a: 10 此时字符串的二进制编码总长度为43 .

(b) 去掉空格，类似(a)计算。