8-1画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证 明在n个顶点的无向完全图中,边的条数为m(n1)/2。 8-2右边的有向图是强连通的吗?请列出所有的简单路径。A 8-3给出右图的邻接矩阵、邻接表和邻接多重表表示 8.4用邻接矩阵表示图时,若图中有1000个顶点,100条C0 边,则形成的邻接矩阵有多少矩阵元素?有多少非零元素? 否稀疏矩阵? 【解答】一个图中有1000个顶点,其邻接矩阵中的矩阵元素有1000=1000000个。它 有1000个非零元素(对于有向图)或2000个非零元素(对于无向图),因此是稀疏矩阵 8-5用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边的条数是否相 【解答】用邻接矩阵表示图,矩阵元素的个数是顶点个数的平方,与边的条数无关。矩 阵中非零元素的个数与边的条数有关。 8-6有n个顶点的无向连通图至少有多少条边?有n个顶点的有向强连通图至少有多少 条边?试举例说明 【解答个顶点的无向连通图至少有n1条边,n个顶点的有向强连通图至少有n条边 例如: 无向图 有向图 ① 8-7对于有n个顶点的无向图,采用邻接矩阵表示,如何判断以下问题:图中有多少条 边?任意两个顶点和j之间是否有边相连?任意一个顶点的度是多少? 【解答】用邻接矩阵表示无向图时,因为是对称矩阵,对矩阵的上三角部分或下三角部 分检测一遍,统计其中的非零元素个数,就是图中的边数。如果邻接矩阵中A[i][i不为 零,说明顶点ⅰ与顶点j之间有边相连。此外统计矩阵第i行或第i列的非零元素个数, 就可得到顶点i的度数。 8-8对于如右图所示的有向图,试写出: (1)从顶点①出发进行深度优先搜索所得到的 深度优先生成树 (2)从顶点②出发进行广度优先搜索所得到的 广度优先生成树8-1 画出 1 个顶点、2 个顶点、3 个顶点、4 个顶点和 5 个顶点的无向完全图。试证 明在 n 个顶点的无向完全图中，边的条数为 n(n-1)/2。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 8-4 用邻接矩阵表示图时，若图中有 1000 个顶点，1000 条 边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？ 是否稀疏矩阵？ 【解答】一个图中有 1000 个顶点，其邻接矩阵中的矩阵元素有 10002 = 1000000 个。它 有 1000 个非零元素（对于有向图）或 2000 个非零元素（对于无向图），因此是稀疏矩阵。 8-5 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相 关？ 【解答】用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩 阵中非零元素的个数与边的条数有关。 8-6 有 n 个顶点的无向连通图至少有多少条边？有 n 个顶点的有向强连通图至少有多少 条边？试举例说明。 【解答】n 个顶点的无向连通图至少有 n-1 条边，n 个顶点的有向强连通图至少有 n 条边。 例如： 8-7 对于有 n 个顶点的无向图，采用邻接矩阵表示，如何判断以下问题： 图中有多少条 边？任意两个顶点 i 和 j 之间是否有边相连？任意一个顶点的度是多少？ 【解答】用邻接矩阵表示无向图时，因为是对称矩阵，对矩阵的上三角部分或下三角部 分检测一遍，统计其中的非零元素个数，就是图中的边数。如果邻接矩阵中 A[i][j] 不为 零，说明顶点 i 与顶点 j 之间有边相连。此外统计矩阵第 i 行或第 i 列的非零元素个数， 就可得到顶点 i 的度数。 8-8 对于如右图所示的有向图，试写出： (1) 从顶点①出发进行深度优先搜索所得到的 深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的 广度优先生成树；