离散数学及其应用 2018-2019学年春夏学期期末考试 习题详解

一、判断题

2.注意transitive的等价条件是R对任意n成立，不是相等关系。

【回顾】transitive相关的条件转化

①求transitive closure:Warshall's Algorithm

②证明transitive，利用等价条件：R对任意n成立。

5.本题表述比较特殊，出入顶点的degree相等是针对每一个顶点而言的。在weakly connected的情况下，没有定点是只出不入或只入不出的。结合数学归纳法，容易证明这样的图是strongly connected的。

6.树的定义：connected simple graph，且e=n-1,不存在cycle.

7.此类题型划分区间讨论即可。比如(2n,2n+1）可以否定这一命题。

二、填空题

5.注意partial ordering和equivalence relation都有自反性(reflexive)的特点，但相应的简图有时会将之略去，不能不考虑。

6.按照同分异构体方法即可。

7.先比较、观察A的位置，发现A是根节点。根据inorder traversal的结果，发现D,B,E构成左子树，C,F构成右子树，再由两种遍历的结果，判断子树中顶点的相对位置关系即可。

8.计算equivalence relation，分类标准是等价类。可以是1个、2个与3个等价类，依次讨论即可。

计算partial ordering，除了自反性要求外，可画简图进行讨论。

本题有3个元素，分为如下几类：（简图只表示相异元素的情况，directed edge a->b表示a≤b，先画出3个点）

①没有directed edge，即任意两个互异元素都是incomparable的：1种。

②一条directed edge：6种（先选start point,再选endpoint，3×2＝6种）。

以下皆为2条 directed edge:

③从一个顶点出发，向另外两个顶点分别发出一条directed edge：3种。

④从两个顶点分别向第三个顶点发出一条directed edge ：3种。

⑤形成“链状”：如a->b->c（注：a->c由传递性可得），6种。

9.不要忽略空集和集合本身。

10.Dijikstra Algorithm。

三、计算题

3.②③都是容斥原理的使用（理解：硬币放入盒子，可以看成onto function的模型）

④选盒子、硬币分组、排序，运用乘法原理。

⑤硬币都是一致的，则属于r-combination with repetition allowed（实际上就是隔板法）

⑥注意r-combination with repetition allowed的前提是没有盒子数的限制，而exactly six boxes are empty要求被选的三个盒子都至少有一个硬币。

故：第一步：选盒子

选完盒子之后，每个盒子中都放一枚硬币，再用r-combination with repetition allowed的公式才能做到不重不漏。

6.③注意不是Hamilton graph的原因:Delete vertice V3 makes 2 components.

7.（1）证明e与v关系的不等式，一般利用欧拉公式和degree of region。

（2）注意后一问可以利用前一问的结论；运用反证法推出矛盾证明。

（3）①相对陌生的证明问题，运用归纳法或反证法比较多见。本题反证法看不出明显矛盾，考虑尝试归纳法，针对顶点个数进行归纳。

②归纳的关键是寻找从n-1到n的过渡条件，过渡条件要从题目已知信息、前几问结论出发。本题注意到containing no triangles即可归纳得出结论。