2005 年研究生期末试题 (120 分钟 )
《图论及其应用》
一、填空 (15 分,每空 1 分)
1、 已知图 G 有 10 条边, 4 个度数为 3 的顶点,其余顶点的度数均小于 2,则
G 中至少有 ___ 8___ 个顶点 .
2、 m 条边的简单图 G 中所有不同的生成子图 (包括 G 和空图 )的个数为
__ 2 ____.
m
3、 4 个顶点的非同构的简单图有 __11___ 个.
4、 图 G1
的最小生成树各边权值之和为
__ 28 ___.
5、若
W
是图
G
中一条包含所有边的闭通道,则
W
在这样的闭通道中具有最短长
度的充要条件是:
(1) 每一条边最多重复经过
_1__
次;
(2) 在
G
的每一个圈上,重复经过的边的数目不超过圈的长度的 _ ___.一半
6、5 阶度极大非哈密尔顿图族有
5 5
2 1
__ , __ ___C C .
7、在图 G2 中,图的度序列为 (44443322),频序列为 (422),独立数为 3,
团数为 4,点色数为 4,边色数为 4,直径为 3.
二、选择 (15 分)
(1)下列序列中,能成为某简单图的度序列的是 ( C )
(A) (54221) (B) (6654332) (C) (332222)
(2)已知图 G 有 13 条边, 2 个 5 度顶点, 4 个 3 度顶点,其余顶点的的度数为
2,则图 G 有( A )个 2 度点。
5
6
1
2
5 10
9
4
3
1
6
7 4
图 G
1
图 G
2
评论0