电子科技大学研究生试?/p>
《图论及其应用?/p>
(
参考答?/p>
)
考试时间?/p>
120
分钟
一.填空题
(
每题
3
分,?/p>
18
?/p>
)
1
?/p>
4
个顶点的不同构的简单图共有
__11___
个;
2
.设无向?/p>
G
中有
12
条边,已?/p>
G
?/p>
3
度顶点有
6
个,其余顶点的度?/p>
均小?/p>
3
。则
G
中顶点数至少?/p>
__9___
个;
3
.设
n
阶无向图是由
k(k
?/p>
2)
棵树构成的森林,则图
G
的边?/p>
m= _n-k____;
4
.下?/p>
G
是否是平面图?答
__
?/p>
___;
是否?/p>
1-
因子分解?答
__
?/p>
_.
5
.下?/p>
G
的点色数
?/p>
)
(
G
?/p>
______,
边色?/p>
?/p>
?/p>
)
(
G
?/p>
__5____
?/p>
?/p>
G
二.单项选择
(
每题
3
分,?/p>
21
?/p>
)
1
.下面给出的序列中,是某简单图的度序列的是
( A )
(A) (11123); (B) (233445); (C) (23445); (D) (1333).
2
.已知图
G
如图所示,则它的同构图是(
D
?/p>
3
?/p>
下列图中,是欧拉图的是(
D
?/p>
4
?/p>
下列图中,不是哈密尔顿图的是?/p>
B
?/p>
5
?/p>
下列图中,是可平面图的图的是?/p>
B
?/p>
A
B
C
D
A
B
C
D