屈婉玲高教版离散数学部分答案2

第七章部分课后习题参考答案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}求RR-1,R{0,1,},R[{1,2}]解：RR={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R1=R1R1={a,a,a,b,a,d}R2=R2R2={b,b,c,c,c,d}R2=R2R2={b,c,c,b,b,d}R2a,d,b,c,b,d,c,b求R1R2,R2R1,R12,R23。解:R1R2={a,d,a,c,a,d}R2R1={c,d}223236．设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,b∴R是A×A上的等价关系(2)∏={{1,1,2,2,3,3,4,4},{2,1,3,2,4,3},{3,1,4,2},{4,1},{1,2,2,3,3,4},{1,3,2,4},{1,4}}41.设A={1，2，3，4}，R为AA上的二元关系,〈a，b〉，〈c，d〉AA,〈a，b〉R〈c，d〉a+b=c+d(1)证明R为等价关系.(2)求R导出的划分.(1)证明：a，b〉AAa+b=a+b∴a,bRa,b∴R是自反的任意的a,b,c,d∈A×A设a,bRc,d，则a+b=c+d∴c+d=a+b∴c,dRa,b∴R是对称的任意的a,b,c,d,x,y∈A×A若a,bRc,d,c,dRx,y则a+b=c+d,c+d=x+y∴a+b=x+y∴a,bRx,y∴R是传递的∴R是A×A上的等价关系(2)∏={{1,1},{1,2,2,1},{1,3,2,2,3,1},{1,4,4,1,2,3,3,2},{2,4,4,2,3,3},{3,4,4,3},{4,4}}43.对于下列集合与整除关系画出哈斯图:(1){1,2,3,4,6,8,12,24}(2){1,2,3,4,5,6,7,8,9,10,11,12}解:248128121046942637235111(1)1(2)45.下图是两个偏序集A,R的哈斯图.分别写出集合A和偏序关系R的集合表达式.debfcgbcdefga(a)a(b)解:(a)A={a,b,c,d,e,f,g}R={a,b,a,c,a,d,a,e,a,f,a,g,b,d,b,e,c,f,c,g}IA(b)A={a,b,c,d,e,f,g}R={a,b,a,c,a,d,a,e,a,f,d,f,e,f}IA46.分别画出下列各偏序集A,R的哈斯图,并找出A的极大元`极小元`最大元和最小元.(1)A={a,b,c,d,e}R={a,d,a,c,a,b,a,e,b,e,c,e,d,e}IA.，解：(1)1(2)A={a,b,c,d,e},R={c,d}IA.解:edbcdea(1)项目极大元:极小元:最大元:最小元:(1)eaeaabc(2)(2)a,b,d,ea,b,c,e无无第十四章部分课后习题参考答案5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G至少有多少个顶点？在最少顶点的情况下，写出度数列、(G)、(G)。解：由握手定理图G的度数之和为：210203度与4度顶点各2个，这4个顶点的度数之和为14度。其余顶点的度数共有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)18、设无向图中有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，度数之和为8，因而度数列为2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1对应的图不是简单图。所以从同构的观点看，4阶4条边的无向简单图只有两个：2n3m所以，G1、G2、G3至少有两个是同构的。20、已知n阶无向简单图G有m条边，试求G的补图G的边数m。解：mn(n1)2m21、无向图G如下图(1)求G的全部点割集与边割集，指出其中的割点和桥；(2)求G的点连通度k(G)与边连通度(G)。e2be3ace1de4e5e解：点割集:{a,b},(d)边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}k(G)=(G)=123、求G的点连通度k(G)、边连通度(G)与最小度数(G)。解：k(G)2、(G)3、(G)428、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况？3n2m解：得n=6,m=9.A00001，A01201010010A2000200200A04AAAA2531、设图G和它的部图G的边数分别为m和m，试确定G的阶数。解：mmn(n1)2得n118(mm)245、有向图D如图(1)求v2到v5长度为1，2，3，4的通路数；(2)求v5到v5长度为1，2，3，4的回路数；(3)求D中长度为4的通路数；(4)求D中长度小于或等于4的回路数；(5)写出D的可达矩阵。v1v2v5v4v3解：有向图D的邻接矩阵为：01100001010100000100002010200020200202320002002000440440000040404000004400023405421212525252121255224(1)v2到v5长度为1，2，3，4的通路数为0,2,0,0；(2)v5到v5长度为1，2，3，4的回路数为0,0,4,0；(3)D中长度为4的通路数为32；(4)D中长度小于或等于4的回路数10；11111111111111111111111