第8章图 第7章图 7-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条边 7-2右边的有向图是强连通的吗?请列出所有的简单路径。 【解答】 判断一个有向图是否强连通,要看从任一顶点出发是否能够回到该顶 点。右面的有向图做不到这一点,它不是强连通的有向图。各个顶点自成 强连通分量 所谓简单路径是指该路径上没有重复的顶点 从顶点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。 7-3给出右图的邻接矩阵、邻接表和邻接多重表表示 【解答】 (1)邻接矩阵 010100 0010 0 000001 Ed 0100 000000 000010第 8 章 图 96                     = 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 Edge 第 7 章 图 7-1 画出 1 个顶点、2 个顶点、3 个顶点、4 个顶点和 5 个顶点的无向完全图。试证明在 n 个顶点的无向 完全图中，边的条数为 n(n-1)/2。 【解答】 【证明】 在有 n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有 n-1 条边与其他 n-1 个顶点相连，总计 n 个顶点有 n(n-1)条边。但在无向图中，顶点 i 到顶点 j 与顶点 j 到顶 点 i 是同一条边，所以总共有 n(n-1)/2 条边。 7-2 右边的有向图是强连通的吗？请列出所有的简单路径。 【解答】 判断一个有向图是否强连通，要看从任一顶点出发是否能够回到该顶 点。右面的有向图做不到这一点，它不是强连通的有向图。各个顶点自成 强连通分量。 所谓简单路径是指该路径上没有重复的顶点。 从顶点 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。 7-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 【解答】 (1) 邻接矩阵 1 个顶点的 无向完全图 2 个顶点的 无向完全图 3 个顶点的 无向完全图 4 个顶点的 无向完全图 5 个顶点的 无向完全图 A B C D E F A B C D E F