数据结构与算法教程 习题答案作者 朱明方 吴及 第5章习题解答.doc

《数据结构与算法教程 习题答案作者 朱明方 吴及 第5章习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第5章习题解答5.1已知一个图有0到9一共10个顶点，图中边为：3-7，1-4，7-8，0-5，5-2，3-8，2-9，0-6，4-9，2-6，6-4；(1)请确定图中各个顶点的度；(2)给出图的连通分量；(3)列出至少有三个顶点的简单路径。[解答]由题意得到的图如图5-1所示。(1)顶点：0123456789；顶点的度：2132323222。(2)连通分量1：如图5-1(b)所示。连通分量2：如图5-1(a)所示。(3)连通分量1：3-7-8；连通分量2中：1-4-6，1-4-9，4-6-0，4-6-2，4-9-2,6-0

2、-5，6-2-5，6-2-9，6-4-9，9-2-5，9-2-6，0-5-2，(a)(b)共有13条。图5-15.2请分别画出1个顶点，2个顶点，3个顶点，4个顶点，5个顶点和6个顶点的无向完全图。[解答]如图5-2所示，分别为1个顶点，2个顶点，3个顶点，4个顶点，5个顶点和6个顶点的无向完全图。图5-2115.3若无向图G有15条边，有3个度为4的顶点，其余顶点的度不大于3，图G至少有多少个顶点？［解答］设图G至少有x个顶点，根据握手定理有：3×4＋3(x-3)=2×15，x=9(个)5.4试证明有V个顶点的任何无环连通

3、图均有V-1条边。[解答]无环连通图即为树。根据树的性质，有V个顶点的树均有V-1条边。5.5对于一个有V个顶点和的无向完全图，请问一共有多少个子图？[解答]一共有个子图。5.6对于一个有V个顶点和E条边的无向图，请给出其连通分量个数的上界和下界。[解答]根据无向图中顶点和边的关系可知，E必然满足0≤E≤V(V-1)/2，由分析可得到：提示：在不形成环的情况下，连通分量数目达到最小值；当某个连通分量为完全图时，连通分量数目达到最大值。5.7给出图5-43所示图的邻接矩阵和邻接表表示。图5-4311[解答]邻接矩阵为：0123

4、45678910111200110011000000110000000000002100010000000030000110000000400110110000005100110000000061000100100000700000010100008000000010100090000000010111100000000001001110000000001001120000000001110邻接表的顶点邻接关系为：0-1-2-5-61-02-0-43-4-54-2-3-5-65-0-3-46-0-4-77-6-88-7-99

5、-8-10-11-1210-9-1211-9-1212-9-10-115.8给出图5-44所示图的邻接矩阵、邻接表和邻接多重表表示。11图5-44[解答](1)邻接矩阵为：01234501B2C3D4E5F10A1B2C3D4E5F324514403101352∧∧∧∧∧∧∧∧∧∧∧∧A(2)邻接表（出边，入边）如图5-3所示。图5-3邻接表与逆邻接表(3)邻接多重表（十字链表）如图5-4所示。11图5-4邻接多重表5.9用邻接矩阵表示无向图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？有多少非零

6、元素？稀疏因子为多少？[解答]共有元素106个，非零元素2000个，稀疏因子为0.002。5.10有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？[解答]有n个顶点的无向连通图至少有n-1条边；有n个顶点的有强向连通图至少有n条边。提示：n个顶点的无向连通图的生成树有n-1条边；连接成环的n个顶点的有强向连通图有n条边。5.11设表示有向无权图的邻接矩阵为A[n][n]，请分别写出求图中任一顶点i的入度、出度、度的表达式。[解答]求顶点i的入度、出度、度的操作描述分别为：for(intj=0；j

7、

8、图邻接关系：有向图的邻接关系：逆图邻接关系：0-6-50-6-50-1-41-41-2-5-6-92-6-92-5113-7-83-8-73-4-1-6-94-94-6-15-0-25-25-06-0-2-46-46-2-07-3-87-87-38-3-78-8-3-79-2-49-9-4