发布时间 : 星期三 文章《离散数学》题库及答案更新完毕开始阅读
由吸收律、分配律和交换律有
b=b?(a
?b)＝b?(a?c)=（b?a）?（b?c） ?(b?c)=c?(a?b)= c?(a?c)＝c。
=(a?c)
83、证明：在有补分配格中，每个元素的补元一定惟一。 证明：
设
a?b=1,a?c=1,a
?b=0,a?c=0。
由吸收律、分配律和交换律有
b= b?0＝b?(ac= c?0=c?(a
?c)=(b?a)?(b?c)=1?(b?c)=b?c,
?b)＝(c?a)?(c?b)=1?(c?b)=c?b。
故b=c。从而每个元素的补元是惟一的。
84、设
(a?b)?c?a?(b?c) 证明：
?设L是分配格。对?a,b,c?L，有
(a?b)?c=(a?c)?(b?c)
因为a?c?a，故(a?c)?(b?c) ?a?(b?c)。从而
(a?b)?c?a?(b?c)
?对?a,b,c?L，因为a?c?a,a?c? c,a? a?b,b?c? c,b?c? b,b? a?b,所以a?c?
a?b，a?c c，b?c c,b?c
?? a?b，
从而(a?c)?(b?c)?(a?b)?c。
???又由已知有
(a?b)?c=((b?a)?c)?c(b?(a?c))?c=((a?c)?b)?c(a?c)?(b?c)。
故(a?b)c=((a?c)?b)?c(a?c)?(b?c)。 从而L是分配格。
85、设
a+b=(a⊙b′)
证明：
?a,b?S，?＜S,?,⊙,′,0,1>是一布尔代数，
???(a′⊙b)。
? ?
a+b=(a⊙b′)
?(a′⊙b)= (b⊙a′)?(b′⊙a)=b+a。
?(a′⊙b))+c
运算+满足交换律。
?a,b,c?S，(a+b)+c=((a⊙b′)
=(((a⊙b′)
?(a′⊙b))⊙c′)?(((a⊙b′)?(a′⊙b))′⊙c)
37
=(a⊙b′⊙c′) =(a⊙b′⊙c′)
=(a⊙b′⊙c′)
?(a′⊙b⊙c′) ?((a′?b)⊙(a?b′)⊙c) ?(a′⊙b⊙c′)?(((a′⊙b′)?(b⊙a))) ⊙c) ?(a′⊙b⊙c′)? (a′⊙b′⊙c) ?(a⊙b⊙c) ?(c′⊙b⊙a′)? (c′⊙b′⊙a) ?(c⊙b⊙a) ?(a′⊙b⊙c′)? (a′⊙b′⊙c) ?(a⊙b⊙c)
a+(b+c)=(c+b)+a =(c⊙b′⊙a′)=(a⊙b′⊙c′) =(a+b)+c
? ? ? ? ?
运算+满足结合律。
?a?S，?＜S,?,⊙,′,0,1>是一布尔代数，
a+0=(a⊙0′)
?(a′⊙0)= (a⊙1)?0=a。
0关于运算+的单位元。
?a?S，?＜S,?,⊙,′,0,1>是一布尔代数，
a+a=(a⊙a′)
?(a′⊙a)=0?0=0。
a是a关于运算+的逆元。
综上所述，
86、设
?b=b}是S上的偏序关系。
?a?S，??满足等幂律，? a?a=a，故aRa。即R是自反的。
?a,b?S，若aRb且bRa,? ?满足交换律，? b=a?b=b?a=a。即R是反对称的。 ?a,b,c?S，若aRb且bRc,? ?满足结合律，? c=c?b=c?（b?a）
=(c?b)?a=c?a,故aRc。即R是反对称的。
综上所述，R={
87、设
?a?S，因为⊙满足等幂律，所以a⊙a=a，故a?a。即?是自反的。
?a,b?S，若a?b且b?a,因为⊙满足交换律，所以a=a⊙b=b⊙a=b。即?是反对称的。
?a,b,c?S，若a?b且b?c,因为⊙满足结合律，因为a=a⊙b=a⊙(b⊙c)=(a⊙b)⊙c=a⊙c,故a?c。
即?是反对称的。
综上所述，?={
（图论部分）
88、证明在有n个结点的树中，其结点度数之和是2n-2。 证明：
设T=
38
88、任一图中度数为奇数的结点是偶数个。 证明：
设G=〈V,E〉是任一图。设|V|=n。 由欧拉握手定理可得
?v?Vdeg(v)=2|E|可得，图中所有结点度数之和是偶数。显然所有偶数度结点的度
数之和仍为偶数，从而所有奇数度结点的度数之和也是偶数。因此，图中度数为奇数的结点一定为偶数个。 89、连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗？若是对的请证明之，否则请举例说明。 证明：
不对。
反例如下：若G 本身是一棵树时，则G的每一条边都不可能是G的任一棵生成树（实际上只有惟一一棵）的弦。
90、设T=
（用反证法证明）设|V|=n。
因为T=〈V,E〉是一棵树，所以|E|=n-1。 由欧拉握手定理可得
?v?Vdeg(v)=2|E|=2n-2。
假设T中最多只有1片树叶，则得出矛盾。
91、画一个使它分别满足： (1) 有欧拉回路和哈密尔顿回路；
?v?Vdeg(v)?2(n-1)+1>2n-2。
(2) 有欧拉回路，但无条哈密尔顿回路； (3) 无欧拉回路，但有哈密尔顿回路； (4) 既无欧拉回路，又无哈密尔顿回路。 解
? ? ? ? ?
? ? ? ?
? ? ? ? ? ?
? ? ? ?
92、设无向图G=
设G中度数小于3的顶点有k个，由欧拉握手定理 24=
?deg(v)
v?V知，度数小于3 的顶点度数之和为6。故当其余的顶点度数都为2时，G的顶点最少。即G中至少有9个顶点。 93、设图G=
39
证明：
由已知可知，G中k+1度顶点为n-nk个。再由欧拉握手定理可知 2m=
?deg(v)=kn+(k+1)(n-n)=(k+1)n+-n
k
k
k
v?V故nk=(k+1)-2m。
94、设G=
(用反证法证明） 设|V|=n，则|E|=n-1。 由欧拉握手定理可得
?v?Vdeg(v)=2|E|=2n-2。
因为G连通，所以?v?V，deg(v)?1。假设G中没有1片树叶，则得出矛盾。
95、若n阶连通图中恰有n-1 条边，则图中至少有一个结点度数为1。 证明：
（用反证法证明）设G=
?v?Vdeg(v)?2n>2n-2。
?v?Vdeg(v)=2|E|=2n-2。
因为G是连通图，所以G中任一结点的度数都大于等于1。
假设G中不存在度数为1 的结点，则G中任一结点的度数都大于等于2.故得出矛盾。
96、若G有n个结点，m条边，f个面，且每个面至少由k(k?3)条边围成，则 m?k(ｎ－2)／(ｋ－2)。 证明：
设连通简单无向平面图G=〈V,E,F〉，则|V|=n,|E|=m,|F|=p。 由已知对任一f?F, deg(f)?k。 由公式
?v?Vdeg(v)?2(n-1)+1>2n-2,
?deg(f)=2|E|可得，2|E|
?k|F|。
2|E|?2。 kf?F再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+即k(n-2)
?(k-2)m。
所以m?k(ｎ－2)／(ｋ－2)。
97、设G=
记|E|=m。因为G=
3k?2m
再由欧拉公式|V|-|E|+|F|=2有
40
?deg(f)=2|E|可
f?F