《20年12月西南大学《离散数学》00004大作业》由会员分享，可在线阅读，更多相关《20年12月西南大学《离散数学》00004大作业（3页珍藏版）》请在金锄头文库上搜索。
1、西南大学培训与继续教育学院课程考试试题卷学期： 2020年秋季 课程名称 【编号】： 离散数学【0004】 A卷考试类别:大作业 满分：100分一、 大作业题目 1.请给出集合A上的关系R的定义. 设A = 0, 1, 2, 3, 4，A上的关系R= x,y|x=y+1或y= x2 ，试用列举法求出R.解：A = 0, 1, 2, 3, 4，（x，y）A，且满足x=y+1或y=x/2x=y+1时 y=x/2时当x=1时，y=0；当x=2时，y=1； 当x=2时，y=1；当x=4时，y=2当x=3时，y=2；当x=4时，y=3； 当x=0时，y=0R=（1,0），（2,1），（3,2），（4,2
2、），（4,3），（0,0）2. 请给出命题逻辑的研究对象，并将“如果张三和李四都不去,那么我就去”符号化.3. 请给出两个整数m和n的最大公因数gcd(m, n)的定义，并使用欧几里得算法计算gcd(119, 35).第一步：如果n=0，返回m的值作为结果，同时过程结束；否则进入第二步第二步：m除以n，将余数赋给r第三步：将n的值赋给m，将r的值赋给n，返回第一步算法 Euclid(119,35) /使用欧几里德算法计算gcd(119,35) /输入：两个不全为0的非负整数119，35 /输出：119，35的最大公约数 if n=0 return n while n!=0 do r119 mo
3、d 35 mn=35 nr=14return n4. 解释无向图G中节点v的度数deg(v)的含义. 设无向图G是一个 (n, m)图且2n 3 = m, 若G的每个节点度数均为3，求n和m各是多少? 5. 给出平面图的定义. 若G是边数的简单平面图，则G中必存在节点使得.解：能够画在平面上，任何两条边除了端点之外没有其他交点，这样的图叫做平面图，但有的图表面有交点，只要改变画法就会没有交点，这样的图也是平面图。证明：假设G(V,E)，任意的ai V，都有deg(ai) 5, 则deg(ai) 5n, 根据握手定理 deg(ai) = 2m，故2m 5n，即m 5n/2，与平面图 m 5n/2-5 矛盾，所以假设不成立。 二、大作业要求大作业共需要完成三道题：第1题必做，满分30分；第2-3题选作一题，满分30分；第4-5题选作一题，满分40分.- 3 -
