割点 / 关节点（图论）：在一个无向图中，删除某个顶点及其相关边会使图的连通分量数量增加（即图变得更不连通），那么这个顶点称为 cut vertex。
（也常称 articulation point；在不同语境下可能还有其他更细分的定义。）
/ˈkʌt ˈvɝːtɛks/
In this graph, removing node B creates two separate groups, so B is a cut vertex.
在这张图里，删除节点 B 会把图分成两个互不连通的部分，所以 B 是一个割点。
Using DFS, we can identify every cut vertex by checking whether a subtree becomes disconnected from the rest of the graph when a vertex is removed.
使用深度优先搜索（DFS），我们可以通过判断“删去某个顶点后某个子树是否与图的其余部分断开”来找出所有割点。
Cut 表示“切断、割开”，vertex 来自拉丁语 vertex（意为“顶点、最高点/转折点”）。合在一起，cut vertex 字面意思就是“会把图切开（导致断连）的顶点”，是图论中非常直观的命名。
Select Language