Cut-Vertex

定义 Definition

cut-vertex（割点）：在图论中，若删除某个顶点（以及与它相连的所有边）会使图的连通分量数增加（也就是图变得更不连通），则该顶点称为 cut-vertex。也常称为 articulation point（关节点/割点）。在有向图或更一般情形下还有扩展定义，这里指最常见的无向图语境。

发音 Pronunciation (IPA)

/ˈkʌtˌvɝːtɛks/

例句 Examples

In this graph, vertex A is a cut-vertex.
在这张图中，顶点 A 是一个割点。

Identifying cut-vertices helps engineers find single points of failure in a communication network.
识别割点能帮助工程师找出通信网络中的单点故障位置。

词源 Etymology

cut- 表示“切断、割开”，vertex 来自拉丁语 vertex（意为“顶点、顶端”）。合起来字面意思是“会把图切开（切断连通性）的顶点”，对应图论中删除该点会“割裂”图的性质。

相关词 Related Words

• Articulation Point
• Cut-Edge
• Bridge
• Connectivity
• Connected
• Biconnected
• Block
• Component
• Vertex
• Graph
• Depth-First Search

文学与名著中的用例 Literary Works

• Graph Theory（Bondy & Murty）——在连通性与块（blocks）相关章节中讨论割点/关节点概念。
• Graph Theory（Reinhard Diestel）——在图的连通性、2-连通与分解结构中出现 cut-vertex（常与 blocks 一起）。
• Introduction to Graph Theory（Douglas B. West）——在“连通性与割点/桥”的基础章节中使用该术语与例题。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）——算法语境更常用 articulation points，与 DFS 低链接值（low-link）方法相关。