形式陈述

设 $G$$G$ 为有限无向图。顶点 $v$$v$ 称为割点，若删除 $v$$v$ 及其关联边后，图的连通分量数严格增加。边 $e$$e$ 称为桥（割边），若删除 $e$$e$ 后连通分量数严格增加。若 $G$$G$ 连通，则割点使 $G-v$$G-v$ 不连通，桥使 $G-e$$G-e$ 不连通。对无向图，边 $e$$e$ 是桥当且仅当它不属于任何圈。若 $e=uv$$e=uv$ 是桥，则它在任意生成森林中出现；连通图中它出现在每棵生成树中。割点与二连通分量可由深度优先搜索的发现时间和 low 值在线性时间内求出。

直觉

割点和桥是网络中的单点、单边瓶颈：移除它们会把原本互达的部分切开。桥不能位于圈上，因为圈提供绕行路径。

例子与边界

树中每条边都是桥；在至少含两个顶点的树中，每个度数至少为二的顶点都是割点，而叶子不是。三角形没有桥也没有割点。定义以“分量数增加”为准，可统一处理原本不连通的图；仅说“删除后图不连通”会在原图已不连通时失真。单顶点图删除唯一顶点后得到空图，是否称割点依分量约定；标准定义用分量增加可避免把它误判。环和多重边会影响“桥 iff 不在圈”的具体圈定义，本条默认有限无向简单图。割点不一定与某条桥关联，例如两个圈共享一个顶点时共享点是割点但所有边都在圈上。

推论与应用

割点与桥用于网络可靠性、道路瓶颈、程序控制流和图的块—割树分解。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017，§1.4, cutvertices, bridges, and connectivity。
• Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001，§4.1, cuts, connectivity, and blocks。