…………………… 效 …
… … … … 无 … … … … …
题 … … 院… 学…… 答 … … … … … 内 … … … 名…… 姓以 … … … … … 线 … … … … … 封 … … 号…… 学…密 ……………………
电子科技大学研究生试卷
（考试时间： 至 ，共__2_小时）
课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2015__年_6__月__26__日 成绩 考核方式： （学生填写）
一．填空题(每空
3分，共15分)
1.不同构的3阶简单图的个数为_____。 2．图1中的最小生成树的权值为________。 3.基于图2的最优欧拉环游的总权值为__________。 4.图3中块的个数为_______。 6 1 6 6 3 2 2 4 5 1 2 2 2 8 7 3 4 1 3 3 6 3 2
图1 图2 图3 5.图4中强连通分支的个数为________。
图4
1
二．单项选择(每题3分，共15分) 1．关于图的度序列，下列命题错误的是( ) (A) 同构的两个图的度序列相同；
(B) 非负整数序列(d1,d2,,dn)是图的度序列当且仅当?di是偶数；
i?1n (C) 如果非负整数序列(d1,d2,,dn)(n?2)是一棵树的度序列，那么序列中至少有两个整数的值为1；
(D). 如果非负整数序列(d1,d2,,dn)是简单图的度序列，那么在同构意义下只能确定一个图。
2．关于n阶简单图的邻接矩阵A?(aij)n?n，下列说法错误的是（ ） (A) 矩阵A的行和等于该行对应顶点的度数； (B) 矩阵所有元素之和等于该图边数的2倍；
(C) 不同构的两个图，它们的邻接矩阵特征谱一定不同； (D) 非连通图的邻接矩阵一定可以表示为准对角矩阵形式。 3.关于欧拉图，下面说法正确的是( ) (A) 欧拉图存在唯一的欧拉环游； (B) 非平凡欧拉图中一定有圈； (C) 欧拉图中一定没有割点； (D) 度数为偶数的图一定是欧拉图。 4.关于哈密尔顿图，下列命题错误的是( )
(A)设G是n?3的简单图，若其闭包是完全图，则G是哈密尔顿图； (B) 若n阶单图的闭包不是完全图，则它一定是非哈密尔顿图；
2
(C)若G是哈密尔顿图，则对于V的每个非空顶点子集S，均有
?(G?S)?S；
(D) 若G是n?3的非H单图，则G度弱于某个Cm,n图。 5.关于偶图，下列说法错误的是( ) (A) 偶图中不存在奇圈；
(B) 非平凡偶图的最大匹配是唯一的； (C) k(k?0)正则偶图存在完美匹配；
(D) 偶图中，最大匹配包含的边数等于最小点覆盖包含的顶点数。 三、 (20分)在一个赋权完全图中找到一个具有最小权值的哈密尔顿圈，称这种圈为最优哈密尔顿圈。(1)、用边交换技术方法求出图5中基于初始圈LTPePaNyMcL的近似最优哈密尔顿圈；(2)、如何获取最优哈密尔顿圈权值的一个下界？以图5为例进行说明。
60 L
56
2 35 70 61 78 68 51 68 57 Ny Mc 21
51 T 13
Pe
36 Pa 图5
3