华中科技大学计算机学院离散数学2,华中科技大学计算机学院2015 离散数学二考试点评.pdf...

2015 下期离散数学(二)考试点评

简答题点评：

1. 一棵树有4 个度为2 的结点，3 个度为3 的结点，2 个度为4 的结点，其它结

点度均为1，试求这棵树共有多少结点。(6 分)

这道题所需要的理论非常简单，就是握手定理已经树的边数等于结点数-1. 单还是不少人每

做出来。

2. 9 件相同玩具分给3 个孩子，保证每个人都有玩具，但任何一人都不能超过4

件，问有多少种分法？(要求用生成函数解答)(6 分)

这道题无论是教材上的例题，还是课堂讲过的例题，都不止一次地讲过，只要依葫芦画

瓢就可以。如果画不了，就是没有看书也没有认真听讲。

3. 求解递推关系 = 4 −1 − 4 −2, 0 = 2, 1 = 6. (8 分)

这道题没有难度。我在最后一次课说过必考的内容。

解答过程：(1)首先给出相应的特征方程，

(2 )解出特征方程的根，是一个重根

(3 )利用相关的定理，对应重根的情况，有相应的解的公式，代入公式

(4 )再将两个给定的初始值带入公式里，把系数求出来，就能得到答案

这是系统化、公式化的解法。只要按照这种公式化的解法解就可以了。

4. 求下图的最小生成树： (6分)

这道题是送分题目，只要利用相关算法，直接解出即可。

5. 判断下面两个图是否同构。如果不同构，说明理由；如果同构，请给出两个

图之间的同构映射。 (6 分)

这道题的答案是不同构。可以有很多理由说明不同构的。

例如：其中一个图是k3,3 ，非平面图，偶图。而另一个显然是平面图。

也可以说，其中一个有长度为3的简单回路，另一个显然没有；等等。

6. 构造一个图模型，用来表示华中科技大学所有学生跟所有的选修课之间的关

系。这个图是否为偶图，为什么？从图中，如何统计一个人选修的课的数目？该

图可能为多重图吗？ 存在单边弧 (两端点相同的边)吗？

这道题要求把建模过程写清楚(我课堂内一再强调这一点)，点表示什么，边表

示什么，然后实际问题如果转变成图的问题等内容，必须说清楚的。至于结论就

很简单了。

问题出现较多的还是没有把建模说清楚，或者根本就不说，直接说答案。

我也在课堂内讲过一道类似的以往的考题，几乎是一样的。

证明题点评：

证明题30 分。

第1 题： 证明平面上5 个坐标为整数的点，至少有两个的中点坐标也为整数。

这一道题比教材上的一道练习题(三维坐标系中9 个点，…)还简单些，道理完全一样。这

道题布置过作业，而且我在课堂上讲过教材上的这道练习题。还是有些同学没做出来，说明

没有好好听课，或者没听懂课后也不去理会。当然也不知道做作业时这道题是怎么做的。

出现的问题有：有些同学根本不知道怎么做；也有些同学做了，但没有说明为什么要两个点

的坐标的奇偶性相同才能保证中点坐标为整数，这是需要说明理由的。尽管理由简单，还是

需要说明的。越是简单的证明题，其理由越是要说清楚。不能跳得太多。

解答：

两个坐标点(a,b),(c,d)的中点坐标是：( (a+c)/2, (b+d)/2). 于是在a,b,c,d 都是整数的情况下要

使得中点坐标为整数，只有a 与c 且b 与d 的奇偶性是一致的。

一个整数坐标的点(x,y)的两个坐标的奇偶组合只可能出现4 种可能(奇数，奇数)、(偶数，偶

数)、(奇数，偶数)、(偶数、奇数)。

于是根据鸽巢原理，5 个点中必然至少有两个点的这种坐标奇偶性相同，从而其中点坐标为

整数。

第2 题： n 个结点的简单图有n+1 条边，那么至少有一个结点的度大于或者等于3.

这道题有不是同学反正，

反正假设是：假设没有结点度大于或者等于3， 于是就得出结论说所以结点的度为2；

也有同学直接说可以假设所以结点的度都为2，于是该都就是一个圈图。

然后再得出结论只有n 条边，与已知矛盾。

首先，没有度大于或者等于3 的结点，那么度还有可能是0,1 或者是2 三种可能。怎么能说

每个结点度是2 ？“大于或者等于3 ”的否命题是“等于2”吗？无论是退出所以度为2 还

是假设所以度为2，都犯了同一个错误，低级错误。

其次，即便是所以点的度都为2，也不一定就是圈图。想象一下，由两个或者更多多不相连

的多边形组合的图(多个分支)，其每个点的度不都是2 吗？

还有个别同学，推来推去，退出2n>n，然后也说矛盾，不知道矛盾在哪里。

另外一个小问题是，不少同学说有”多少个度，几个度“，这种词不知道从哪里学来的。

正确解答：(其实只要应用握手定理，非常简单。这10 分可以说是送分题