Vertex Cut

定义 Definition

vertex cut（顶点割集）：在图论中，指图 (G) 的一个顶点集合 (S)，把 (S) 及其相关联的边从图中删除后，会使原图变成不连通（或使指定的两个顶点不再连通）。常用于讨论图的连通性与鲁棒性。
（在不同语境下也可指“最小顶点割集”，即大小最小的这类集合。）

例句 Examples

Removing a vertex cut can disconnect the graph.
删除一个顶点割集可以使该图变得不连通。

By Menger’s theorem, the size of a minimum vertex cut between two vertices equals the maximum number of internally vertex-disjoint paths between them.
根据门格尔定理，两个顶点之间的最小顶点割集大小等于它们之间内部顶点不相交路径的最大条数。

发音 Pronunciation (IPA)

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

词源 Etymology

vertex 源自拉丁语 vertex（意为“顶点、最高点、旋转的中心”），在数学与图论中引申为“图的节点/顶点”。cut 原义为“切割”，在图论里引申为“通过删除元素使结构被分开”的“割”。合起来 vertex cut 就是“通过删除某些顶点实现分割/断连的集合”。

相关词 Related Words

• Vertex
• Edge
• Separator
• Cutset
• Articulation Point
• Connectivity
• Minimum Cut
• Menger’s Theorem

文学与著作中的用例 Literary Works

• Graph Theory — Reinhard Diestel（常用“vertex cut / separating set”讨论图的连通与分离）
• Introduction to Graph Theory — Douglas B. West（涉及顶点割、连通度与相关定理）
• Graph Theory with Applications — J. A. Bondy & U. S. R. Murty（在连通性章节中使用顶点割相关术语）
• Combinatorial Optimization: Algorithms and Complexity — Christos H. Papadimitriou & Kenneth Steiglitz（在网络与割的相关讨论中涉及顶点割/分离概念）