概念

连通性

割点与桥是网络的脆弱环节，2-连通与强连通（Menger 定理）刻画去除少量元素后网络仍互达的健壮性。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

连通性图论

01定义

连通性度量网络的健壮程度：割点与桥是删之即断的薄弱环节，

k

-连通要求删除任意

k-1

个顶点后仍连通。门格尔定理断言：最小割的大小恰等于不相交路径的最大条数——断与连的精确对偶。

割点：单点故障使网络一分为二

割点（删之增连通分量数）与桥（删之断连的边）是脆弱点；Tarjan 一次 DFS 即可全部找出——关键基础设施审计的标准算法。

分隔 $s,t$ 的最少顶点数 = $s,t$ 间顶点不交路径的最大条数——「最小割 = 最大流」的图论原型，网络可靠性分析的基石。

有向图的强连通分量（SCC）由 Kosaraju/Tarjan 线性时间求出；缩点成 DAG 后可解 2-SAT、课程依赖排序等问题。

\kappa(s,t)=\max\{\text{不相交}\ s\text{-}t\ \text{路径数}\}

门格尔 1927 年证明该定理（惠特尼同年给出不交形式）；Tarjan 1972 年的 DFS 算法族（割点、SCC、桥）奠定了线性时间图算法的范式。

电网与通信网的脆弱性评估、互联网骨干冗余设计、社交网络关键人物识别、编译器控制流分析（支配树）。

连通性与割点移除割点后图分裂成多个连通分量

cut 移除割点0