电大离散数学计算题参考题

四、计算题1．设G=V，E，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，试(1)给出G的图形表示；(2)写出其邻接矩阵；(3)求出每个结点的度数；(4)画出其补图的图形．解：(1)因为V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，所以G的图形表示为：（2）邻接矩阵：0110010110110110110000100(3)由G的图形可知，v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2(4)由关于补图的定义3.1.9可知，先画出完全图（见图1），然后去掉原图，可得补图（见图2）如下：2．图G=V,E，其中V={a,b,c,d,e}，E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(c,d),(d,e)}，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．解（1）因为V={a,b,c,d,e}，E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(c,d),(d,e)}，所以G的图形如右图表示．（2）由图得图G的邻接矩阵为：0110110011100110110111110A（3）图G有5个结点，其生成树有4条边，用Kruskal算法（避圈法）求其权最小的生成树T：第1步，取具最小权1的边(a,c)；第2步，取剩余边中具最小权1的边(c,e)；第3步，取剩余边中不与前2条边构成回路的具最小权2的边(a,b)；第4步，取剩余边中不与前3条边构成回路的具最小权3的边(b,d)．所求最小生成树T如右下图，其权为．()11237WT3．设有一组权为2,3,5,7,17,31，试画出相应的最优二叉树，计算该最优二叉树的权．解：方法（Huffman）：从2,3,5,7,17,31中选2,3为最低层结点，并从权数中删去，再添上他们的和数，即5,5,7,17,31；再从5,5,7,17,31中选5,5为倒数第2层结点，并从上述数列中删去，再添上他们的和数，即7,10,17,31；然后，从7,10,17,31中选7,10为倒数第3层结点，并从上述数列中删去，再添上他们的和数，即17,17,31；……最优二叉树如右图所示．最优二叉树权值为：25+35+54+73+172+311=10+15+20+21+34+31=131例3给定如图3.3.3所示有向图，其邻接矩阵以及邻接矩阵的乘积如下：32755173410173165v1v5v2v3v4v1v5v2v3v4v1v5v2v3v4cabed12216435cabed12130100010000000100010100010A，10000010000010100020001012A01000100000002000202000203A，10000010000020200040002024A从上面的矩阵中可以得到一些结论，如：（1）从A2中第1行第3列的为1可知，结点v1与v3之间有一条长度为2的路；（2）从A3中第1行第2列的为2可知，v1与v2之间有2条长度为3的路；（3）从A4中第2行第2列的为4可知，在结点v2有4条长度为4的回路．四、计算题1．设集合A={{1},{2},1,2}，B={1,2,{1,2}}，试计算（1）AB；（2）A∩B；（3）A×B．解：（1）AB={{1},{2},1,2}{1,2,{1,2}}={{1},{2}}（2）A∩B={{1},{2},1,2}∩{1,2,{1,2}}={1,2}（3）AB={{1},{2},1,2}{1,2,{1,2}}={{1},1,{1},2,{1},{1,2},{2},1,{2},2,{2},{1,2},1,1,1,2,1,{1,2},2,1,2,2,2,{1,2}}2．设A={1，2，3，4，5}，R={x，y|xA，yA且x+y4}，S={x，y|xA，yA且x+y0}，试求R，S，RS，SR，R-1，S-1，r(S)，s(R)．解：R={1,1,1,2,1,3,2,1,2,2,3,1},S=，RS=，SR=，R-1=R，S-1=，r(S)=IA．s(R)={1,1,1,2,1,3,2,1,2,2,3,1}3．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}．（1）写出关系R的表示式；（2）画出关系R的哈斯图；（3）求出集合B的最大元、最小元．解：（1）R=I{1,2,1,3,1,4,1,5,1,6,1,7,1,8,2,4,2,6,2,8,3,6,4,8}（2）关系R的哈斯图如下图所示（3）集合B没有最大元，最小元是：2．1．求PQR的析取范式，合取范式、主析取范式，主合取范式．解PQRPQR（析取范式、合取范式、主合取范式）(P(QQ)(RR))((PP)Q(RR))((PP)(QQ)R)（补齐命题变项）(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（对的分配律）(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)（主析取范式）2．设谓词公式()((,)()(,,))()(,)xPxyzQyxzyRyz．（1）试写出量词的辖域；（2）指出该公式的自由变元和约束变元．解（1）量词x的辖域为(,)(,,)PxyzQyxz，z的辖域为(,,)Qyxz，y的辖域为(,)Ryz．（2）自由变元为(,)(,,)PxyzQyxz中的y，(,)Ryz中的z．约束变元为(,)(,,)PxyzQyxz中的x，(,,)Qyxz中的z，(,)Ryz中的y．3．设个体域为D={a1,a2}，求谓词公式yxP(x,y)消去量词后的等值式．解：yxP(x,y)(xP(x,a1))(xP(x,a2))(P(a1,a1)P(a2,a1))(P(a1,a2)P(a2,a2))2．设集合A={1,2,3,4}，B={2,4,6,8}，判断下列关系f：A→B是否构成函数，并说明理由．(1)f={1,4,2,2,,4,6,1,8}；(2)f={1,6,3,4,2,2}；(3)f={1,8,2,6,3,4,4,2,}．解：(1)f不能构成函数．因为A中的元素3在f中没有出现．(2)f不能构成函数．因为A中的元素4在f中没有出现．(3)f可以构成函数．因为f的定义域就是A，且A中的每一个元素都有B中的唯一一个元素与其对应，满足函数定义的条件．v1v5v2v3v4图3.3.3例3图12346578关系R的哈斯图