无向完全图与有向图的性质分析

"图解法" 本章节主要讨论了与图相关的概念和性质，特别是无向完全图、有向图的强连通性以及图的不同表示方法。以下是详细的知识点： 1. 无向完全图：一个无向图中，如果任意两个不同的顶点之间都存在一条边，那么这个图被称为无向完全图。例如，图8-1展示了从1个顶点到5个顶点的无向完全图。证明表明，具有n个顶点的无向完全图包含的边数是n(n-1)/2。这是因为每个顶点与其他n-1个顶点相连，但由于边是无向的，每对顶点间只算一条边。 2. 强连通有向图：在有向图中，如果从任意一个顶点可以沿着有向边到达图中的任何其他顶点，并且能返回原顶点，那么这个图是强连通的。在8-2的问题中，右边的有向图并未满足这一条件，因此它不是强连通的。每个顶点形成了自己的强连通分量，意味着每个顶点只能到达自己。 3. 简单路径：在图中，简单路径是指路径上的顶点不重复出现。题目给出了从不同顶点出发的所有简单路径，这有助于理解如何识别和列举图中的路径。 4. 图的表示： - 邻接矩阵：8-3的解答部分，邻接矩阵是用二维数组表示图的方式，其中元素表示对应顶点间是否有边相连。如果有1000个顶点，邻接矩阵会有1000000个元素，其中对于有向图有1000个非零元素，无向图则有2000个非零元素，这样的矩阵被认为是稀疏矩阵。 - 邻接表：这是一种节省空间的表示方式，仅存储图中实际存在的边。 - 邻接多重表（十字链表）：邻接多重表是邻接表的变体，适合表示有多条边连接同一对顶点的图。 5. 图的性质： - 稀疏矩阵：如果一个图的边数远小于顶点数的平方，它的邻接矩阵被认为是稀疏的，因为它大部分元素为零。 - 无向连通图的最少边数：n个顶点的无向连通图至少需要n-1条边，因为要确保图是连通的，最简单的形式是树形结构。 - 有向强连通图的最少边数：n个顶点的有向强连通图至少需要n条边，每个顶点必须有一条进入的边和一条离开的边，形成环状结构。 这些知识点涵盖了图论的基本概念，包括图的结构、性质以及表示方法，是理解图论和图算法的基础。通过这些问题，我们可以深入理解图的特性和应用，如网络连接性、路径搜索等。