割点与桥

割点与桥分别检测顶点失效和边失效造成的断连。区别在于删除一个顶点会同时去掉多条边，可能破坏各个圈共同使用的中转站；删除单条边却未必破坏这些圈提供的绕行。

度数本身不能判断网络是否脆弱。一个高次数顶点周围可能有充分的替代路径，也可能是多个区域唯一的接点。判定真正要问的是：删除这个对象后，原先能互达的两个幸存顶点还能否互达。

两个三角形只通过一条新边 $uv$ 相连时，$uv$ 是桥，$u,v$ 都是割点；三角形内部各边都有绕行，均不是桥。如果两个三角形改为只共享一个顶点 $w$，则删除 $w$ 会留下两个分量，所以 $w$ 是割点；但每条边都在三角形上，图中没有桥。

树中每条边都是桥；树的割点恰是度数至少为 $2$ 的顶点。特别地，$K_2$ 的唯一边是桥，但两个端点都不是割点：删去一个端点后仍有一个分量。因此桥的端点未必是割点。单顶点图也没有割点，因为删除后分量数由 $1$ 降为 $0$。

定义必须比较删除前后的分量数。若原图已有两个分量，删除三角形中的一条边后仍不连通，并不能据此说这条边是桥。

深度优先搜索中的判据 ​

运行深度优先搜索理路深度优先搜索Depth-first search · DFS沿未访问边尽可能深入后回溯的图遍历算法。，记 $\mathrm{tin}(u)$ 为首次发现 $u$ 的时间；$\mathrm{low}(v)$ 是从 $v$ 的 DFS 子树出发，沿树边向下再至多用一条返祖边能到达的最早发现时间。对父子树边 $uv$，

严格大于表示子树连父节点也无法绕行到达。非根节点 $u$ 是割点，当且仅当有某个子节点 $v$ 满足 $\mathrm{low}(v)\ge \mathrm{tin}(u)$；这里允许等号，因为经过 $u$ 的绕行会随 $u$ 一起消失。DFS 根是割点则当且仅当它有至少两个树子节点。这些判据可在线性时间内求出全部割点与桥。

删除所有桥后得到不含桥的连通块；围绕割点组织极大的无割点块，可建立块—割树，在原图不连通时则得到森林。它们分别描述边故障与顶点故障下的分解，不能混为一种“双连通分量”。

块—顶点森林与单点失效查询理路块—顶点森林与单点失效查询Block-cut forest failure index · Block-vertex incidence forest · 单点失效连通性索引把点双连通块与原顶点组成关联森林，用树路径判定一次指定顶点失效后的两点连通性，并以原顶点的森林度数计算剩余分量数。保留每个原顶点，并为每个点双连通块另建节点。删去 $x$ 后，两个幸存端点是否仍连通，取决于关联森林的唯一端点路径是否经过 $x$；同一割点失效并不切断所有端点对。非割点保留为叶子，孤立点保留为孤立节点，使端点被删与整分量消失的边界都可单独核对。

道路冗余与通信容灾可用这些结构定位单一故障点。树理路树Tree连通且无圈的有限简单无向图，也就是任意两点之间只有一条简单路径的图。是无绕行的极端情形，而圈提供替代路径理路路与圈Path and cycle in a graph用相邻顶点序列刻画图中的行走、简单路径与首尾闭合的简单圈。。有向控制流中的支配关系还要求所有从入口出发的有向路径经过指定节点，不能直接用无向割点代替。

多重图仍可讨论桥，但平行边应构成长度二的圈，自环构成长度一的圈；DFS 实现还必须按边身份跳过父边，不能跳过所有通向父顶点的边。