离散数学试卷（六）
一、 填空 15% （每小题 3分）
1、 n阶完全图结点v的度数d(v) = 。
2、 设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶点，
Nk+1个k+1度顶点，则N k = 。 3、 算式 ((a?(b*c)*d)?(e*f)的二叉树表示为
。 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、b； C、c； D、没有。
a a b c b b a c c c c c 35
离散数学试卷（六）
3、如右图 相对于完全图K5的补图为（ ）。
4、一棵无向树T有7片树叶，3个3度顶点，其余顶点均为4度。则T有（ ）4度
结点。
A、1； B、2； C、3； D、4。
5、设[A，+，·]是代数系统，其中+，·为普通加法和乘法，则A=（ ）时，[A，+，·]
是整环。
A、{x|x?2n,n?Z} ； B、{x|x?2n?1,n?Z} ； C、{x|x?0,且x?Z} ； D、{x|x?a?b45,a,b?R}。
三、证明 50%
n21、设G是（n,m）简单二部图，则m?4。（10分）
122、设G为具有n个结点的简单图，且m?(n?1)(n?2)，则G是连通图。（10分）
3、记“开”为1，“关”为0，反映电路规律的代数系统[{0，1}，+，·]的加法运算和乘法运算。如下：
+ 0 1 0 0 1 1 1 0
· 0 0 1 0 0 1 0 1 证明它是一个环，并且是一个域。（14分）
4、 [L,?,?]是一代数格，“≤”为自然偏序，则[L，≤]是偏序格。（16分）
36
离散数学试卷（六）
四、10%
设E(x1,x2,x3)?(x1?x2)?(x2?x3)?(x2?x3)是布尔代数[{0,1},?,?,?]上的一个布尔表达式，试写出E(x1,x2,x3)的析取范式和合取范式（10分）
五、10%
如下图所示的赋权图表示某七个城市v1,v2,?,v7及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。
37
离散数学试卷（六）
一、填空 15%（每小题3分）
1、n-1；2、n(k+1)-2m；3、如右图；4、0 ；5、臂力小者 二、选择 15%（每小题 3分）
三、证明 50%
1、 证：设G=（V，E）V?X?Y,X?n121题目 答案 1 D 2 C 3 A 4 A 5 D ,Y?n2,n1?n2?n n22对完全二部图有m?n1?n2?n1(n?n1)??n?n1n??(n1?2)?n24
当n1?n2时，完全二部图(n,m)的边数m有最大值
2n4
故对任意简单二部图(n,m)有m?n4。
2、 证：反证法：若G不连通，不妨设G可分成两个连通分支G1、G2，假设G1和G2的顶
点数分别为n1和n2，显然n1?n2?n ?n1?1n2?1?n1?n?1n2?n?1
?m?n1(n1?1)2?n2(n2?1)2?(n?1)(n1?n2?2)2?(n?1)(n?2)2
与假设矛盾。所以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。
38
离散数学试卷（六）
逆：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 。
③·对+的分配律 ?x,y?{0,1} Ⅰ 0·（x+y）=0=0+0=(0·x)+(0·y)； Ⅱ 1·（x+y） 当x=y (x+y)=0 则
?0?0??(1?0)?(1?0)?1?(x?y)?1?0?0???????(1?x)?(1?y)；
1?1(1?1)?(1?1)????当x?y（x?y?1）则
?1?0??(1?1)?(1?0)?1?(x?y)?1?1?1???????(1?x)?(1?y)
?0?1??(1?0)?(1?1)?所以?x,y,z?{0,1}均有z?(x?y)?(z?x)?(z?y) 同理可证：(x?y)?z?(x?z)?(y?z) 所以·对+ 是可分配的。
由①②③得，[{0，1}，+，·]是环。 （2）[{0，1}，+，·]是域
因为[{0，1}，+，·]是有限环，故只需证明是整环即可。 ①乘交环： 由乘法运算表的对称性知，乘法可交换。 ②含幺环：乘法的幺元是1 ③无零因子：1·1=1≠0
因此[{0，1}，+，·]是整环，故它是域。
4、证：（1 ）“≤”是偏序关系， ≤ 自然偏序 ?a,b?L①反自反性：由代数格幂等关系：a?a?a?a?a。 ②反对称性：?a,b?L 若 a?b,b?a 即：a?b?a,
39
a?b?a
b?a?b，
