4度

G







第十四章部分课后习题参考答案

5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G至

∆、

少有多少个顶点？在最少顶点的情况下，写出度数列、

解：由握手定理图G的度数之和为：210

20

()(G)。

3度与4度顶点各2个，这4个顶点的度数之和为14度。

其余顶点的度数共有6度。

其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取2,

所以，G至少有7个顶点,出度数列为3,3,4,4,2,2,2,∆()

4

,

()2.

GG

7、设有向图D的度数列为2，3，2，3，出度列为1，2，1，1，求D的入度列，并求

∆(D),(D)，

∆(

D),

()

,∆−

D

(D),



(D).

解：D的度数列为2，3，2，3，出度列为1，2，1，1，D的入度列为1,1,1,2.

∆()3,

()2,∆DD

(D)

2,



()

1,∆−

D

(D)

2,

(D)1

8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少

个顶点？

解：由握手定理图G的度数之和为：2612

设2度点x个，则31512x12，x2，该图有4个顶点.

14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同

构的无向图，其中至少有两个时简单图。

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

解：(1)2+2+3+3+4+4+5=23是奇数，不可图化；

(2)2＋2+2+2+3+3+4+4=16,是偶数，可图化；

18、设有3个4阶4条边的无向简单图G

1

、G

2

、G

3

，证明它们至少有两个是同构的。

证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列

1



k



k

k

G



3

为2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1对应的图不是简单图。所以

从同构的观点看，4阶4条边的无向简单图只有两个：

所以，G

1

、G

2

、G

3

至少有两个是同构的。

20、已知n阶无向简单图G有m条边，试求G的补图G的边数m

′

。

解：

′

n(n−1)

m

2

m

21、无向图G如下图

(1)求G的全部点割集与边割集，指出其中的割点和桥；

(2)求G的点连通度k(G)与边连通度(G)。

a

e1

e2

d

e

b

e5

解：点割集:

{a,b},(d)

e3

e4

c

边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}

()=

(

GG

)=1

23、求G的点连通度(G)、边连通度(

G

)与最小度数()。G

解：(G)2、

(G)3

、()4





28、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种

非同构的情况？

解：

⎧



n

2m

得n=6,m=9.

⎧

2n−3m

2





A



0000

2

101

3

020



101000000202020



1

010

0



0

000

2



0

202

0





0

0

4

0

4



23

31、设图G和它的部图

G

的边数分别为

m

和

m

，试确定G的阶数。

解：m

m

n(n

1)

2

−

1



得n



18(mm)

2

45、有向图D如图

(1)求v

2

到v

5

长度为1，2，3，4的通路数；

(2)求v

5

到v

5

长度为1，2，3，4的回路数；

(3)求D中长度为4的通路数；

(4)求D中长度小于或等于4的回路数；

(5)写出D的可达矩阵。

v1

v4

v5

v2

v3

解：有向图D的邻接矩阵为：

⎧0000

⎧











⎧

010

1

1⎧



⎧





1

⎧

，A

⎧



⎧



⎧01

⎧





⎧

0

⎧



⎧

20

010⎧



⎧





0

⎧

A

⎧



20

⎧



⎧20200⎧



⎧⎧





⎧

20

⎧





⎧⎧



⎧

0000

⎧



⎧00004

⎧



⎧⎧

⎧

40400

⎧

4⎧

000

04

⎧



A

⎧⎧

⎧40400

⎧

⎧⎧



⎧

0404

⎧











AA











A

A

⎧01

⎧

⎧

52

4

⎧

2

1

⎧

⎧42

⎧



⎧

25

215⎧



⎧

522

⎧

215

⎧



⎧

522⎧

⎧



25

⎧



(1)v

2

到v

5

长度为1，2，3，4的通路数为0,2,0,0；

(2)v

5

到v

5

长度为1，2，3，4的回路数为0,0,4,0；

(3)D中长度为4的通路数为32；

(4)D中长度小于或等于4的回路数10；

3

1



⎧

1

⎧

⎧

1

(4)出D的可达矩阵

⎧

1

P

⎧

⎧

1

⎧



⎧

1

1111⎧



⎧

1111

⎧

1111

⎧



⎧

1111⎧

111

⎧



第十六章部分课后习题参考答案

1、画出所有5阶和7阶非同构的无向树.

2、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有

几个顶点?

解：设3度分支点x个，则

51323x2(53x−1)，解得

x3

T有11个顶点

3、无向树T有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T有几个4

度分支点？根据T的度数列，请至少画出4棵非同构的无向树。

解：设4度分支点x个，则

81234x2(82x−1)，解得x

2

度数列4

4

至

i

n4、棵无向树T有

i

几片树叶?

(i=2，3，…，k)个i度分支点，其余顶点都是树叶，问T应该有

解：设树叶片，则x

n

i

ix

12

(n

i

x−1)，解

得x(

−2)n

i

2

评论：2，3，4题都是用了两个结论,一是握手定理，二是mn−1

5、n(n≥3)阶无向树T的最大度少为几？最多为几？

解：2，n-1

6、若n(n≥3)阶无向树T的最大度=2，问T中最长的路径长度为几？

解：n-1

7、证明：n(n≥2)阶无向树不是欧拉图.证明：

无向树没有回路，因而不是欧拉图。

8、证明：n(n≥2)阶无向树不是哈密顿图.证明：

无向树没有回路，因而不是哈密顿图。

9、证明：任何无向树T都是二部图.

证明：无向树没有回路，因而不存在技术长度的圈，是二部图。

10、什么样的无向树T既是欧拉图，又是哈密顿图?

解：一阶无向树

14、设e为无向连通图G中的一条边，e在G的任何生成树中，问e应有什么性质?

解：e是桥

15、设e为无向连通图G中的一条边，e不在G的任何生成树中，问e应有什么性质?

解：e是环

23、已知n阶m条的无向图G是k(k≥2)棵树组成的森林，证明：m=n-k.；

证明：数学归纳法。k=1时,m=n-1，结论成立；

设k=t-1(t-1≥1)时，结论成立，当k=t时,无向图G是t棵树组成的森林,任

取两棵

树，每棵树任取一个顶点，这两个顶点连线。则所得新图有t-1棵树，所以m=n-（k-1）.

所以原图中m=n-k

得证。

24、在图16.6所示2图中，实边所示的生成子图T是该图的生成树.

(1)指出T的弦，及每条弦对应的基本回路和对应T的基本回路系统.

5

(2)指出T的所有树枝，及每条树枝对应的基本割集和对应T的基本割集系统.

(a)(b)

图16.16

解：(a)T的弦：c,d,g,h

T的基本回路系统:S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a,b,f,g}}

T的所有树枝:e,a,b,f

T的基本割集系统:S={{e,g,h},{a,c,d,g,h},{b,c,d,g,h},{f,d,g}}

(b)有关问题仿照给出

25、求图16.17所示带权图中的最小生成树.

(a)(b)

图16.17

解：

注：答案不唯一。

37、画一棵权为3，4，5，6，7，8，9的最优2叉树，并计算出它的权.

6

38.下面给出的各符号串集合哪些是前缀码?

A1={0，10，110，1111}是前缀码A2={1，01，001，

000}是前缀码A3={1，11，101，

001，0011}不是前缀码A4={b，c，aa，

ac，aba，abb，abc}是前缀码A5={b，c，a，

aa，ac，abc，abb，aba}不是前缀码

41.设7个字母在通信中出现的频率如下:

a:35%b:20%

c:15%d:10%

e:10%f:5%

g:5%

用Huffman算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码.

并指出传输10n(n≥2)个按上述频率出现的字母，需要多少个二进制数字.

解：

a:01b:10c:000d:110e:001f:1111g:1110

W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255

传输10n(n≥2)个按上述频率出现的字母，需要255*10n-2个二进制数字.

7