电子科技大学研究生试题《图论及其应用》(参考答案) 下载本文

内容发布更新时间 : 2024/12/23 20:12:56星期一 下面是文章的全部内容请认真阅读。

电子科技大学研究生试题

《图论及其应用》(参考答案)

考试时间:120分钟

一.填空题(每题3分,共18分)

1.4个顶点的不同构的简单图共有__11___个;

2.设无向图G中有12条边,已知G中3度顶点有6个,其余顶点的度数均小于3。则G中顶点数至少有__9___个;

3.设n阶无向图是由k(k?2)棵树构成的森林,则图G的边数m= _n-k____;

4.下图G是否是平面图?答__是___; 是否可1-因子分解?答__是_.

5.下图G的点色数?(G)?______, 边色数??(G)?__5____。

图G

图G

二.单项选择(每题3分,共21分)

1.下面给出的序列中,是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2.已知图G如图所示,则它的同构图是( D )

d121234bc434312a图(G)ABC

3. 下列图中,是欧拉图的是( D)

ABCD

4. 下列图中,不是哈密尔顿图的是(B )

A B C D 5. 下列图中,是可平面图的图的是(B )

A B C D D

6.下列图中,不是偶图的是( B )

A B C D

7.下列图中,存在完美匹配的图是(B )

ABCD三.作图(6分)

1.画出一个有欧拉闭迹和哈密尔顿圈的图; 2.画出一个有欧拉闭迹但没有哈密尔顿圈的图;

3.画出一个没有欧拉闭迹但有哈密尔顿圈的图; 解:

1 2 3 四.(10分)求下图的最小生成树,并求其最小生成树的权值之和。