第七章复习题第七章复习题.pdfVIP

第七章 复习题 1. 画出 1 个顶点、2 个顶点、3 个顶点、4 个顶点和 5 个顶点的无向完全图。 试证明在 n 个顶点的无向完全图中，边的条数为 n(n-1)/2。 【解答】 1 个顶点的 2 个顶点的 无向完全图 无向完全图 3 个顶点的 4 个顶点的 无向完全图 无向完全图 5 个顶点的 无向完全图 【证明】 在有 n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相 连，所以每一个顶点有 n-1 条边与其他 n-1 个顶点相连，总计n 个顶点有 n(n-1) 条边。但在无向图中，顶点 i 到顶点j 与顶点j 到顶点 i 是同一条边，所以总共 有 n(n-1)/2 条边。 A D 2. 右边的有向图是强连通的吗？请列出所有的简单路 B E 径。 C F 【解答】 判断一个有向图是否强连通，对于任何一对顶点 vi,vj ，从 vi 到 vj 和从 vj 到 vi 都存在路径。右面的有向图做不到这一点，它不是强连通的有向图。各 个顶点自成强连通分量。 所谓简单路径是指该路径上没有重复的顶点。 从顶点 A 出发，到其他的各个顶点的简单路径有A→B ，A→D→B ，A→B →C，A→D→B→C，A→D ，A→B→E ，A→D→E ，A→D→B→E ，A→B→C →F→E ，A→D→B→C→F→E ，A→B→C→F ，A→D→B→C→F 。 从顶点 B 出发，到其他各个顶点的简单路径有B→C，B→C→F ，B→E ，B →C→F→E 。 从顶点 C 出发，到其他各个顶点的简单路径有C→F ，C→F→E 。 从顶点 D 出发，到其他各个顶点的简单路径有D→B ，D→B→C，D→B→ C→F ，D→E ，D→B→E ，D→B→C→F→E 。 从顶点 E 出发，到其他各个顶点的简单路径无。 从顶点 F 出发，到其他各个顶点的简单路径有F→E 。 3. 给出右图的邻接矩阵、邻接表表示。 【解答】 (1) 邻接矩阵 A D ⎡0 1 0 1 0 0 ⎤ ⎢ ⎥ B E ⎢0 0 1 0 1 0 ⎥ ⎢0 0 0 0 0 1 ⎥ C F Edge ⎢ ⎥ ⎢0 1 0 0 1 0 ⎥ ⎢0 0 0 0 0 0 ⎥ ⎢ ⎥ ⎢⎣0 0 0 0 1 0 ⎦⎥ (2) 邻接表 0 A 1 3 ∧ （出边表） 1 B 2