第七章图习题答案.doc

第七章 图 习题答案 基础知识： 7.1 在图7.23所示的各无向图中：　　　　　(1)找出所有的简单环。　(2)哪些图是连通图?对非连通图给出其连通分量。　(3)哪些图是自由树(或森林)?答:　(1)所有的简单环：(同一个环可以任一顶点作为起点)　　　(a)1231　　　(b)无　　　(c)1231、2342、12341　　　(d)无　(2)连通图：　　　(a)、(c)、(d)是连通图，　　　(b)不是连通图，因为从1到2没有路径。具体连通分量为：　　　　　　(3)自由树(森林)：自由树是指没有确定根的树，无回路的连通图称为自由树：　　　(a)不是自由树，因为有回路。　　　(b)是自由森林，其两个连通分量为两棵自由树。　　　(c)不是自由树。　　　(d)是自由树。 7.2 在图7.24(下图)所示的有向图中：　　　 　(1) 该图是强连通的吗? 若不是，则给出其强连通分量。　(2) 请给出所有的简单路径及有向环。　(3) 请给出每个顶点的度，入度和出度。　(4) 请给出其邻接表、邻接矩阵及逆邻接表。答：(1)该图是强连通的，所谓强连通是指有向图中任意顶点都存在到其他各顶点的路径。　(2)简单路径是指在一条路径上只有起点和终点可以相同的路径：　　有v1v2、v2v3、v3v1、v1v4、v4v3、v1v2v3、v2v3v1、v3v1v2、v1v4v3、v4v3v1、v3v1v4、另包括所有有向环,有向环如下：　　　　　v1v2v3v1、v1v4v3v1(这两个有向环可以任一顶点作为起点和终点)　(3)每个顶点的度、入度和出度：　　　D(v1)=3　 ID(v1)=1　 OD(v1)=2　　　D(v2)=2 　ID(v2)=1　 OD(v2)=1　　　D(v3)=3 　ID(v3)=2　 OD(v3)=1　　　D(v4)=2 　ID(v4)=1　 OD(v4)=1　(4)邻接表：(注意边表中邻接点域的值是顶点的序号，这里顶点的序号是顶点的下标值-1)?? vertex firstedge? next　　　┌─┬─┐? ┌─┬─┐? ┌─┬─┐　 　0│v1│　─→│ 1│　─→│ 3│∧│????? ├─┼─┤? ├─┼─┤? └─┴─┘???? 1│v2│　─→│ 2│∧│????? ├─┼─┤? ├─┼─┤???? 2│v3│　─→│ 0│∧│????? ├─┼─┤? ├─┼─┤???? 3│v4│　─→│ 2│∧│????? └─┴─┘? └─┴─┘? 逆邻接表：??? ┌─┬─┐? ┌─┬─┐?? 0│v1│　─→│ 2│∧│??? ├─┼─┤? ├─┼─┤?? 1│v2│　─→│ 0│∧│??? ├─┼─┤? ├─┼─┤? ┌─┬─┐?? 2│v3│　─→│ 1│　─→│ 3│∧│??? ├─┼─┤? ├─┼─┤? └─┴─┘?? 3│v4│　─→│ 0│∧│??? └─┴─┘? └─┴─┘? 邻接矩阵：??? 0 1 0 1??? 0 0 1 0??? 1 0 0 0??? 0 0 1 0 7.3 假设图的顶点是A,B...，请根据下述的邻接矩阵画出相应的无向图或有向图。　　　　 ┌　　　　┓ ? ┌?????? ┓?? | 0 1 1 0 0 |? | 0 1 1 1 |?? | 0 0 0 1 0 |?? | 1 0 1 1 |?? | 0 0 0 1 0 |?? | 1 1 0 1 |?? | 1 0 0 0 1 |?? | 1 1 1 0 |?? | 0 1 0 1 0 |? ┕?????? ┙ ┕　?????? ┙????? (a)?????????????? (b)?答:??? 7.4 假设一棵完全二叉树包括A,B,C...等七个结点，写出其邻接表和邻接矩阵。解：? 邻接表如下：　　┌─┬─┐? ┌─┬─┐? ┌─┬─┐　 0│A │　─→│ 1│? ─→│ 2│∧│??? ├─┼─┤? ├─┼─┤? ├─┼─┤? ┌─┬─┐?? 1│B │　─→│ 0│　─→│ 3│　─→│ 4│∧│??? ├─┼─┤? ├─┼─┤? ├─┼─┤? ├─┼─┤?? 2│C │　─→│ 0│　─→│ 5│　─→│ 6│∧│??? ├─┼─┤? ├─┼─┤? └─┴─┘? └─┴─┘?? 3│D │　─→│ 1│∧│??? ├─┼─┤? ├─┼─┤?? 4│E │　─→│ 1│∧│??? ├─┼─┤? ├─┼─┤?? 5│F │　─→│ 2│∧│??? ├─┼─┤? ├─┼─┤?? 6│G │　─→│ 2│∧│??? └─┴─┘? └─┴─┘? 邻