一．填空题(每空2分，共20分)
1． n阶简单正则图g的补图的边数为___
2．4个顶点的不同构树的个数为___
3．具有m条边的简单图的不同生成子图的个数为___
4．彼得森图的点连通度为___
5. n点圈的2—宽直径为___
6. 2n阶完全图共有___个不同的完美匹配。
7. 设的阶数为n，点覆盖数为，则其点独立数为___
8. 完全图能分解为个边不重合的二因子之并。
9. 拉姆齐数=。
10. n完全图的不同定向方式有种。
二．单项选择(每题3分，共15分)
1．下面说法错误的是( )
(a) 在正常点着色下，图中的一个色组，在其补图中的点导出子图必为一个完全子图；
b) 若图不连通，则其补图必连通；
(c) 存在14阶的自补图；
(d) 6阶图的补图可能是可平面图。
2．下列说法错误的是（ ）
(a) 一个非平凡图是偶图，当且仅当它不含有奇圈；
b) 超立方体图(方体，)是偶图；
(c) 非平凡森林是偶图；
(d) 不含三角形的图都是偶图。
3.下面说法正确的是( )
a) k连通图的连通度一定为k；
b) 完全图一定没有割边；
c)阶图是块，则中无环，且任意两点均位于同一圈上；
(d) 非平凡树一定有割点。
4.下列说法错误的是( )
a) 若图g是哈密尔顿图，则其闭包一定为完全图；
b) 设阶单图的任意两个不邻接顶点与满足，则其闭包一定为完全图；
c)若(n,m)单图g的边数，且，则g是哈密尔顿图；
d) 若g是的非h单图，则g度弱于某个图。
5.下列说法错误的是( )
(a) 若(n,m)图g是极大可平面图，则；
(b) 极大外平面图的外部面边界一定为圈；
(c) 平面图的外部面只有一个；
(d)平面图的对偶图的对偶图与是同构的。
三、 (10分)求证：任意图中奇度点个数一定为偶数。
四，(10分) 求证：非平凡树至少有两片树叶。
五．(10分) 求证：(1)、若g中每个顶点度数均为偶数，则g没有割边；
(2)、若g为的k正则偶图，则g没有割边。
六。(10分)求出下图的最小生成树，并计算权值(不要中间过程，在原图中用波浪边标出最小生成树)
七、(8分) 设图有10个4度顶点和8个5度顶点，其余顶点度数均为7。求7度顶点的最大数量，使得保持其可平面性。
解：分两种情况讨论：(1)、若g是非简单图，则容易知道，满足条件的7度顶点数可以为无穷多。
2)、若g是简单图。
设7度顶点的数量是。由握手定理：
另一方面：欲使保持其可平面性，必有。
即： ，得。
八、(7分)如果边赋权图中只有两个奇度顶点，如何构造一条最优欧拉环游？说明构造理由。
九．(10分)求下图g的色多项式pk(g).并求出点色数。
电子科技大学研究生试卷
考试时间至共 2 小时 课程名称 数字信号处理 教师学时 40 学分 2 教学方式考核日期年月日成绩。考核方式 开卷 1 20分 一个连续信号的数字处理系统如图 a 所示，具有带限的频谱，如图 b 所示。对其以nyquist采样率进行采样。频率响应为的数字理想高通如图 c 所示。分别做出，和的频谱图...
2019电子科技大学研究生试卷
一 填空题 每空3分，共15分 1.不同构的3阶简单图的个数为 2 图1中的最小生成树的权值为 3.基于图2的最优欧拉环游的总权值为。4.图3中块的个数为。5.图4中强连通分支的个数为。二 单项选择 每题3分，共15分 1 关于图的度序列，下列命题错误的是 a 同构的两个图的度序列相同 b 非负整数...
2019电子科技大学研究生试卷答案
一 填空题 每空3分，共15分 1.不同构的3阶简单图的个数为 4 2 图1中的最小生成树的权值为 20 3.基于图2的最优欧拉环游的总权值为。4.图3中块的个数为。5.图4中强连通分支的个数为。二 单项选择 每题3分，共15分 1 关于图的度序列，下列命题错误的是 d a 同构的两个图的度序列相同...