layout: article title: “连通图” date: 2024-09-24 tags: [“图”] category: DSA —

连通 所有顶点都是彼此可达的 ！要注意的是，连通是指两个顶点之间有路径可以到达，比如 A 和 C 之间有：A-B-C，那么顶点AC就是连通的，但AC之间没有一条直接相连的边！要注意这个区别！

连通无向图

  • 定义：一个无向图是连通的，如果图中任意两个顶点之间都存在至少一条路径。

  • 特点：

    • 连通性：确保所有顶点都是彼此可达的，没有孤立的部分。

    • 边的数量：对于 $n$ 个顶点的连通无向图，边的数量至少为 $n−1$，最多可达 $\dfrac{n(n - 1)}{2}$
    • 结构多样性：可以有多种不同的连接方式，只要保持连通性即可。

完全图

  • 定义：一个完全图是指在无向图中，任意两个不同的顶点之间都存在一条直接的边相连。

  • 特点：

    • 最大连通性：每个顶点都直接连接到其他所有顶点，没有例外。

    • 边的数量：对于 $n$ 个顶点的完全图，边的数量固定为 $\dfrac{n(n - 1)}{2}$，这是无向图中可能的最大边数。

    • 结构唯一性：同一顶点数的完全图只有一种结构形式。

区别总结

  1. 边的数量不同：

    • 连通无向图：边的数量介于 $n-1$ 和 $\dfrac{n(n - 1)}{2}$​ 之间。

    • 完全图：边的数量固定为

    \[\dfrac{n(n - 1)}{2}\]

    达到最大值。

  2. 顶点连接方式：

    • 连通无向图：任意两个顶点之间可能需要经过其他顶点才能到达。

    • 完全图：任意两个顶点之间都直接相连，无需经过其他顶点。

  3. 图的密度：

    • 连通无向图：密度可高可低，取决于边的数量。

    • 完全图：密度最高，边数最多。

  4. 应用场景：

    • 连通无向图：适用于一般的网络结构，如交通网络、通信网络，强调连通性而非密集连接。

    • 完全图：多用于理论分析和特殊算法，实际应用较少，因为高密度带来高成本。