2006年春-期末考试-无答案1
需积分: 0 121 浏览量
2022-08-03
17:33:14
上传
评论
收藏 123KB PDF 举报
2006 研究生图论期末试题 (120 分钟 )
一、填空题 (15 分，每空 1 分)
1、若两个图的顶点与顶点之间，边与边之间都存在
_________
对应，而且它们的关联关
系也保持其
_________
关系，则这两个图同构。
2、完全图
4
K 的生成树的数目为
_________
；阶为 6 的不同构的树有
_________
棵。
3、设无向图
G
有 12 条边，已知
G
中度为 3 的结点有 6 个，其余结点的度数均小于 3，则
G
中至少有
_________
个结点。
4、具有 5 个结点的自补图的个数有
_________
。
5、已知图
G
的邻接矩阵
11110
10101
11010
10111
01010
)(GA
，顶点集合
54321
,,,,)( vvvvvGV
，
则由
2
v 到
5
v 的途径长度为 2 的条数为
_________
。
6、若
n
K
为欧拉图，则 n= _________ ；若
n
K
仅存在欧拉迹而不存在欧拉回路，则
n= _________ 。
7、无向完全图
n
K (n 为奇数 )，共有
_________
条没有公共边的哈密尔顿圈。
8、设 G 是具有二分类
),( YX
的偶图，则 G 包含饱和 X 的每个顶点的匹配当且仅当
_________ ，对所有
XS
。
9、在有 6 个点。 12 条边的简单连通平面图中，每个面均由
_________
条边组成。
10、彼德森图的点色数为 _________ ；边色数为 _________ ；点独立数为 _________ 。
二、单选或多选题 (15 分，每题 3 分)
1、设 5,4,3,2,1V ， ,)1,5(),5,4(),4,3(),3,2(),2,1(E 则图 EVG , 的补图是 ( ).
1
2
3 4
5
A
1
1
2
3
4
5
B
C
2
3 4
5
D
1
Friday永不为奴
- 粉丝: 12
- 资源: 317
评论0