割点与桥

割点与桥分别检测顶点级和边级的单一失效点。它们的共同特征是删除后原先某些点对之间的所有路径同时消失；这比只看度数更可靠，因为高次数顶点也可能有大量替代路径。桥“不在任何圈上”正是路径冗余的局部刻画。

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

把两个三角形只通过一条边 $uv$ 相连，则 $uv$ 是桥，$u,v$ 都是割点，而三角形内部各边都不是桥。若让两个三角形只共享顶点 $w$，则 $w$ 是割点，但图中每条边都处在一个圈上，没有桥。算法中的 DFS 树可用 $\mathrm{low}$ 值判断：树边 $(u,v)$ 为桥当且仅当 $\mathrm{low}(v)>\mathrm{tin}(u)$。

连通性公理库图连通性Graph connectivity用顶点间是否存在路径定义无向图的连通性，并由此划分连通分量。只回答网络当前是否连通，割点与桥进一步定位脆弱位置。删除所有桥得到边双连通分量，围绕割点组织则形成块—割树；树公理库树Tree连通且无圈的有限简单无向图，也就是任意两点之间只有一条简单路径的图。是每条边均为桥的极端情形。道路冗余、通信容灾和编译器控制流中的支配/分块分析都借助这种“替代路径公理库路与圈Path and cycle in a graph用相邻顶点序列刻画图中的行走、简单路径与首尾闭合的简单圈。是否存在”的结构。