计算机四级考试辅导：计算机离散数学习题八

 

8.1 画出完全二部图

8.2 设 为 阶二部图，至少用几种颜色给G的顶点染色，使相邻的顶点颜色不同？

8.3 完全二部图 中，边数 为多少？

8.4 完全二部图 的匹配数 为多少？

8.5 今有工人甲、乙、丙要完成三顶任务 ，已知工人甲能胜任 三项任务；工人乙能胜任 两项任务；工人丙能胜任 两项任务，你能给出一种安排方案，每个工人各完成一项他们能胜任的任务吗？

8.6 画一个无向欧拉图，使它具有：

（1）偶数个顶点，偶数条边；

（2）奇数个顶点，奇数条边；

（3）偶数个顶点，奇数条边；

（4）奇数个顶点，偶数条边

8.7 画一个有向的欧拉图，要求同8.6

8.8 画一个无向图，使它是：

（1）既是欧拉图，又是哈密尔顿图；

（2）是欧拉图，而不是哈密尔顿图；

（3）是哈密尔顿图，而不是欧拉图；

（4）既不是欧拉图，也不是哈密尔顿图。

8.9 画一个有向图，要求同8.8 题。

8.10 若D为有向欧拉图，则D一定为强连通图，其逆命题成立吗？

8.11 在什么条件下无向完全图 为哈密尔顿图？又在什么条件下为欧拉图？

8.12 有割点的无向图G不可能为哈密尔顿图，G也一定不是欧拉图吗？

8.13 今有 7个人，已知下列事实：

a、会讲英语；

b、会讲英语和汉语；

c会讲英语、意大利语和俄语；

d、会讲日语和汉语；

e、会讲德语和意大利语；

f、会讲法语、日语和俄语；

g、会讲法语和德语；

试问这7个人应如何排座位，才能使每个人都能和他身边的人交谈？

8.14 某工厂生产由6种不同颜色的纱织成的双色布。已知在品种中，每种颜色至少分别和其他5种颜色中的3种颜色搭配，证明可以挑出3种双色布，它们恰有6种不同的颜色。

8.15 指出图8.1 所示平面图各面的次数，并验证各面次数之和等于边数的两倍。

8.16 求图8.1 所示平面图G的对偶图 ，并验证 其中， 分别为G的顶点数、边数和面数，而 分别为 的顶点数、边数和面数。

 

8.17 求图8.2 所示平面图G的对偶图 ，再求 的对偶图 ， 与G同构吗？

8.18 彼得森图如图8.3 所示，证明它不是二部图，也不是欧拉图，还不是平面图。

8.19 证明图8.4 所示图G是哈密尔顿图，但它不是平面图。

8.20 图8.5 所示图G为平面图，试给出它的一个平面嵌入。它是极大平面图吗？

题8.12-8.23 的要求是从供选择的答案中选出应填出应填入叙述中的  内的正确答案。

8.21 （1）完全图 都是欧位图，这个命题的真值为A。

（2）完全图 都是哈密尔顿图，这个命题的真值为B。

（3）完全二部图 都是欧拉图，这个命题的真值为C。

（4）完全二部图 都是哈密尔顿图。这个命题的真值为D。

A，B，C，D；①真；②假。

8.22 （1）设 与 是两个平面图，若 ，则它们的对偶图 。这个命题的真值为A。

（2）任何平面图 的对偶图 的对偶图 与 同构。这个命题的真值为B。

（3）任何平面图 的对偶图 的面数 都等于 的顶点数 。这个命题的真值为C。

供选择的答案

A，B，C；①真；②假。

8.23  6个顶点11条边的所有可能的非同构的连通的简单的非平面图有A个，其中有B个含子图 ，有C个含与 同胚子图。

供选择的答案

A，B，C；①1；②2；③3；④4；⑤5；⑥6；⑦7；⑧8。