一．填空题(每空3分，共15分)
1.不同构的3阶简单图的个数为___
2．图1中的最小生成树的权值为___
3.基于图2的最优欧拉环游的总权值为。
4.图3中块的个数为。
5.图4中强连通分支的个数为。
二．单项选择(每题3分，共15分)
1．关于图的度序列，下列命题错误的是( )
(a) 同构的两个图的度序列相同；
b) 非负整数序列是图的度序列当且仅当是偶数；
(c) 如果非负整数序列是一棵树的度序列，那么序列中至少有两个整数的值为1；
(d). 如果非负整数序列是简单图的度序列，那么在同构意义下只能确定一个图。
2．关于阶简单图的邻接矩阵，下列说法错误的是（ ）
(a) 矩阵的行和等于该行对应顶点的度数；
b) 矩阵所有元素之和等于该图边数的2倍；
(c) 不同构的两个图，它们的邻接矩阵特征谱一定不同；
(d) 非连通图的邻接矩阵一定可以表示为准对角矩阵形式。
3.关于欧拉图，下面说法正确的是( )
a) 欧拉图存在唯一的欧拉环游；
b) 非平凡欧拉图中一定有圈；
c) 欧拉图中一定没有割点；
(d) 度数为偶数的图一定是欧拉图。
4.关于哈密尔顿图，下列命题错误的是( )
a)设是的简单图，若其闭包是完全图，则是哈密尔顿图；
b) 若阶单图的闭包不是完全图，则它一定是非哈密尔顿图；
c)若g是哈密尔顿图，则对于的每个非空顶点子集，均有；
d) 若g是的非h单图，则g度弱于某个图。
5.关于偶图，下列说法错误的是( )
(a) 偶图中不存在奇圈；
(b) 非平凡偶图的最大匹配是唯一的；
(c)正则偶图存在完美匹配；
(d) 偶图中，最大匹配包含的边数等于最小点覆盖包含的顶点数。
三、 (20分)在一个赋权完全图中找到一个具有最小权值的哈密尔顿圈，称这种圈为最优哈密尔顿圈。(1)、用边交换技术方法求出图5中基于初始圈的近似最优哈密尔顿圈；(2)、如何获取最优哈密尔顿圈权值的一个下界？以图5为例进行说明。
四，(10分)。矩阵的一行或一列称为矩阵的一条线，利用哥尼定理证明：布尔矩阵中，包含了所有“1”的最少数目，等于具有性质“任意两个1都不在同一条线上的1的最大数目”。
（注：哥尼定理：在偶图中，最大匹配包含的边数等于最小点覆盖包含的顶点数）
五．(10分) 求证：设是n阶的具有m条边的简单连通平面图，则：。
六。(20分) 一家公司计划建造一个动物园，他们打算饲养下面这些动物：狒狒(b)、狐狸(f)、山羊(g)、土狼(h)、非洲大羚羊(k)、狮子(l)、豪猪(p)、兔子(r)、鼩鼱(s)、羚羊(w)和斑马(z)。
根据经验，动物的饮食习惯为：狒狒喜欢吃山羊、非洲大羚羊(幼年)、兔子和鼩鼱；狐狸喜欢吃山羊、豪猪、兔子和鼩鼱；土狼喜欢吃山羊、非洲大羚羊、羚羊和斑马；狮子喜欢吃山羊、非洲大羚羊、羚羊和斑马；豪猪喜欢吃鼩鼱和兔子；而其余的则喜欢吃虫子、蚯蚓、草或其它植物。公司将饲养这些动物，希望它们能自由活动但不能相互捕食。
求这些动物的一个分组，使得需要的围栏数最少。(要求用图论方法求解)
七．(10分)求下图g的色多项式pk(g).并求出点色数。
电子科技大学研究生试卷
考试时间至共 2 小时 课程名称 数字信号处理 教师学时 40 学分 2 教学方式考核日期年月日成绩。考核方式 开卷 1 20分 一个连续信号的数字处理系统如图 a 所示，具有带限的频谱，如图 b 所示。对其以nyquist采样率进行采样。频率响应为的数字理想高通如图 c 所示。分别做出，和的频谱图...
2019电子科技大学研究生试卷
一 填空题 每空2分，共20分 1 n阶简单正则图g的补图的边数为 2 4个顶点的不同构树的个数为 3 具有m条边的简单图的不同生成子图的个数为 4 彼得森图的点连通度为 5.n点圈的2 宽直径为 6.2n阶完全图共有 个不同的完美匹配。7.设的阶数为n，点覆盖数为，则其点独立数为 8.完全图能分解...
2019电子科技大学研究生试卷答案
一 填空题 每空3分，共15分 1.不同构的3阶简单图的个数为 4 2 图1中的最小生成树的权值为 20 3.基于图2的最优欧拉环游的总权值为。4.图3中块的个数为。5.图4中强连通分支的个数为。二 单项选择 每题3分，共15分 1 关于图的度序列，下列命题错误的是 d a 同构的两个图的度序列相同...