G +
第十四章部分课后习题参考答案
5、设无向图 G 有 10 条边，3 度与 4 度顶点各 2 个，其余顶点的度数均小于 3，问 G 至 ∆ 、
少有多少个顶点？在最少顶点的情况下，写出度数列、 解：由握手定理图 G 的度数之和为： 2
10
20
( )
(G ) 。
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.
∆( ) 3, ( ) 2 , ∆ D D (D ) 2,
( ) 1, ∆−
D ( D ) 2,
( D ) 1
8、设无向图中有 6 条边，3 度与 5 度顶点各 1 个，其余顶点都是 2 度点，问该图有多少 个顶点？
解：由握手定理图 G 的度数之和为： 2 6 12 设 2 度点 x 个，则 3脊灰野病毒
1
5
1
2x
12 ， x
2 ，该图有 4 个顶点.
14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出 3 种非同 构的无向图，其中至少有两个时简单图。
颐和园2006
(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条边的无向简单图只有两个：
所以，G1、G2、G3至少有两个是同构的。
20、已知n阶无向简单图G有m条边，试求G的补图G的边数m′。 解：′n(n −1)
m
2
m
21、无向图G如下图
(1)求G 的全部点割集与边割集，指出其中的割点和桥； (2) 求G的点连通度k (G) 与边连通度(G ) 。
a e1
e2d
e
b e5
解：点割集: {a,b},(d)e3
e4
边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}团队氛围
( ) =
(G G
) =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− 3 m
2
A = 0 0 0
0 2 1 0 1 3 0 2 0 1 0 1 0 0
0 0 0 0 2 0 2 0 2 0
1 0 1 0 0 0 0 0 0
2 0 2 0 2 0
0 0 4 0 4
2 3
31、设图 G 和它的部图 G 的边数分别为 m 和 m ，试确定 G 的阶数。
解： m
m
n (n 1) 2
−
1 得 n
1 8(m m )
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 的邻接矩阵为：
⎧0 0 0
0 ⎧
⎧0
1 0
1 1 ⎧
⎧
1 ⎧， A
⎧
⎧ ⎧0 1 ⎧
⎧0
⎧
⎧ 2 0 0 1 0 ⎧
⎧南黄海
⎧A
⎧ 2 0 ⎧
⎧ 2
0 2 0 0 ⎧
⎧
⎧ ⎧
2 0 ⎧
⎧ ⎧ ⎧0 0 0
0 ⎧
⎧0 0 0 0 4 ⎧ ⎧ ⎧
⎧ 4 0 4 0 0 ⎧
4 ⎧0 0 0
0 4 ⎧
A ⎧ ⎧
⎧ 4 0 4 0 0 ⎧ ⎧ ⎧ ⎧0 4 0 4 ⎧ A A
A
A
⎧01 ⎧ ⎧52 4 ⎧2
1 ⎧ ⎧4
2 ⎧ ⎧25
2 1 5 ⎧
⎧ 5 2 2 ⎧ 2 1 5 ⎧ ⎧ 5 2 2 ⎧ ⎧ 2 5
⎧
(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；
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议