2015电子科技大学研究生试卷

…………………… 效 …

… … … … 无 … … … … …

题 … … 院… 学…… 答 … … … … … 内 … … … 名…… 姓以 … … … … … 线 … … … … … 封 … … 号…… 学…密 ……………………

电子科技大学研究生试卷

(考试时间: 至 ,共__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

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