离散数学(本)阶段练习四.doc

华东理工大学 网 络 教 育 学 院
本科《离散数学》第四阶段练习

一、判断题（对的在括弧中打个“√”，错的在括弧中打个“”）

1、对任何无向图，奇其点的个数必然为奇数。 （ ）
2、对于简单无向图而言，其所有顶点的度数和等于其两倍的边数。 （ √ ）
3、自补图对应的完全图的边数必为偶数。 （ √ ）
4、通路就是边不重复的一个点边交替序列。 （ ）
5、若图是连通的，则其补图必然是不连通的。 （ √ ）
6、若是图的邻接矩阵，则矩阵幂次中的对角线上元素等于它对应的顶点的度。 （ √ ）
7、所有顶点的度都为偶数的无向图一定是欧拉图。 （ ）
8、含有汉密尔顿路的图就是汉密尔顿图。 （ ）
9、对连通平面图而言，其边数、点数、面数必然满足。 （ √ ）
10、任意一棵树都至少拥有三个1度点。 （ ）
11、任一连通图都至少有一棵生成树，且生成树可以不唯一。 （ √ ）
12、任意一棵二叉树的树叶可对应一个前缀码。 （ √ ）

二、作图题
1、画出一个自补图；
2、画出一个既有欧拉回路、又有汉密尔顿圈的无向图；
3、画出一个有欧拉回路、但没有汉密尔顿圈的无向图；
4、画出一个无欧拉回路、但却有汉密尔顿圈的无向图；
5、画出一个自对偶图。

三、一棵树有个2度点，个3度点，……，个度点，其余均为1度点，试问：这棵树有多少个1度点？
解：设树有个1度点，是的边数，于是有

解之即得

四、若无向图中恰有两个奇点，试证明这两点之间必有一条路相连。
证明：（反证法）不妨设着两个奇点为，且它俩在图中没有路相连，那么它俩必存在于两个连通分支中，即存在于图的两个不连通的子图、当中，而作为每个子图来说，其中奇点的数目一定为偶数，故子图、当中至少分别存在两个奇点，即图中至少有4个奇点，这显然与图中恰有两个奇点矛盾。故这两点之间必有一条路相连。

五、试证明完全二部图不是平面图。
证明：（反证法）设完全二部图是平面图，且点数、边数、面数分别为、、，由于图中任何三条边围不成一个面，即围成一个面至少需要4条边，于是有，即，代入欧拉公式中即得。而中的，，且，于是矛盾，故而不是平面图。

六、用韦尔奇.鲍威尔法证明右下图的着色数。
证明：由韦尔奇.鲍威尔法，按红（）、蓝（）、黄（）、白（）……的着色顺序，给本图染色如右，正好用了4中颜色，因此该图是4色的。又由于该图中存在完全图，其4个顶点必须染以不同的颜色，所以该图不可能是3色的，故该图的色数。

七、试证明彼得森（）图不是汉密尔顿图。
证明：（仿照课本的例题2的标号法）因为任一个汉密尔顿图经过这种标号后，的个数必然相等（注意逆命题不成立！），利用逆否命题，现在此图因为有7个，9个，故彼得森（）图不是汉密尔顿图。

八、试将以下根树化成对应的二叉树。

解：

九、给定权，试以它们构造一棵最优二叉树。
解：
构造过程为从左下到右上。

4