华东理工大学网络教育学院

1、华东理工大学网络教育学院本科离散数学第四阶段练习答案一、判断题（对的在括弧中打个“”，错的在括弧中打个“”）1、对任何无向图，奇其点的个数必然为奇数。（）2、对于简单无向图 G 而言，其所有顶点的度数和等于其两倍的边数。（）3、自补图对应的完全图的边数必为偶数。（）4、通路就是边不重复的一个点边交替序列。（）5、若图 G 是连通的，则其补图G 必然是不连通的。（）6、若 A(G ) 是图 G 的邻接矩阵，则矩阵幂次( A(G ) 2 中的对角线上元素aii(2) 等于它对应的顶点 vi 的度 deg(vi ) 。（）7、所有顶点的度都为偶数的无向图一定是欧拉图。（）8、含有汉密尔顿路的图就是汉

2、密尔顿图。（）9、对连通平面图 G 而言，其边数 e 、点数 v 、面数 r 必然满足 v e r2 。 （）10、任意一棵树都至少拥有三个1 度点。（）11、任一连通图都至少有一棵生成树，且生成树可以不唯一。（）12、任意一棵二叉树的树叶可对应一个前缀码。（）二、作图题1、画出一个自补图；2、画出一个既有欧拉回路、又有汉密尔顿圈的无向图；3、画出一个有欧拉回路、但没有汉密尔顿圈的无向图；4、画出一个无欧拉回路、但却有汉密尔顿圈的无向图；5、画出一个自对偶图。1三、一棵树 T 有 n2 个 2 度点， n3 个 3 度点， ， nk 个 k 度点， 其余均为1 度点，试问：这棵树 T 有多少个

3、1 度点？解：设树 T 有 n1 个 1 度点， e 是的边数，于是有e (n1n2n3nk ) 12en12n23n3knk解之即得e n32n4(k 2)nk 2四、若 无向图 G 中恰有两个奇点，试证明这两点之间必有一条路相连。证明：（反证法）不妨设着两个奇点为u、 w ，且它俩在图G 中没有路相连，那么它俩必存在于两个连通分支中，即存在于图G 的两个不连通的子图Gu 、 G w 当中，而作为每个子图来说，其中奇点的数目一定为偶数，故子图Gu 、 G w 当中至少分别存在两个奇点，即图 G 中至少有 4 个奇点，这显然与图 G 中恰有两个奇点矛盾。故这两点之间必有一条路相连。五、试 证明

4、完全二部图K 3, 3 不是平面图。证明：（反证法） 设完全二部图K 3, 3 是平面图，且点数、边数、面数分别为v 、 e、 r ，由于图中任何三条边围不成一个面，即围成一个面至少需要 4 条边，于是有2e4r ，即 r1 e，2代入欧拉公式 2v er 中即得 e 2v4 。而 K 3, 3 中的 e9 ，v6，且9 26 48 ，于是矛盾，故而K 3, 3 不是平面图。六、用 韦尔奇 .鲍威尔法证明右下图的着色数4 。2证明：由韦尔奇.鲍威尔法，按红（r ）、蓝（ b ）、黄（ y ）、白（ w ） 的着色顺序，给本图染色如右，正好用了4 中颜色， 因此该图是 4 色的。又由于该图中存在完全图K 4 ，其 4 个顶点必须染以不同的颜色，所以该图不可能是 3 色的，故该图的色数4。七、试 证明彼得森（Peterson）图不是汉密尔顿图。证明：（仿照课本p310 的例题 2 的标号法）因为任一个汉密尔顿图经过这种标号后，A、B的个数必然相等 （注意逆命题不成立！ ），利用逆否命题， 现在此图因为有7 个 A ，9 个 B ，故彼得森（ Peterson）图不是汉密尔顿图。八、试