成都理工大学2012－2013学年第二学期
《离散数学》考试试卷
大题 一 得分 得分二 三 四 五 六 七 八 九 十 总分 一、填空题（本大题共10小题，每小题2分，共20分）
1、设G为9阶无向图，每个结点度数不是5就是6，则G中至少有个5度结点。 2、n阶完全图，Kn的点数X (Kn) = 。
3、有向图中从v1到v2长度为2的通路有条。
4、设[R，+，·]是代数系统，如果①[R，+]是交换群②[R，·]是半群 ③则称[R，+，·]为环。
5、设[L,?,?]是代数系统，则[L,?,?]满足幂等律，即对?a?L有。
6. A上的关系R是自反的、对称和传递的，称R是A上的??等价关系?????????。 7. 群是一个存在二元运算可结合，存在???单位元???????，每个元素存在???????逆元?????的代数。
8. 若h是A=〈S，?〉到A′=〈S′，?′〉的同态，则h（a?b）=?h（a）?′h（b）。 9.〈R，+，?〉是环，则〈R，+〉是交换群，〈R，?〉是?半群?。
10．一个无向图的欧拉回路要求经过图中___每条_边_____一次且仅一次，哈密尔顿回
路要求经过图中___每个顶点______一次且仅一次。
二、选择题（本大题共10小题，每小题2分，共20分）
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、下列偏序集（）能构成格。
s?{1,5、设
111,2,,3,,4}234，*为普通乘法，则[S，*]是（）。
A、 代数系统； B、半群； C、群； D、都不是。
6．设A = {1,2,3,4}，A上的关系R = {(1,1),(2,3),(2,4),(3,4)},则R具有( )。
A．自反性；B．传递性； C．对称性； D．以上都不是
7. 满足谓词P(x,y)：xy?0的整数集Z上的二元关系具有（）性质？ B、 A．自反、对称 B．对称、传递 C．反对称 D．反自反、对称、传递
8. V=〈{1，2，3}，*，1〉，x*y表示取x和y中较大数。下列不是V的子代数的（）。
A．〈{1，2，3}，*，1〉 B．〈{1}，*，1〉
C．〈{2，3}，*，1〉 D．〈{1，3}，*，1〉
9．给定下列各序列，不能构成无向简单图的度数序列是（）。 A．1，1，1，2，3； B ．2，2，2，2； C． 3，3，3，3； D ．1，3，3，3。 10．下列无向图中，不是二部图的是（D）。
得分三、（本大题共40分）
1、（10%）在至少有2个人的人群中，至少有2 个人，他们有相同的朋友数。 2、（8%）若图G中恰有两个奇数度顶点，则这两个顶点是连通的。 3、（8%）证明在6个结点12条边的连通平面简单图中，每个面的面数都是3。
4、（10%）证明循环群的同态像必是循环群。 5、（12%）设[B,?,?,?,0,1]是布尔代数，定义运算*为a*b?(a?b)?(a?b)，
求证[B，*]是阿贝尔群。
四、（本大题共20分） 得分1、在二叉树中
1）求带权为2，3，5，7，8的最优二叉树T。（10分） 2）求T对应的二元前缀码。（10分）
2、下图所示带权图中最优投递路线并求出投递路线长度（邮局在D点）。
答案：
一、填空
1、 6；2、n；3、2；4、+对·分配且·对+分配均成立；5、a?a?a且a?a?a。
二、选择
题目 答案
1 A,B 2 B,D 3 B 4 C 5 D 三、证明
1、（10分）证明：用n个顶点v1，…，vn表示n个人，构成顶点集V={v1，…，vn}，设
E?{uv|u,v?V,且u,v是朋友（u?v）}，无向图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 由图论基本定理知：
?deg(F)?2?m?24，而deg(F)?3，所以必有deg(F)?3，
ii即每个面用3条边围成。
4（10分）证：设循环群[A，·]的生成元为a，同态映射为f，同态像为[f（A），*]，于是
?an,am?A都有f(an?am)?f(an)*f(am)
对n=1有
f(a)?f(a)
相关推荐：
loading