离散数学考试题及答案

无向树满足边数e等于顶点数n-1，而所有顶点的度数相加等于边数的2倍2e只有B满足：节点数n=8，所有度数相加为14，则边数e=14/2=7，恰好为n-1无向完全图任意两点之间都有一条边，则边数为C(n,2)=n(n-1)/2，选C图看不清，但这是不重复遍历所有边的一笔画问题。只要所有顶点的度都为偶数，或者仅有两个奇数度顶点，则可以一笔画。假设图中最上面三个点从左到右依次为A、B、C，那么A和C是图中唯二的奇数度顶点，从A到C可以一笔画，也即通过的边数最少。而从B到C不能一笔画，必须重复经过某些边。因此从A出发的甲先到达目的地CA和D无法不重复的遍历所有顶点，B可以但无法回到起点，C从最下面的点出发，可以不重复的经过每个点再回到起点，满足题意，选C关系R：A中模2同余的两个元素。[2]ʀ表示2形成的R等价类，即A中与2模2同余的所有元素，即A中所有偶数。选C双射表示f(x)→y和f⁻¹(y)→x都是一一对应。A中j²对应两个元素j和-j，排除；B中1对应无数个奇数，0对应无数个偶数，排除；C中|2j|+1对应两个元素j和-j，排除；只有D中2j-15对应唯一的j，满足双射，选Dn阶无向简单图即n个顶点，任意顶点的最大度Δ(G)不超过n-1，即某顶点与其他任意顶点都有一条边，最大度为n-1。所以选A一笔画问题的条件：所有顶点的度都为偶数（任意点出发可一笔画回到该点）；或者只有两个度为奇数的顶点，从其中一个奇度顶点出发，可一笔画到另一个奇度顶点只有A中恰好有两个度为奇数的顶点，因此可以一笔画。选A

4 (1)(A-B)-C=A-B-C, (A-C)-(B-C)=A-C-B

解 我们用如下办法产生一个等价关系R R1＝{a，b}×{a，b}＝{，，，} R2＝{c}×{c}＝{} R3＝{d，e}×{d，e}＝{，，，} R=R1∪R2∪R3＝{，，，，，，，，} 从R的序偶表示式中，容易验证R是等价关系。