下列叙述中的 内。 1．下列群一定为循环群的是 5) 。
5)
（1）结合律 （2）交换律 （3）有零元 （4） 封闭性 3．设I是整数集，N是自然数集，P（S）是S的幂集，“×，＋，∩”是普通的乘法，加法和集合的交运算。下面代数系统中 （2） 是群。 （1）
（1）
（2）
第七章 图论
一、填空题
（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′=
（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