《离散数学》题库及答案

由吸收律、分配律和交换律有

b=b?(a

?b)=b?(a?c)=(b?a)?(b?c) ?(b?c)=c?(a?b)= c?(a?c)=c。

=(a?c)

83、证明:在有补分配格中,每个元素的补元一定惟一。 证明:

是一个有补分配格。?a?L,设b和c都是a 的补元,即

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、设是格,则L是分配格当且仅当?a,b,c?L,有

(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、设是一布尔代数,则 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)

=(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。

38

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片树叶,则得出矛盾。

91、画一个使它分别满足: (1) 有欧拉回路和哈密尔顿回路;

?v?Vdeg(v)?2(n-1)+1>2n-2。

(2) 有欧拉回路,但无条哈密尔顿回路; (3) 无欧拉回路,但有哈密尔顿回路; (4) 既无欧拉回路,又无哈密尔顿回路。 解

? ? ? ? ?

? ? ? ?

? ? ? ? ? ?

? ? ? ?

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

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

?deg(v)

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

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|=|E|+1的图,则G中有一个度为1的结点。 证明:

(用反证法证明) 设|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=有n-1条边且|V|=n。 由欧拉握手定理可得

?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(n-2)/(k-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(n-2)/(k-2)。

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

记|E|=m。因为G=是连通的简单平面图,故每个面的度数都不小于3。从而由公式得

3k?2m

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

40

?deg(f)=2|E|可

f?F

联系客服:779662525#qq.com(#替换为@)