《离散数学》考试题库及答案
试卷五试题与答案
一、填空15%（每空3分）
1、设G为9阶无向图，每个结点度数不是5就是6，则G中至少有         个5度结点。
2、n阶完全图，Kn的点数X (Kn) =                           。
3、有向图      中从v1到v2长度为2的通路有         条。
4、设[R，+，·]是代数系统，如果①[R，+]是交换 ②[R，·]是半
二叉树公式 ③                                                       则称[R，+，·]为环。
5、设是代数系统，则满足幂等律，即对有                 。
二、选择15%（每小题3分）
1、 下面四组数能构成无向简单图的度数列的有（          ）。
A、（2，2，2，2，2）；          B、（1，1，2，2，3）；
C、（1，1，2，2，2）；          D、（0，1，3，3，3）。
2、 下图中是哈密顿图的为（        ）。
3、 如果一个有向图D是强连通图，则D是欧拉图，这个命题的真值为（    ）
A、真；    B、假。
4、 下列偏序集（      ）能构成格。
5、 设，*为普通乘法，则[S，*]是（）。
A、代数系统； B、半； C、；  D、都不是。
三、证明 48%
1、（10%）在至少有2个人的人中，至少有2 个人，他们有相同的朋友数。
2、（8%）若图G中恰有两个奇数度顶点，则这两个顶点是连通的。
3、（8%）证明在6个结点12条边的连通平面简单图中， 每个面的面数都是3。
4、（10%）证明循环的同态像必是循环。
5、（12%）设是布尔代数，定义运算*为，
求证[B，*]是阿贝尔。
四、计算22%
1、在二叉树中
1） 求带权为2，3，5，7，8的最优二叉树T。（5分）
2） 求T对应的二元前缀码。（5分）
2、 下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。
答案：
一、填空（15%）每空3 分
1、 6；2、n；3、2；4、+对·分配且·对+分配均成立；5、。
二、选择（15%）每小题3分
题目
1
2
3
4
5
答案
A,B
B,D
B
C
D
三、证明（48%）
1、（10分）证明：用n个顶点v1，…，vn表示n个人，构成顶点集V={v1，…，vn}，设，无向图G=（V，E）
现证G中至少有两个结点度数相同。
事实上，（1）若G中孤立点个数大于等于2，结论成立。
（2） 若G中有一个孤立点，则G中的至少有3个顶点，既不考虑孤立点。设G中每个结点度
数均大于等于1，又因为G为简单图，所以每个顶点度数都小于等于n-1，由于G中n顶点其度数取值只能是1，2，…，n-1，由鸽巢原理，必然至少有两个结点度数是相同的。
2、（8分）证：设G中两个奇数度结点分别为u，v。若 u，v不连通则至少有两个连通分支G1、G2，使得u，v分别属于G1和G2。于是G1与G2中各含有一个奇数度结点，与握手定理矛盾。因而u，v必连通。
3（8分）证：n=6,m=12 欧拉公式n-m+f=2知 f=2-n+m=2-6-12=8
由图论基本定理知：，而，所以必有，即每个面用3条边围成。
4（10分） 证：设循环[A，·]的生成元为a，同态映射为f，同态像为[f（A），*]，于是都有
对n=1有
n=2,  有
若n=k-1时  有
对n=k时，
这表明，f(A)中每一个元素均可表示为，所以[f(A),*]为f(a) 生成的循环。
5、证：
（1） 交换律：有
（2） 结合律：有
而：
（3） 幺：有
（4） 逆： 
综上所述：[B，*]是阿贝尔。
四、计算（22%）
1、（10分）
（1）（5分）由Huffman方法,得最佳二叉树为：
（2）（5分）最佳前缀码为：000，001，01，10，11
2、（12分）
  图中奇数点为E、F ，d(E)=3,d(F)=3,d(E,F)=28 p=EGF
复制道路EG、GF，得图G‘，则G‘是欧拉图。