割点

割点（cut vertex，articulation point）是删除后使无向图的连通分量数增加的顶点。删除顶点时，与它关联的全部边也一同删除。割点刻画一个顶点对连通性的影响；判断时比较的是删除前后分量数，而不是只观察图中是否出现了孤立点。

例如，在边为 $ab,ac,bc,cd,de$ 的五顶点图中，$a,b,c$ 构成三角形，后接路径 $c,d,e$。删去 $c$ 后剩下边 $ab$ 与 $de$，原来一个分量变成两个；因此 $c$ 是割点。删去 $b$ 后则剩路径 $a,c,d,e$，仍连通，故 $b$ 不是割点。

删去c后，a、b与d、e之间失去全部连接。虚线仅标记被删除的边，不属于结果图。

分量数的定义适用于非连通图

令 $c(G)$ 表示图 $G$ 的连通分量数，约定空图分量数为零。顶点 $v$ 为割点的精确定义是 $$c(G-v)>c(G).$$ 设原来包含 $v$ 的分量为 $H$。其他分量不受删除影响，因此 $$c(G-v)=c(G)-1+c(H-v).$$ 所以只需检查 $H-v$ 是否分成至少两块。这一式也解释了孤立顶点：此时 $H$ 只有 $v$，删后分量数减少一，故孤立点不是割点。

在主例中，删 $d$ 后得到三角形 $abc$ 和孤立点 $e$，分量数变为二，因此 $d$ 也是割点。删叶子 $e$ 后，剩余图仍连通，分量数保持一。全部割点恰为 $\{c,d\}$。

所有连接路线都经过该点

路径判据。 顶点 $v$ 是割点，当且仅当存在两个不同于 $v$ 的顶点 $x,y$，它们在原图中属于同一连通分量，却每条连接它们的路径都经过 $v$。

证明。 若 $v$ 是割点，按上一节，$H-v$ 至少有两个分量。从其中不同分量各取一点 $x,y$；它们在 $H$ 中相连，但若原图存在避开 $v$ 的路径，这条路径也会留在 $H-v$ 中，与两点属于不同分量矛盾。

反过来，假设这样的 $x,y$ 存在。它们都留在 $H-v$ 中；若仍连通，就会有一条避开 $v$ 的原图路径，违反条件。因此 $H-v$ 至少有两个分量，代入分量数公式即得 $c(G-v)>c(G)$。

主例中取 $x=b,y=e$，任何连接它们的路径都必须依次经过 $c,d$。而取 $x=a,y=c$，既可沿边 $ac$，也可经 $b$；删除 $b$ 并不切断二者。判据检查所有路径是否被同一个顶点阻断，而非某一条画出来的路线是否经过它。

度数、环路和桥的区别

度零或度一的顶点不可能是割点。度一顶点若位于一条连接其他两点的简单路径内部，路径必须从唯一邻居进入后又返回同一邻居，这会重复顶点，不能是简单路径。因此其他点之间已有路径时，可选一条不经过该叶子的简单路径，删除它不会把其余点分开。度零的情况已由分量数直接说明。

但度至少二并不充分：三角形的每个顶点度都为二，删除任一点后另外两点仍由一条边连接，所以没有割点。更一般地，一个点位于环上，也不足以排除它成为割点。主例的 $c$ 位于三角形上，但仍是三角形区域与尾部之间的唯一接口。

桥是删除后增加分量数的边。割点未必关联桥。将两个三角形 $vabv$ 和 $vcdv$ 只在 $v$ 处相接：删 $v$ 后留下两条分离边，所以 $v$ 是割点；每条边却都位于三角形中，删一条后可沿同一三角形另两边绕行，因此没有桥。顶点脆弱性和边脆弱性不能混为一谈。

删除后的分量与有解答的变式

主例删除 $c$，可以由边表直接复算：五条边中 $ac,bc,cd$ 被删除，留下 $ab,de$；四个顶点被划分为两个分量。若误把 $a$ 与 $d$ 接起来，就进行了额外的消元操作，而不是删除顶点。

变式。 向原图增加边 $be$。此时 $b,c,d,e$ 形成环，$a$ 又连接着 $b,c$。删去 $c$ 后有路径 $a,b,e,d$；删去 $d$ 后 $e$ 仍经 $b$ 接入；删去其余任一点也不会断开。因此新图没有割点。一条绕行边可以同时消除多个割点，但这依赖它连接了哪些原先被分开的区域。

对至少三顶点的连通图，“没有割点”是二顶点连通性的一个等价描述。只有两个顶点的一条边也没有割点，通常仍需另列规模条件；把“无割点”直接当成所有规模下的二连通定义，会遗漏这个边界。