成都理工大学2012-2013离散数学期末试题

成都理工大学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)

22f(a)?f(a?a)?f(a)*f(a)?(f(a))n=2, 有 k?1k?1f(a)?(f(a))若n=k-1时有

kk?1k?1k?1kf(a)?f(a?a)?f(a)*f(a)?(f(a))*f(a)?(f(a))对n=k时， n(f(a))这表明，f(A)中每一个元素均可表示为，所以[f(A),*]为f(a) 生成的循环群。

5、证：

（1） 交换律：（2） 结合律：

?a,b?B有a*b?(a?b)?(a?b)?(b?a)?(b?a)?b*a ?a,b,c?B有

(a*b)*c?((a?b)?(a?b))*c?(((a?b)?(a?b))?c)?((a?b)?(a?b))?c?(a?b?c?a?b?c)?((a?b)?(a?b))?c?a?b?c?a?b?c?(a?a?a?b?b?a?b?b)?c?a?b?c?a?b?c?b?a?c?a?b?c?a?b?c?a?b?c?a?b?c?a?b?c而：

a*(b*c)?a*((b?c)?(b?c))?(a?(b?c)?(b?c))?((a?(b?c)?(b?c))?a?(b?c)?(b?c)?a?b?c?a?b?c?a?b?c?a?b?c?a?b?c?a?b?c?(a*b)*c?a*(b*c)

（3） 幺：?a?B有

a*0?(a?0)?(a?0)?a?0?a0*a?(0?a)?(0?a)?0?a?a

?0是[B，*]幺元。

（4） 逆：?a?Ba*a?(a?a)?(a?a)?0?0?0

?a是a的逆元。

综上所述：[B，*]是阿贝尔群。

四、计算

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‘

是欧拉图。 由D开始找一条欧拉回路：DEGFGEBACBDCFD。 道路长度为：

35+8+20+20+8+40+30+50+19+6+12+10+23=281。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库成都理工大学2012-2013离散数学期末试题在线全文阅读。