离散复习题概要.docx

1, 使用Dijkstra法，求出下图顶点A到其余顶点的最短路径。 （在表格中体现该算法的求解步骤）。 t A B C D E F 1 (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个奇数顶点，请证明中有r个奇度数顶点 解：由G得补图定义可知，G∪为 由于n为奇数，所以中各顶点的度数n-1为偶数 对于图G的任意结点v应有v也是G的顶点 deg(v)+deg(v)=n-1(第一个deg(v)代表的是图G，第二个代表 n-1为偶数，所以G中有r个奇数度节点 同理在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,f8 4、已知G有21条边，4个3度顶点，其余顶点度数至少为5，求G图最多几个顶点？ 解：由题目可知 共有21*2=42个度 剩余度数为42-3*4=30 30÷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=54 7、已知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)， 解： =512种 r(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∪ ={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∪∪ 因为={a,a,a,b,c,a,c,b} ={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) ?∨ ∨∨∨ 所以主合取范式： ∧∧ 11、求出下图的邻接矩阵,求出 到 长度小于3的所有通路个数 解： 邻接矩阵为A(D)=， 所以通路个数为1+2=3 12、构造下面推理的证明 前提： 结论：