离散数学同步练习册a(4)

下列叙述中的 内。 1．下列群一定为循环群的是 5) 。

5) （运算“＋”是整数集I上的普通加法） 6) （R是实数集，“×”是普通乘法） 7) （运算“＋”是有理数集Q上的普通加法） 8) （P（S）是集合S的幂集，“?”为对称差） 2．运算“－”是整数集I上的普通减法，则代数系统 满足下列 性质 （4） 。

（1）结合律 （2）交换律 （3）有零元 （4） 封闭性 3．设I是整数集，N是自然数集，P（S）是S的幂集，“×，＋，∩”是普通的乘法，加法和集合的交运算。下面代数系统中 （2） 是群。 （1） （2） （3） （4） 4．下列代数系统不是群的是 （2） 。

（1） （运算“＋”是整数集I上的普通加法）

（2） （P（S）是集合S的幂集，“∩”为交运算） （3） （运算“＋”是有理数集Q上的普通加法） （4） （P（S）是集合S的幂集，“?”为对称差）

第七章 图论

一、填空题

（1）一个无向图G=（V，E）是二部图当且仅当G中无 奇数 长度的回路。 （2）任何图(无向的或有向的)中，度为奇数的顶点个数为 偶数。

（3）设D是一个有向图，若D中任意一对顶点都是相互可达的，则称D是__

强连通的。

（4）既不含平行边，也不含环的图称为 简单图 。

（5）经过图中 每边 一次且仅一次并且行遍图中每个顶点的回路，称为欧拉

回路。

（6）一棵有n个顶点的树含有n?1条边。

（7）设G =（V，E），G? =（V?，E?）是两个图，若V′= V且E′? E ，称G

16

是G的生成子图。

（8）经过图中 每个结点 一次且仅一次的回路，称为哈密尔顿回路。 二．判断题（正确的在括号内填√,错误的在括号内填×）

1．5个顶点的有向完全图有20条边。 （ × ）√ 2．连通无向图的欧拉回路经过图中的每个顶点一次且仅一次。 （ × ） 3．图中的初级通路都是简单通路。 （ √ ） 4．已知n (n?2)阶无向简单图G有n – 1条边，则G一定为树。 （ × ） 5．n阶无向完全图Kn的每个顶点的度都是n。 （ × ） 6．一个无向图是二部图当且仅当它没有奇数度的顶点。 （ × ） 7．任何图都有一棵生成树。 （ × ） 8．连通无向图的哈密尔顿回路经过图中的每条边一次且仅一次。 （ × ） 9．图中的初级回路都是简单回路。 （ √ ） 10．任一图G=（V，E）的顶点的最大度数必小于G的顶点数。 （ × ） 11．欧拉图一定是汉密尔顿图。 （ × ） 12．无向连通图G的任意两结点之间都存在一条路。 （ √ ） 13．根树中除一个结点外，其余结点的入度为1。 （ √ ） 三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内。 1．下列为欧拉图的是 (4) 。

2．下列各图为简单图的是 (3) 。

(1)

(2)

17

(3)

(4)

3．设无向图G有12条边，已知G中3度顶点有6个，其余顶点的度数都小于3，则该图至少有 (3) 个顶点。

（1）6 （2）8 （3）9 （4） 12 4．下列四个有6个结点的图 (3) 是连通图。

(1) (2) (3) (4)

5．称图G′=为图G = 的生成子图是指__(3)___.

（1）V′? V （2）V′? V且E′? E （3）V′= V且E′? E （4）V′? V且E′? E 6．有向图中结点之间的可达关系是__(2)___。

（1） 自反的，对称的 （2） 自反的，传递的 （3） 自反的，反对称的 （4） 反自反的，对称的 7．在下列关于图论的命题中，为真的命题是 d) 。

a) 完全二部图Kn, m (n ?1, m ?1)是欧拉图 b) 欧拉图一定是哈密尔顿图

c) 无向完全图Kn（n?3）都是欧拉图 d) 无向完全图Kn（n?3）都是哈密尔顿图 8．下列各图为平面图的是 （3） 。

9．设G为任意的连通的平面图，且G有n个顶点，m条边，r个面，则平面图的欧拉公式为 （1） 。

（1）n – m + r = 2（2）m – n + r = 2（3）n + m – r =2（4）r + n + m = 2 10．

下列四个图中与其余三个图不同构的图是 （3） 。

(1) (2) (3) (4)

18

（1） （2） （3） （4）

四、解答题

1．给定边集：{（1，2），（1，3），（2，3），（2，4），（2，5），（3，4），

（3，5），（4，5）}，

1）画出相应的无向图G（设G无孤立点）； 2）画出顶点子集V1 = { 2, 3, 4, 5}导出的导出子图； 3）画出图G的一棵生成树。 解

124图1)132图2)3524图3)35542．如图所示带权图，用避圈法(Kruskal算法)求一棵最小生成树并计算它的权

值。

解

4142C?T??1?2?4?4?11

3．如图所示带权图，用避圈法(Kruskal算法)求一棵最小生成树并计算它的权

值。

19

解

1345

2C?T??1?3?4?5?2?154．求带权图G的最小生成树，并计算它的权值。

1312

解

C?T??1?2?3?1?7

5．给定权为2，6，3，9，4；构造一颗最优二叉树。 解 2 3 4 9 5 4 9 9 9 18

W?T??3?2?3?3?2?4?9?32

189439526．给定权为1，9，4，7，3；构造一颗最优二叉树。 解 1 3 4 7 9 4 4 7 9 8 7 9 15 9 24

W?T??4?1?4?3?3?4?2?7?1?9?51

20

241583497416．给定权为2，6，5，9，4，1；构造一颗最优二叉树。 解 1 2 4 5 6 9 3 4 5 6 9 7 5 6 9 7 11 9 11 16 27

W?T??4?1?4?2?3?4?2?9?2?5?2?6?64

2711956167312421

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学同步练习册a(4)在线全文阅读。