Min-cut

释义 Definition

Min-cut（最小割）：在图论与网络流中，把图（通常有源点 s 与汇点 t）分成两个不相交的部分，使得从 s 一侧到 t 一侧的所有跨边容量（或权重）之和最小；这个最小值称为最小割值，对应的划分称为最小割。（在 s–t 最大流问题中，最小割值等于最大流值。）

发音 Pronunciation (IPA)

/ˈmɪn ˌkʌt/

例句 Examples

We computed the min-cut of the network to find the weakest connection.
我们计算了该网络的最小割，以找出最薄弱的连接。

In the max-flow problem, the min-cut provides a certificate that no larger flow is possible.
在最大流问题中，最小割提供了一个“证明”，说明不可能再有更大的流量。

词源 Etymology

min-cut 是 minimum（最小的）的缩略 min 与 cut（割／切分）组合而成的术语；其中 cut 在图论里指把顶点集合“切”成两部分的划分。“最小割”这一说法随着 20 世纪中期网络流与组合优化的发展而普及，常与“最大流—最小割定理”一起出现。

相关词 Related Words

• Capacity
• Cut
• Edge
• Flow
• Graph
• Max-flow
• Min-cut theorem
• Network
• Residual
• Source
• Sink

文学与名著中的用例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，《算法导论》）：网络流章节讨论最大流与最小割及其等价关系。
• Network Flows: Theory, Algorithms, and Applications（Ahuja, Magnanti, Orlin）：系统介绍最小割、最短路、最小费用流等经典模型。
• Algorithm Design（Kleinberg & Tardos，《算法设计》）：用最大流/最小割处理匹配、图像分割等建模问题。