华东理工大学 网 络 教 育 学 院
本科《离散数学》第四阶段练习
一、判断题（对的在括弧中打个“√”，错的在括弧中打个“⨯”）
1、对任何无向图，奇其点的个数必然为奇数。

（ ⨯ ）
2、对于简单无向图G 而言，其所有顶点的度数和等于其两倍的边数。

（ √ ）
3、自补图对应的完全图的边数必为偶数。

（ √ ）
4、通路就是边不重复的一个点边交替序列。

（
⨯ ）
5、若图G 是连通的，则其补图G 必然是不连通的。

（ √ ）
6、若)(G A 是图G 的邻接矩阵，则矩阵幂次2
))((G A 中的对角线上元素)
2(ii a 等于它对应的
顶点i v 的度)deg(i v 。

（ √ ）
7、所有顶点的度都为偶数的无向图一定是欧拉图。

（ ⨯ ） 8、含有汉密尔顿路的图就是汉密尔顿图。

（ ⨯ ）
9、对连通平面图G 而言，其边数e 、点数v 、面数r 必然满足2=+-r e v 。

（ √ ） 10、任意一棵树都至少拥有三个1度点。

（ ⨯ ） 11、任一连通图都至少有一棵生成树，且生成树可以不唯一。

（ √ ） 12、任意一棵二叉树的树叶可对应一个前缀码。

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

三、一棵树T 有2n 个2度点，3n 个3度点，……，k n 个k 度点，其余均为1度点，试问：
这棵树T 有多少个1度点？
解：设树T 有1n 个1度点，e 是的边数，于是有
⎩
⎨
⎧++++=-++++=k k kn n n n e n n n n e 3213213221
)( 解之即得
2)2(243+-+++=k n k n n e
四、若无向图G 中恰有两个奇点，试证明这两点之间必有一条路相连。

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

故这两点之间必有一条路相
连。

五、试证明完全二部图3,3K 不是平面图。

证明：（反证法）设完全二部图3,3K 是平面
图，且点数、边数、面数分别为v 、e 、r ，由于图中任何三条边围不成一个面，即围成一个面
至少需要4条边，于是有r e 42≥，即e r 2
1
≤，代入欧拉公式r e v +-=2中即得42-≤v e 。

而3,3K 中的9=e ，6=v ，且84629=-⋅>，于是矛盾，故而3,3K 不是平面图。

六、用韦尔奇.鲍威尔法证明右下图的着色数4=χ。

证明：由韦尔奇.鲍威尔法，按红（r ）、蓝（b ）、黄（y ）、白（w ）……的着色顺序，给本图染色如右，正好用了4中颜色，因此该图是4色的。

又由于该图中存在完全图4K ，其4个顶点必须染以不同的颜色，所以该图不可能是3色的，故该图的色数4=χ。

七、试证明彼得森（Peterson
）图不是汉密
尔顿图。

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

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

解：
九、给定权13
,3
,2，试以它们构造一棵最优二叉树。

,5
,
11
,7
解：
构造过程为从左下
到右上。