第7章图习题(带答案).docVIP

第7章 图习题 7．1在图7．1所示的各无向图中： (1)找出所有的简单环。 (2)哪些图是连通图?对非连通图给出其连通分量。 【分析与解答】 (1)路径上除了起点和终点相同以外，其他顶点都不相同的回路称为简单环。上述 无向图的简单环如下： (a)(1 2 3 1) (b)无 (c)(1 2 3 1) (2 3 4 2) (1 2 4 3 1) (d)无 (2)在图7．1中(a)、(c)、(d)是连通图。 图7-1(b)是非连通图，它有两个连通分量是(1，4)和(2，3)。 7．2在有向图7-2中： (1)该图是强连通的吗?若不是，给出其强连通分量。 (2)请给出所有简单路径及有向环。 (3)请给出每个顶点的度、入度和出度。 (4)请给出其邻接表、邻接矩阵及逆邻接表。 图7-2 【分析与解答】 (1)任何一对顶点之间都相互可达的有向图称为强连通图。该图是强连通的。 (2)所有简单路径(重复环未计算)． ①只包含一个顶点的简单路径有4条： (V1)、(V2)、(V3)、(74) ②只包含两个顶点的简单路径有5条： (Vl V2)、(V 2 V3)、(V3 V1)、(VI V4)、(V 4 V 3) ③只包含3个顶点的简单路径有6条： (V1 V2v3)、(V2 V 3 V1)、(V3 V1 V 4)、(V 3 Vl V 2)、(Vl V 4 V 3)、(V4 V 3 V1) ④只包含4个顶点的简单路径有4条： (V1 V2 V 3V1)、(V2V3V1 V 4)、(V 3V1 V 4 V 3)、(V4 V3Vl V 2) ⑤有向环有两个： (Vl V 2 V 3V1)和(V1 V 4 V 3V1) (3)各顶点的度、入度和出度如下所示： (4) ①邻接表 ②邻接矩阵 ③逆邻接表 7．3假设图的顶点是“A，B”，请根据下述邻接矩阵，如图7．3所示，1画出相应的有向图或无向图。 图7-3 【分析与解答】 ． 矩阵(a)除主对角线以外的元素全为1，因此它所对应的图是一个无向完全图或有向完 全图。矩阵(b)是一个非对称阵，因此它所对应的图是一个有向图。解答示意图如下图 (a)～(c) 7．4 对下图所示的连通图，请用Prim算法和Kruskal算法构造其最小生成树，并写出其构造过程。 答最小生成树如下： 7．5 已知有向图如下图所示，试写出图中的全部可能的拓扑排序序列。 答：152364；152634；156234；561234；512364；5126345； 16234； 7．6下图是一个无向图，从顶点1出发，DFS遍历的输出序列是（A），BFS遍历的输出序列是（D）。 A 1 3 5 4 2 7 6 B 1 3 4 7 6 2 5 C 1 5 3 4 2 7 6 D 1 2 4 3 7 5 6 3 4 2 2 2 5 2 1 5 1 3 6 4 4 3 7 5 6