电子科技大学研究生试题图论及其应用参考答案修订稿

1、电子科技大学研究生试题图论及其应用参考答LOGODocument number SA80SAB-SAA9SYT-SAATC-SA6UT-SA18电子科技大学研究生试题图论及其应用(参考答案)考试时间：120分钟 一.填空题(每题3分，共18分)1 . 4个顶点的不同构的简单图共有_11_个；2 .设无向图G中有12条边，已知G中3度顶点有6个，其余顶点的度数均小于3o则G中顶点数至少有_9一个;3 .设n阶无向图是由k(k2)棵树构成的森林，则图G的边数m=_n-k.4 .下图G是否是平面图答是；是否可1-因子分解答是5 .下图G的点色数7(G)=,边色数/(G)=_5-o二.单项选择(每题3

2、分，共21分)1 .下面给出的序列中，是某简单图的度序列的是(A )(A) (11123); (B) (233445); (C) (23445); (D) (1333).2 .已知图G如图所示，则它的同构图是(D )3 .下列图中，是欧拉图的是(D)4 .下列图中，不是哈密尔顿图的是(B )5.下列图中，是可平面图的图的是(B )ABCD6 .下列图中，不是偶图的是（B ）7 .下列图中，存在完美匹配的图是（B ）三.作图（6分）1 .画出一个有欧拉闭迹和哈密尔顿的图;2 .画出一个有欧拉闭迹但没有哈密尔顿的图;的图;4 .（10分）求下图的最小生成树，并求其最小生成树的权值之和。解：由克鲁斯

3、克尔算法的其一最小生成树如下图：权和为：20.5 .（8分）求下图G的色多项式R（G）.解：用公式6（G-c）=）07型多 可得G的色多项式：PJG） = （Zb + 3（口 +2）（攵-3） o6 .（10分）一棵树有m细点的度数为2, m个顶点的度数为3,，取个顶点的 度数为k,而其余顶点的度数为1,求1度顶点的个数。解：设该树有m个1度顶点，树的边数为m.一方面：2m=ni+2n2+, , +knk另一方面：m= ni+n2+>*,+nk-l由上面两式可得：ni=n2+2n3+ (k-1) nk七.证明：(8分)设G是具有二分类(X,Y)的偶图，证明(1)G不含奇圈；(2)若 X

4、Y I，则G是非哈密尔顿图。证明：(1)若不然，设C=v,2Va vi为G的一个奇圈，不妨设ViX, 则：vX,这样推出V1与v.邻接，与G是偶图矛盾。(2)若XY,设|X|r|,则(G-Y)Y,由H图的必要条件，G为非哈密尔顿图。八.(8分)设G是边数m小于30的简单连通平面图，证明:G中存在顶点v,使 d (v)4.证明：若不然，则对任意的vV(G),有d(v)5,这样，一方面有:2m=d (v) 5n另一方面，G为简单连通平面图,有:1113n-6由，屋1?,把该式代入得:m30,与题设矛盾。九.(8分)证明：每个没有割边的3正则图都有完美匹配。证明：设G是没有割边的3正则图，S是V的真子集，用G, G%,或表示G-S的 奇分支，并设n是一个顶点在G中，另一个端点在S中的那些边的条数。由于G是 3正则图，所以日一)=3眸)|, lin由式,ve