电子科技大学研究生试题

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

考试时间：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

二．单项选择(每题3分，共21分)

1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D） 4． 下列图中，不是哈密尔顿图的是（B ）

A B C D 5． 下列图中，是可平面图的图的是（B ）

A B C D 6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分)

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

3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解：

v1167v224v61 358102 3 v39v546v4四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20.

五．(8分 )求下图G的色多项式Pk

(G). 解：用公式Pk(G?e)?Pk(G)?Pk(G?e)，可得G的色多项式：

Pk(G)?(k)5?3(k)4?(k)3?k(k?1)2(k?2)(k?3)。

六．(10分) 一棵树有n2个顶点的度数为图G 2，n3个顶点的度数为3，…，个顶点的度数为k，而其余顶点的度数为1，求1度顶点的个数。解：设该树有n1个1度顶点，树的边数为m.

一方面：2m=n1+2n2+…+knk

另一方面：m= n1+n2+…+nk-1

nk

由上面两式可得：n1=n2+2n3+…+(k-1)nk

七．证明：(8分) 设G是具有二分类(X,Y)的偶图，证明(1)G不含奇圈；（2）若|X |≠|Y |，则G是非哈密尔顿图。

证明：(1) 若不然，设C=v1v2…vm v1为G的一个奇圈，不妨设v1?X, 则：vm?X,这样推出v1与vm邻接，与G是偶图矛盾。

(2)若 |X |≠|Y |，设|X |?|Y |，则 ?(G-Y)??Y?,由H图的必要条件，G为非哈密尔顿图。

八．（8分）设G是边数m小于30的简单连通平面图，证明:G中存在顶点v，使d(v)?4.

证明：若不然，则对任意的v?V(G),有d(v)?5，这样，一方面有：

2m=?d(v)?5n (1)

另一方面，G为简单连通平面图，有：

m?3n-6 (2)

由(1),n?m,把该式代入(2)得：m?30,与题设矛盾。 九．(8分) 证明：每个没有割边的3正则图都有完美匹配。

证明：设G是没有割边的3正则图，S是V的真子集，用G1, G2,…,Gn表示G-S的奇分支，并设mi是一个顶点在Gi中，另一个端点在S中的那些边的条数。由于G是3正则图，所以

v?V(G)25?d(v)?3V(G), 1?i?n (1)

i且

?d(v)?3S （2）

v?S由(1)式，mi?v?V(Gi)?d(v)?2E(G)是奇数。又由于G没有割边，所以mi ?1

i