屈婉玲高教版离散数学部分答案2[1](1).docx

第七章部分课后习题参考答案

7.列出集合A={2,3,4}上的恒等关系IA,全域关系EA,小于或等于关系LA,整除关系

DA.

解：IA={2，2,3,3,4,4}

EA={2,2,2,3,2,4,3,4,4,4,3,2,3,3,4,2,4,3}

LA={2,2,2,3,2,4,3,3,3,4,4,4}

DA={2,4}

13.设A={1,2,2,4,3,3}

B={1,3,2,4,4,2}

求A??B,A??B,domA,domB,dom(A??B),ranA,ranB,ran(A??B),fld(A-B).

解：A??B={1,2,2,4,3,3,1,3,4,2}

A??B={2,4}

domA={1,2,3}

domB={1,2,4}

dom(A∨B)={1,2,3,4}

ranA={2,3,4}

ranB={2,3,4}

ran(A??B)={4}

A-B={1,2,3,3}，fld(A-B)={1,2,3}

14.设R={0,10,2,0,3,1,2,1,3,2,3}

求R?R,

R-1,

R??{0,1,},

R[{1,2}]

解：R?R={0,2,0,3,1,3}

R-1,={1,0,2,0,3,0,2,1,3,1,3,2}

R??{0,1}={0,1,0,2,0,3,1,2,1,3}

R[{1,2}]=ran(R|{1,2})={2,3}

16．设A={a,b,c,d}，R1

，

R2为A上的关系，其中

R1=?a,a,a,b,b,d

?

R2????a,d,b,c,b,d,c,b

?

求R1?R2,R2?R1,R12,R23。

解:R1?R2={a,d,a,c,a,d}

R2?R1={c,d}

2

2

32

36．设A={1，2，3，4}，在A??A上定义二元关系R，

?u,v,x,y?A??A，〈u,vRx,y??u+y=x+v.

(1)证明R是A??A上的等价关系.

(2)确定由R引起的对A??A的划分.

（1）证明：∵u,vRx,y??u+y=x-y

∴u,vRx,y??u-v=x-y

?u,v?A??A

∵u-v=u-v

∴u,vRu,v

∴R是自反的

任意的u,v,x,y∈A×A

如果u,vRx,y，那么u-v=x-y

∴x-y=u-v

∴x,yRu,v

∴R是对称的

任意的u,v,x,y,a,b∈A×A

若u,vRx,y,x,yRa,b

则u-v=x-y,x-y=a-b

∴u-v=a-b

∴R是传递的

∴u,vRa,bR1=R1?R1={a,a,a,b,a,d}R2=R2

R1=R1?R1={a,a,a,b,a,d}

R2=R2?R2={b,b,c,c,c,d}

R2=R2?R2={b,c,c,b,b,d}

其余顶点的度数共有6度。

其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取

2,

所以，G至少有7个顶点,出度数列为3,3,4,4,2,2,2,??(G)??4,??(G)??2.

7、设有向图D的度数列为2，3，2，3，出度列为1，2，1，1，求D的入度列，

并求??(D),?(D)，

??(D),???(D),???(D),???(D).

解：D的度数列为2，3，2，3，出度列为1，2，1，1，D的入度列为1,1,1,2.

?(D)??3,?(D)??2,???(D)??2,???(D)??1,???(D)??2,???(D)??1

8、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该

图有多少个顶点？

解：由握手定理图G的度数之和为：2??6??12

设2度点x个，则3??1??5??1??2x??12，x??2，该图有4个顶点.

14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3

种非同构的无向图，其中至少有两个时简单图。

(1)2,2,3,3,4,4,5

(2)

2,2,2,2,3,3,4,4

解：(1)2+2+3+3+4+4+5=23

是奇数，不可图化；

(2)

2＋2+2+2+3+3+4+4=16,是偶数，可图化；

18、设有3个4阶4条边的无向简单图G1、G2、G3，证明它们至少有两个是同

构的。

证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为