离散数学试卷及答案(6).doc

(完整word版)离散数学试卷及答案(6)
一、 填空 15% （每小题 3分）
1、 n阶完全图结点v的度数d(v) = 。
2、 设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶点，Nk+1个k+1度顶点，则N k = 。
3、 算式 的二叉树表示为

。
4、 如图

给出格L，则e的补元是 。
5、 一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元是 。

二、选择 15% （每小题 3分）
1、设S={0,1,2,3},≤为小于等于关系，则{S，≤}是（ ）。
A、群；B、环；C、域；D、格。
2、设[{a , b , c}，*]为代数系统，*运算如下：
*
a
b
c
a
a
b
c
b
b
a
c
c
c
c
c
则零元为（ ）。
A、a； B、b； C、c； D、没有。

3、如右图 相对于完全图K5的补图为（ ）。

4、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（ ）4度结点。
A、1； B、2； C、3； D、4。
5、设[A，+，·]是代数系统，其中+，·为普通加法和乘法，则A=（ ）时，[A，+，·]是整环。
A、 ； B、 ；
C、 ； D、。
三、证明 50%
1、设G是（n,m）简单二部图，则。（10分）
2、设G为具有n个结点的简单图，且，则G是连通图。（10分）
3、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下：
+
0
1

·
0
1
0
0
1
0
0
0
1
1
0
1
0
1
证明它是一个环，并且是一个域。（14分）
4、 是一代数格，“≤”为自然偏序，则[L，≤]是偏序格。（16分）
四、10%
设是布尔代数上的一个布尔表达式，试写出的析取范式和合取范式（10分）
五、10%
如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。

一、填空 15%（每小题3分）
1、n-1；2、n(k+1)-2m；3、如右图；4、0 ；5、臂力小者
二、选择 15%（每小题 3分）
题目
1
2
3
4
5
答案
D
C
A
A
D

三、证明 50%
1、 证：设G=（V，E）
对完全二部图有
当时，完全二部图的边数m有最大值
故对任意简单二部图有。
2、 证：反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶点数分别为n1和n2，显然

与假设矛盾。所以G连通。
3、 （1）[{0，1}，+，·]是环
①[{0，1}，+]是交换群
乘：由“+”运算表知其封闭性。由于运算表的对称性知：+运算可交换。
群： （0+0）+0=0+（0+0）=0 ；（0+0）+1=0+（0+1）=1；
（0+1）+0=0+（1+0）=1 ； （0+1）+1=0+（1+1）=0；
（1+1）+1=1+（1+1）=0 ……
结合律成立。
幺：幺元为0。
逆：0，1逆元均为其本身。
②[{0，1}，·]是半群
乘：由“· ”运算表知封闭
群： （0·0）·0=0·（0·0）=0 ；（0·0）·1=0·（0·1）= 0；
（0·1）·0=0·（1·0）=0 ； （0·1）·1=0·（1·1）=0；
（1·1）·1=1·（1·1）=0 。
③·对+的分配律
Ⅰ 0·（x+y）=0=0+0=(0·x)+(0·y)；
Ⅱ 1·（x+y）
当x=y (x+y)=0 则
；
当（）则

所以均有
同理可证：
所以·对+ 是可分配的。
由①②③得，[{0，1}，+，·]是环。
（2）[{0，1}，+，·]是域
因为[{0，1}，+，·]是有限环，故只需证明是整环即可。
①乘交环： 由乘法运算表的对称性知，乘法可交换。
②含幺环：乘法的幺元是1
③无零因子：1·1=1≠0
因此[{0，1}，+，·]是整环，故它是域。
4、证：（1 ）“≤”是偏序关系， ≤ 自然偏序
①反自反性：由代数格幂等关系：。
②反对称性： 若 即：，
则
③传递性：则：

（2）在L中存在{x,y}的下（上）确界
设则：
事实上：

若{x , y }有另一下界c，则
是{x , y }最大下界，即
同理可证上确界情况。
四、14%
解：函数表为：

0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
析取范式：
合取范式：
五、10%
解： 用库斯克（Kruskal）算法求产生的最优树。算法为：

结果如图：

树权C(T)=23+1+4+9+3+17=57（万元）即为总造价

41