下期离散数学(二)考试点评
简答题点评：
1. 一棵树有 4 个度为 2 的结点，3 个度为 3 的结点，2 个度为 4 的结点，其它结
点度均为 1，试求这棵树共有多少结点。 (6 分)
这道题所需要的理论非常简单，就是握手定理已经树的边数等于结点数 -1. 单还是不少人每
做出来。
2. 9 件相同玩具分给 3 个孩子，保证每个人都有玩具，但任何一人都不能超过 4
件，问有多少种分法？(要求用生成函数解答) (6 分)
这道题无论是教材上的例题，还是课堂讲过的例题，都不止一次地讲过，只要依葫芦画
瓢就可以。如果画不了，就是没有看书也没有认真听讲。
3. 求解递推关系 ?? = 4?? - 4?? , ?? = 2, ?? = 6. (8 分)
?? ??-1 ??-2 0 1
这道题没有难度。我在最后一次课说过必考的内容。
解答过程： (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 个点中必然至少有两个点的这种坐标奇偶性相
