关于连通性
连通性是图论中描述节点之间连接关系的重要概念。 通过连通性，我们可以判断图中任意两个节点是否可达， 识别图中的关键边（桥），以及分析有向图的强弱连通性质。
本章将系统介绍连通图与非连通图、连通分量、桥与局部桥，以及有向图的强连通和弱连通。
连通性
节点间的可达性
在无向图中，如果存在从节点u到节点v的路径，则称u和v连通（connected）。 如果图中任意两个节点都连通，则称该图为连通图。 连通性是图的一个重要拓扑性质，反映了信息或资源在图中的流通能力。
下面通过BFS（广度优先搜索）算法，动态展示如何查找两个节点之间的路径。
🎯 基本概念
📊 连通图
💻 NetworkX
连通分量
最大连通子图
连通分量（Connected Component）是无向图中的极大连通子图。 在连通分量内部，任意两个节点都可达； 不同连通分量之间的节点不可达。 非连通图可以分解为多个连通分量。
连通图示例 (图4-5)
非连通图示例 (图6)
最多6个节点的所有连通图 (图7)
NetworkX提供了图集（Graph Atlas），包含了最多6个节点的所有非同构连通图。 这些图展示了小规模图的所有可能拓扑结构。
📐 数学定义
🔍 识别算法
🎯 应用场景
📊 性质
💻 NetworkX
强连通、弱连通
有向图的连通性
有向图的连通性分为强连通和弱连通。 强连通要求任意两点间存在双向路径，条件严格； 弱连通只要求忽略方向后图连通，条件宽松。 强连通图一定是弱连通图，但反之不成立。
💻 NetworkX函数
🎯 实际应用
桥
图中的关键边
桥（Bridge）是图中移除后会增加连通分量数量的边。 桥连接了两个原本通过该边连通的部分，是图连通性的关键。局部桥虽然不一定是桥，但移除后会显著增加两端节点的距离。
空手道俱乐部的桥与局部桥 (图13-14)
树中的桥 (图15)
k边连通 (图16-17)
网络可靠性：k边连通图可以承受最多k-1条边的故障而保持连通。 通信网络、电网等关键基础设施通常设计为至少2边连通，以提供冗余保护。
最大k边连通分量：识别图中最鲁棒的子结构， 这些分量内部具有高度的连通性和容错能力。
🌉 桥的性质
🔍 识别算法
🎯 应用场景
所有的桥都是局部桥：桥移除后图不连通，两端节点距离变为无穷，必然是局部桥。
局部桥未必是桥：局部桥可能只是让两端距离变长，但不至于断开连通性。
本章小结
连通性是图论中描述节点可达性的核心概念。 通过连通性分析，我们可以识别网络中的关键结构、 检测孤岛、发现瓶颈，为网络优化和风险管理提供依据。
📊 核心概念
🎯 实际应用
💡 关键要点
- • 连通图：任意两点可达
- • 连通分量：极大连通子图
- • 桥：移除后连通性下降
- • 强连通：任意两点双向可达
- • 弱连通：忽略方向后连通
- • 强连通 ⊆ 弱连通