…………………… 密……………封……………线……………以……………内……………答…… ………题……………无……………效…………………… 电子科技大学研究生试卷

（考试时间： 至 ，共__2_小时）

课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2013__年_6__月__20__日 成绩 考核方式： （学生填写）

一．填空题(每空

学 号 姓 名 学 院 2分，共20分)

1． n阶k正则图G的边数m=_____。 2．4个顶点的不同构单图的个数为________。

3．完全偶图Kr,s(r,s?2且为偶数)，则在其欧拉环游中共含____条边。 4．高为h的完全2元树至少有_______片树叶。

5. G由3个连通分支K1,K2,K4组成的平面图，则其共有_______个面。 6. 设图G与K5同胚，则至少从G中删掉_______条边，才可能使其成为可平面图。

7. 设G为偶图，其最小点覆盖数为?，则其最大匹配包含的边数为

________。

8. 完全图K6能分解为________个边不重合的一因子之并。 9. 奇圈的边色数为______。 10. 彼得森图的点色数为_______。 二．单项选择(每题3分，共15分) 1．下面说法错误的是( )

1

(A) 图G中的一个点独立集，在其补图中的点导出子图必为一个完全子图；

(B) 若图G连通，则其补图必连通； (C) 存在5阶的自补图； (D) 4阶图的补图全是可平面图. 2．下列说法错误的是（ ） (A) 非平凡树是偶图；

(B) 超立方体图(n方体,n?1)是偶图； (C) 存在完美匹配的圈是偶图； (D) 偶图至少包含一条边。 3.下面说法正确的是( ) (A) 2连通图的连通度一定为2； (B) 没有割点的图一定没有割边；

(C) n(n?3)阶图G是块，则G中无环，且任意两点均位于同一圈上； (D) 有环的图一定不是块。 4.下列说法错误的是( )

(A) 设n(n?3)阶单图的最小度满足??，则其闭包一定为完全图； (B) 设n(n?3)阶单图的任意两个不邻接顶点u与v满足d(u)?d(v)?n，则其闭包一定为完全图；

(C)有割点的图一定是非哈密尔顿图；

(D) 一个简单图G是哈密尔顿图的充要条件是它的闭包是哈密尔顿图。

2

n

2

5.下列说法错误的是( )

(A) 极大平面图的每个面均是三角形； (B) 极大外平面图的每个面均是三角形；

(C) 可以把平面图的任意一个内部面转化为外部面； (D) 连通平面图G的对偶图的对偶图与G是同构的。

三、 (10分)设d1,d2,dn是n个不同的正整数，求证：序列??(d1,d2,,dn)不能是简单图的度序列。

四，(15分) 在下面边赋权图中求：(1)每个顶点到点v1的距离(只需要把距离结果标在相应顶点处，不需要写出过程); (2) 在该图中求出一棵最小生成树，并给出最小生成树权值(不需要中间过程，用波浪线在图中标出即可)；(3)，构造一条最优欧拉环游。

v1167459486v232v610v3v5v4

3