1
第十四章部分课后习题参考答案
5 、设 无向图 G 有 10 条边， 3 度与 4 度顶点各 2 个，其余顶点的度数均小于 3 ，问 G 至
少有多少个顶点？在最少顶点的情况下，写出度数列、 。
)()(
GG δ
、∆
解： 由握手定理图 G 的度数之和为：
20102 =×
3 度与 4 度顶点各 2 个，这 4 个顶点的度数之和为 14 度。
其余顶点的度数共有 6 度。
其余顶点的度数均小于 3 ，欲使 G 的顶点最少，其余顶点的度数应都取 2,
所以， G 至少有 7 个顶点 , 出度数列为 3,3,4,4,2,2,2, .
2)(,4)( ==∆
GG δ
7 、设有向图 D 的度数列为 2 ， 3 ， 2 ， 3 ，出度列为 1 ， 2 ， 1 ， 1 ，求 D 的入度列，并求
，
)(),(
DD δ
∆
, .
)(),(
DD
++
∆
δ
)(),(
DD
−−
∆
δ
解： D 的度数列为 2 ， 3 ， 2 ， 3 ，出度列为 1 ， 2 ， 1 ， 1 ， D 的入度列为 1,1,1,2.
, ,
2)(,3)( ==∆
DD δ
1)(,2)( ==∆
++
DD δ
1)(,2)( ==∆
−−
DD δ
8
、设
无向图中有 6 条边， 3 度与 5 度顶点各 1 个，其余顶点都是 2 度点，问该图有多 少
个顶点？
解： 由握手定理图 G 的度数之和为：
1262 =×
设 2 度点 个，则 ， ，该图有 4 个顶点 .
x
1221513 =+×+×
x
2=
x
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 ， 因而度数 列
www.khdaw.com
课后答案网
