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

电子科技大学研究生试题

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

考试时间: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.画出一个没有欧拉闭迹但有哈密尔顿圈的图; 解: v1167459486v21 32v6102 3 v3v5v4四.(10分)求下图的最小生成树,并求其最小生成树的权值之和。 解:由克鲁斯克尔算法的其一最小生成树如下图: 权和为:20.

)求下图G的色多项式P(G). 五.(8分k

解:用公式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图个顶点的度数为2,n3个顶点的度数为3,…,nk个顶G 点的度数为k,而其余顶点的度数为1,求1度顶点的个数。 解:设该树有n1个1度顶点,树的边数为m.

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

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

由上面两式可得: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没有割边,所以m ?1

ii

因此,mi ?3, 1 ?i ?n (3) 由(3)可得:

由托特定理,G中有完美匹配。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4