《离散数学》练习题和参考答案

从而L是分配格。

85、设是一布尔代数，则是一个交换群，其中＋定义为 a+b=(a⊙b′)?(a′⊙b)。 证明：

?a,b?S，?＜S,?,⊙,′,0,1>是一布尔代数，

? a+b=(a⊙b′)?(a′⊙b)= (b⊙a′)?(b′⊙a)=b+a。 ? 运算+满足交换律。

?a,b,c?S，(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′⊙b′)?(b⊙a))) ⊙c) =(a⊙b′⊙c′)?(a′⊙b⊙c′)? (a′⊙b′⊙c) ?(a⊙b⊙c) a+(b+c)=(c+b)+a

=(c⊙b′⊙a′)?(c′⊙b⊙a′)? (c′⊙b′⊙a) ?(c⊙b⊙a) =(a⊙b′⊙c′)?(a′⊙b⊙c′)? (a′⊙b′⊙c) ?(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、设是一布尔代数，则 R={ | a?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）

41

=(c?b)?a=c?a,故aRc。即R是反对称的。 综上所述，R={ | a?b=b}是S上的偏序关系。

87、设是一布尔代数，则关系?={ | a⊙b=a}是S上的偏序关系。 证明：

?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。即?是反对称的。

综上所述，?={ | a⊙b=a}是S上的偏序关系。

（图论部分）

88、证明在有n个结点的树中，其结点度数之和是2n-2。 证明：

设T=是任一棵树，则|V|=n，且|E|=n-1。 由欧拉握手定理，树中所有结点的度数之和等于2|E|. 从而结点度数之和是2n-2。

88、任一图中度数为奇数的结点是偶数个。 证明：

设G=〈V,E〉是任一图。设|V|=n。

由欧拉握手定理可得 v?Vdeg(v)=2|E|可得，图中所有结点度数之和是偶数。显然所有偶数度结点的度数之和仍为偶数，从而所有奇数度结点的度数之和也是偶数。因此，图中度数为奇数的结点一定为偶数个。

89、连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗？若是对的请证明之，否则请举例说明。 证明： 不对。

反例如下：若G 本身是一棵树时，则G的每一条边都不可能是G的任一棵生成树（实际上只有惟一一棵）的弦。 90、设T=是一棵树，若|V|>1，则T中至少存在两片树叶。 证明：

（用反证法证明）设|V|=n。

因为T=〈V,E〉是一棵树，所以|E|=n-1。 由欧拉握手定理可得 v?Vdeg(v)=2|E|=2n-2。

假设T中最多只有1片树叶，则v?Vdeg(v)?2(n-1)+1>2n-2。 得出矛盾。

91、画一个使它分别满足：

42

???

有欧拉回路和哈密尔顿回路； 有欧拉回路，但无条哈密尔顿回路； 无欧拉回路，但有哈密尔顿回路； 既无欧拉回路，又无哈密尔顿回路。 解

? ? ? ? ?

? ? ? ?

? ? ? ? ? ?

? ? ? ?

92、设无向图G=，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？ 解：

设G中度数小于3的顶点有k个，由欧拉握手定理

24=v?V?deg(v)

知，度数小于3 的顶点度数之和为6。故当其余的顶点度数都为2时，G的顶点最少。即G中至少有9个顶点。 93、设图G=，|V|=n，|E|=m。k度顶点有nk个，且每个顶点或是k度顶点或是k+1度顶点。证明：nk=(k+1)-2m。 证明：

由已知可知，G中k+1度顶点为n-nk个。再由欧拉握手定理可知 2m=v?V?deg(v)=knk+(k+1)(n-nk)=(k+1)n+-nk

故nk=(k+1)-2m。

94、设G=是一个连通且|V|=|E|+1的图，则G中有一个度为1的结点。 证明：

(用反证法证明） 设|V|=n，则|E|=n-1。

由欧拉握手定理可得 v?Vdeg(v)=2|E|=2n-2。

因为G连通，所以?v?V，deg(v)?1。假设G中没有1片树叶，则v?Vdeg(v)?2n>2n-2。

43

??

得出矛盾。

95、若n阶连通图中恰有n-1 条边，则图中至少有一个结点度数为1。 证明：

（用反证法证明）设G=有n-1条边且|V|=n。 由欧拉握手定理可得 v?Vdeg(v)=2|E|=2n-2。

因为G是连通图，所以G中任一结点的度数都大于等于1。

假设G中不存在度数为1 的结点，则G中任一结点的度数都大于等于2.故v?Vdeg(v)?2(n-1)+1>2n-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。

由公式f?Fdeg(f)=2|E|可得，2|E|?k|F|。

???2再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+k|E|?2。

即k(n-2)?(k-2)m。 所以m?k(ｎ－2)／(ｋ－2)。

97、设G=是连通的简单平面图，|V|=n?3，面数为k,则k?2n-4。 证明：

记|E|=m。因为G=是连通的简单平面图，故每个面的度数都不小于3。从而由公式f?Fdeg(f)=2|E|可得 3k?2m

再由欧拉公式|V|-|E|+|F|=2有 m=n+k-2

?3及 2k?n+k-2

故 k?2n-4。

98、证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点。 证明：

若结点个数小于等于3时，结论显然成立。 当结点多于3 个时，用反证法证明。 记|V|=n,|E|=m,|F|=k。

44