Minimum Cut

定义 Definition

minimum cut（最小割）：在图论/网络流中，指把图（常见为带容量的有向网络）分成两个不相交的部分（源点 \(s\) 在一侧、汇点 \(t\) 在另一侧）所需要“切断”的边集合；其割容量（从 \(s\) 侧指向 \(t\) 侧的边容量之和）在所有这样的切分里最小。常与“最大流最小割定理”一起出现。

发音 Pronunciation (IPA)

/ˈmɪnɪməm kʌt/

例句 Examples

A minimum cut separates the source from the sink with the smallest total capacity.
最小割以最小的总容量把源点与汇点分开。

Using the max-flow min-cut theorem, we can compute a minimum cut after finding the maximum flow in the network.
利用最大流最小割定理，我们在求出网络的最大流后就能计算出一个最小割。

词源 Etymology

minimum 源自拉丁语 minimus（“最小的”），cut 原义为“切割”。在图论里，cut 被借用为术语，表示把顶点集合“切分”为两部分的操作；minimum cut 就是“容量最小的切分/割”。

相关词 Related Words

• Capacity
• Cut
• Flow
• Max-Flow
• Min-Cut
• Residual
• Source
• Sink
• Partition
• Bottleneck

文学与著作中的用例 Literary & Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常称 CLRS）：网络流章节系统讲解最小割与最大流最小割定理。
• Network Flows: Theory, Algorithms, and Applications（Ahuja, Magnanti, Orlin）：以网络流为核心，频繁使用并扩展 minimum cut 的概念与算法。
• Combinatorial Optimization: Algorithms and Complexity（Papadimitriou & Steiglitz）：在组合优化语境下讨论最小割及其与其他优化问题的关系。