离散复习题

1,使用Dijkstra法，求出下图顶点A到其余顶点的最短路径。（在表格中体现该算法的求解步骤）。tABCDEF1(0,λ)*(+∞,λ)(+∞,λ)(+∞,λ)(+∞,λ)(+∞,λ)2(6,A)(3,A)*(+∞,λ)(+∞,λ)(+∞,λ)3(5,C)*(6,C)(9,C)(+∞,λ)4(6,C)*(9,C)(14,D)5(7,D)*(14,D)6(12,E)*2、一个n(n=2)阶无向简单图G中，r为奇数，已知G中有r个奇数顶点，请证明G中有r个奇度数顶点解：由G得补图G定义可知，G∪G为nK由于n为奇数，所以nK中各顶点的度数n-1为偶数对于图G的任意结点v应有v也是G的顶点deg(v)+deg(v)=n-1(第一个deg(v)代表的是图G，第二个代表Gn-1为偶数，所以G中有r个奇数度节点同理在G中偶数度顶点在G中仍为偶数度顶点则G中也有r个奇度数顶点3、已知A={3，4}，B={1，2,3}求A到B的所有函数。并指出入射函数。解：F1={3,1,4,1},F2={3,1,4,2},F3={3,1,4,3},F4={3,2,4,1},F5={3,2,4,2},F6={3,2,4,3},F7={3,3,4,1},F8={3,3,4,2},F9={3,3,4,3},函数性质：1，满射，无。2，单射，f2,f3,f4,f6,f7,f84、已知G有21条边，4个3度顶点，其余顶点度数至少为5，求G图最多几个顶点？解：由题目可知共有21*2=42个度剩余度数为42-3*4=3030÷5=6所以最多6+4=10个顶点5、设A={a,b,c},求p（A）*A解：={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}所以={,a,,b,,c,,a,,b,,c,,a,,b,,c,,a,,b,,c,,a,,b,,c,,a,,b,,c,,a,,b,,c,{a,b,c},a,{a,b,c},b,{a,b,c},c}6、求1至200之间不能被2,3,5整除的元素个数。解：设能被2，3，5整除的数字集合为A,B,C[A]=[200/2]=100[B]=[200/3]=66[C]=[200/5]=40[A∩B]=[200/6]=33[A∩C]=[200/10]=20[B∩C]=[200/15]=13[A∩B∩C]=[200/30]=6[A∪B∪C]=100+66+40-33-20-13+6=146所以不能被2，3，5整除的个数为200-146=547、已知S=},R为A上关系，则此关系共有多少种？如果R1,R2为R上关系，且分别为R1={a,a,a,bc,a},R2={a,b,b,c},分别求出r(R1)，S(R1)，R1R2,R2R1，t(R1)，解：232=512种r(R1)=R1∪R1={a,a,a,b,c,a}∪{a,a,b,b,c,c}={a,a,b,b,c,c,a,b,c,a}S(R1)=R1∪11R={a,a,a,b,c,a}∪{a,a,b,a,a,c}={a,a,a,b,c,a,b,a,a,c}R1R2={a,b,a,c,c,b}R2R1={b,a,b,b}t(R1)=R1∪21R∪31R因为21R={a,a,a,b,c,a,c,b}31R={a,a,a,b,c,a,c,b}所以t(R1)={a,a,a,b,c,a,c,b}8、∃x(F(x)→∀yG(x,y,z))∨∃zH(x,y,z)解：⇒∃x∀y(F(x)→G(x,y,z))∨∃zH(x,y,z)⇒∃x∀y((F(x)→G(x,y,z))∨∃zH(x,y,z))⇒∃x∀y∃z((F(x)→G(x,y,z))∨H(x,y,z))9、设个体域D={2,3},则请消去公式中的量词.∃x∀yF(y,x)⇒∃x(F(2,x)∧F(3,x))⇒(F(2,2)∧F(3,2))∨(F(2,3)∧F(3,3))10、求下列各式的主析取范式，主合取范式¬(¬p→q)∨r解：主析取范式：⇒¬(p∨q)∨r⇒(¬p∧¬q)∨r⇒((¬p∧¬q)∧(r∧¬r))∨(r∧(p∨¬p)⇒(¬p∧¬q∧¬r)∨(¬p∧¬q∧r)∨(p∧¬q∧r)∨(p∧q∧r)∨(¬p∧¬q∧r)⇒0m∨1m∨3m∨5m∨7m所以主合取范式：2M∧4M∧6M11、求出下图的邻接矩阵,求出0V到2V长度小于3的所有通路个数解：邻接矩阵为A(D)=0111001000101100，21120001000100121A所以通路个数为1+2=312、构造下面推理的证明前提：结论：证明：○1p○2p○3T○1○2○4p○5T○4⑥T○3○513、设A={2，3，4，5，6，8，9}，如果R是A上的模5同余关系，请写出R及A中每个元素的等价类。21、已知无向树T中,有1个3度顶点,2个2度顶点,其余顶点全是树叶.试求树叶数,并画出满足要求的非同构的无向树.解用树的性质m=n1和握手定理.设有x片树叶，于是n=1+2+x=3+x,2m=2(2+x)=13+22+x解得x=3，故T有3片树叶.22、已知无向树T有5片树叶,2度与3度顶点各1个,其余顶点的度数均为4.求T的阶数n,并画出满足要求的所有非同构的无向树.解设T的阶数为n,则边数为n1,4度顶点的个数为n7.由握手定理得2m=2(n1)=51+21+31+4(n7)解得n=8,4度顶点为1个.1设集合A={2,{a},3,4}，B={{a},3,4,1}，E为全集，则下列命题正确的是()。(A){2}A(B){a}A(C){{a}}BE(D){{a},1,3,4}B.2设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备().(A)自反性(B)传递性(C)对称性(D)反对称性3设半序集(A,≤)关系≤的哈斯图如下所示，若A的子集B={2,3,4,5},则元素6为B的()。(A)下界(B)上界(C)最小上界(D)以上答案都不对4下列语句中，()是命题。(A)请把门关上(B)地球外的星球上也有人(C)x+56(D)下午有会吗？5设I是如下一个解释：D＝{a,b},0101b)P(b,a)P(b,b)P(a,),(aaP则在解释I下取真值为1的公式是().(A)xyP(x,y)(B)xyP(x,y)(C)xP(x,x)(D)xyP(x,y).6.若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是().(A)(1,2,2,3,4,5)(B)(1,2,3,4,5,5)(C)(1,1,1,2,3)(D)(2,3,3,4,5,6).7.设G、H是一阶逻辑公式，P是一个谓词，G＝xP(x),H＝xP(x),则一阶逻辑公式GH是().(A)恒真的(B)恒假的(C)可满足的(D)前束范式.8设命题公式G＝(PQ)，H＝P(QP)，则G与H的关系是()。(A)GH(B)HG(C)G＝H(D)以上都不是.9设A,B为集合，当()时A－B＝B.(A)A＝B(B)AB(C)BA(D)A＝B＝.10设集合A={1,2,3,4},A上的关系R＝{(1,1),(2,3),(2,4),(3,4)},则R具有()。(A)自反性(B)传递性(C)对称性(D)以上答案都不对11下列关于集合的表示中正确的为()。(A){a}{a,b,c}(B){a}{a,b,c}(C){a,b,c}(D){a,b}{a,b,c}12命题xG(x)取真值1的充分必要条件是().(A)对任意x，G(x)都取真值1.(B)有一个x0，使G(x0)取真值1.(C)有某些x，使G(x0)取真值1.(D)以上答案都不对.13.设G是连通平面图，有5个顶点，6个面，则G的边数是().(A)9条(B)5条(C)6条(D)11条.14.设G是5个顶点的完全图，则从G中删去()条边可以得到树.(A)6(B)5(C)10(D)4.15.设图G的相邻矩阵为0110110101110110010111110，则G的顶点数与边数分别为().(A)4,5(B)5,6(C)4,10(D)5,8.16.与命题公式)(RQP等价的公式是（）（A）RQP)(（B）RQP)(（C）)(RQP（D）)(RQP17.设集合cbaA,,,A上的二元关系bbaaR,,,不具备关系()性质（A）(A)传递性(B)反对称性(C)对称性(D)自反性18.在图EVG,中,结点总度数与边数的关系是()(A)Evi2)deg((B)Evi)deg((C)VviEv2)deg((D)VviEv)deg(19.设D是有n个结点的有向完全图,则图D的边数为()(A))1(nn(B))1(nn(C)2/)1(nn(D)2/)1(nn20.无向图G是欧拉图,当且仅当()(A)G的所有结点的度数都是偶数(B)G的所有结点的度数都是奇数（C）G连通且所有结点的度数都是偶数(D)G连通且G的所有结点度数都是奇数。1.C.2.D.3.B.4.B.5.D.6.C.7.C.8.A.9.D.10.B.11.B.13.A.14.A.15.D16B17D18C19A20C1.计算机系期末要安排7门公共课的考试，课程编号为1到7。下列每一对课程有学生同时选修：1和2，1和3，1和4，1和7，2和3，2和4，2和5，2和7，3和4，3和6，3和7，4和5，4和6，5和6，5和7，6和7。这7门课的考试至少要安排在几个不同的时间段？给出一个安排方案。解：由题意可设G=,VE,其中V有7个结点分别表示7门公共课考试的课程编号，若Vi,Vjv，且Vi,Vj表示有学生同时选修每一对课程，则,vivjE，由此可画图G为：该问题转化为G图的着色问题，可得：这7门课的考试至少要安排在4个不同的时间段1和5可以安排在同一时间段T1;2和6可以安排在同一时间段T2;3可以安排在时间段T3;4和7可以安排在同一时间段T4;2.假设两家电视台相距不超过150千米就不能使用相同的频率，表5-5列出6家电视台之间的距离，它们至少需要使用多少不同的频率？如何分配？23456185175200501002125175100160310020025042102205100解：由题意可设G=,VE,其中V有6个结点分别表示6家电视台，若Vi,Vjv，且Vi,Vj间距离小于150千米，则,vivjE，由此可画图G为：1321234567该问题转化为G图的着色问题，可得：它们至少需要使用3种不同的频率1和3可为同一频率f1;2,4,6可为同一频率f2;5为频率f3；3.证明定理6.12证明：（1）设G连通的平面图，且每个面的次数至少为l（l=3），G中顶点数为n，边数为m，面数为r由定理6.9可知lr=2m把欧拉公式n-m+r=2代入得l(2-n+m)=2m化简得m(l-2)=ln-2l所以m=l(n-2)/l-2得证（2）设G是p(p2)个连通分支的平面图，每个面的次数至少为l（l=3），G中顶点数为n，边数为m，面数为r由定理6.9可知lr=2m把欧拉公式的推广n-m+r=p+1代入lr=2m得l(p+1-n+m)=2m化简得m(l-2)=ln-l-lp所以m=l(n-p-1)/(l-2)得证4、某工厂生产由6种不同颜色的纱织成的双色布。已知在品种中，每种颜色至少分别和其他5种颜色中的3种颜色搭配，证明可以挑出3种双