2023年7月19日发(作者：)
第十四章部分课后习题参考答案
5、设无向图 G 有 10 条边，3 度与 4 度顶点各 2 个，其余顶点的度数均小于 3，问 G 至
少有多少个顶点在最少顶点的情况下，写出度数列、
解：由握手定理图 G 的度数之和为： 2
20
∆
、
G
( ) (G) 。
10
3 度与 4 度顶点各 2 个，这 4 个顶点的度数之和为 14 度。
其余顶点的度数共有 6 度。
其余顶点的度数均小于 3，欲使 G 的顶点最少，其余顶点的度数应都取 2,
所以，G 至少有 7 个顶点, 出度数列为 3,3,4,4,2,2,2,
∆(
)
4 ,
( ) 2 .
G
G
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.
∆( )
( )
D
3,
(D)
( )
2,
2 ,
∆1,
∆D
D (
D)
2,(
D) 1
8、设无向图中有 6 条边，3 度与 5 度顶点各 1 个，其余顶点都是 2 度点，问该图有多少
个顶点
解：由握手定理图 G 的度数之和为： 2
设 2 度点
x
个，则 3
6
1 2x
12
12 ，
x
2 ，该图有 4 个顶点. 1 5
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 条边的无向简单图 G1、G2、G3，证明它们至少有两个是同构的。
证明：4 阶 4 条边的无向简单图的顶点的最大度数为 3，度数之和为 8，因而度数列
1 为 2，2，2，2；3，2，2，1；3，3，1，1。但 3，3，1，1 对应的图不是简单图。所以
从同构的观点看，4 阶 4 条边的无向简单图只有两个：
所以，G1、G2、G3
至少有两个是同构的。
20、已知 n 阶无向简单图 G 有 m 条边，试求 G 的补图
G
的边数
m′。
解：
′m
2
n(n −1)
m
21、无向图 G 如下图
(1)求 G 的全部点割集与边割集，指出其中的割点和桥；
(2) 求 G 的点连通度
k
(G) 与边连通度
a
e1
e2
b
(G) 。
d
e
e5
e4
c
解：点割集:
{a,b},(d)
e3
边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}
) =1
( ) =
k
(
G G
23、求 G 的点连通度 (
) 、边连通度 (
) 与最小度数 ( ) 。
k
GG
G
解： (G) 2 、
k
(G) 3
、 ( )
G
4
28、设 n 阶无向简单图为 3-正则图，且边数 m 与 n 满足 2n-3=m 问这样的无向图有几种
非同构的情况
解：⎨
⎨3
n
2m
⎨2n −3
得 n=6,m=9.
m
2 G
的边数分别为
m
和
m
，试确定 31、设图 G 和它的部图 G 的阶数。
解：
m
n(n
−1 8(m m)
m
1)
1
2
2
得
n
45、有向图 D 如图
(1)求
v到
v长度为 1，2，3，4 的通路数；
(2)求
v到
v长度为 1，2，3，4 的回路数；
(3)求 D 中长度为 4 的通路数；
(4)求 D 中长度小于或等于 4 的回路数；
(5)写出 D 的可达矩阵。
v1
v4
v5
v2
v3
解：有向图 D 的邻接矩阵为：
⎨0 0 0 0
1
⎨⎨0 1
0 1 0
⎨⎨2 0 2
⎨⎨0 1 0
0
⎨⎨
⎨
⎨0 0 0
2
⎨⎨
⎨
0 0 0
1
⎨2 0⎨
⎨
⎨1 0 1
0
⎨
⎨
⎨0
2
2A
⎨
⎨⎨0 1 0 0
⎨
，
A
⎨0 0 0
⎨2
⎨
⎨2 0⎨0 1 0⎨0
0
⎨
1
⎨
A
⎨0 0 0
⎨⎨⎨2 0
⎨2 0
0
⎨⎨0 0 0 0 4
4
⎨00⎨A
⎨
⎨⎨ ⎨⎨4⎨⎨4 0 4 0 0
0
⎨⎨40⎨0 0 0 0⎨0 0
⎨2
0
⎨0
0
⎨⎨
2 0
0
4
⎨⎨⎨0 4 0
⎨4
⎨2 1 5
0
⎨1
A
A
⎨⎨A
⎨5 2 2
5
⎨2
⎨2 1 5
2
⎨1
⎨⎨⎨5 2 2
4
⎨2
⎨⎨⎨2 52 5
⎨v到
v长度为 1，2，3，4 的通路数为 0,2,0,0；
v到
v长度为 1，2，3，4 的回路数为 0,0,4,0；
中长度为 4 的通路数为 32；
中长度小于或等于 4 的回路数 10；
3
4A
(1)
(2)
(3)D
(4)D
⎨1 1 1 1⎨⎨1
⎨1 1 1 1⎨⎨1 1 1 1⎨1
(4)出 D 的可达矩阵
⎨1 1 1 1⎨⎨1
⎨1 1 1
1
⎨P
⎨⎨1
⎨⎨1
第十六章部分课后习题参考答案
1、画出所有 5 阶和 7 阶非同构的无向树.
2、一棵无向树 T 有 5 片树叶，3 个 2 度分支点，其余的分支点都是 3 度顶点，问 T 有
几个顶点
解：设 3 度分支点
x
个，则
5 1
3
3 2 3x
2 (5 3
x −1) ，解得
x
T 有 11 个顶点
3、无向树 T 有 8 个树叶，2 个 3 度分支点，其余的分支点都是 4 度顶点，问 T 有几个 4
度分支点根据 T 的度数列，请至少画出 4 棵非同构的无向树。 解：设 4 度分支点
x
个，则
8 1 2 3 4x
2 (8 2
x −1) ，解得
x
2
度数列
4
4、棵无向树 T 有
几片树叶
(i=2，3，…，k )个 i 度分支点，其余顶点都是树叶，问 T 应该有
n
解：设树叶 片，则
x
ni
1
(n
x
−2
(
2)n2
i
x −1) ，解得
x
评论：2，3，4 题都是用了两个结论,一是握手定理，二是
m
5、n(n≥3)阶无向树 T 的最大度解：2，n-1
n −1
少为几最多为几
至
6、若 n(n≥3)阶无向树 T 的最大度解：n-1
=2，问 T 中最长的路径长度为几
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、在图 所示 2 图中，实边所示的生成子图 T 是该图的生成树.
(1)指出 T 的弦，及每条弦对应的基本回路和对应 T 的基本回路系统.
5 (2) 指出 T 的所有树枝， 及每条树枝对应的基本割集和对应 T 的基本割集系统.
(a)
图
(b)
解：(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、求图 所示带权图中的最小生成树.
(a)
(b)
图
解：
注：答案不唯一。
37、画一棵权为 3，4，5，6，7，8，9 的最优 2 叉树，并计算出它的权.
6
38.下面给出的各符号串集合哪些是前缀码
A1={0，10，110，1111}
000}
001，0011}
ac，aba，abb，abc}
是前缀码 A2={1，01，001， 是前缀码 A3={1，11，101，不是前缀码 A4={b，c，aa，是前缀码 A5={ b，c，a，不是前缀码 aa，ac，abc，abb，aba}
41.设 7 个字母在通信中出现的频率如下:
a: 35%
c: 15%
e: 10%
g: 5%
b: 20%
d: 10%
f: 5%
用 Huffman 算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码.
并指出传输 10n(n≥2)个按上述频率出现的字母，需要多少个二进制数字.
解：
a:01 b:10 c:000 d:110 e:001 f:1111 g: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
发布者：admin，转转请注明出处：http://www.yc00.com/news/1689733022a281864.html
评论列表（0条）