最大流最小割定理

在最优化理论中，最大流最小割定理提供了对于一个网络流，从源点到目标点的最大的流量等于最小割的每一条边的和。即对于一个如果移除其中任何一边就会断开源点和目标点的边的集合的边的容量的总和。
最大流最小割定理是线性规划中的对偶问题的一种特殊情况，并且可以用来推导门格尔定理和König–Egerváry定理。

定义

令G = (V, E)为一个网络（有向图），并且有一个起源点 s 和一个超汇点 t，代表 s 是所有流的源头，t 是所有流的终点。

举例

上图是一个网络，上有流量为7 的流。令 S 集合和T 集合分别包含所有白色和灰色的点， 从而形成了一个割集包含图中虚线的s-t 割，并且其容量为7，与流量相同。故由大流最小割定理知，前述的流与s-t 割皆达到流量及容量的极值。

门格尔定理

不共边路径问题为给定无向图 及两顶点s、t，求从s 到 t 彼此没有共同边的路径数量的最大值。
门格尔定理的叙述为从s 到 t 彼此没有共同边的路径数量的最大值等于在所有G 的 s-t 割(以原本的定义)中，顶点分别在不同集合的边数的最小值。

历史

最大流最小割问题最早在1956年被P. Elias, A. Feinstein，和 C.E. Shannon 证明， 并且L.R. Ford, Jr. 和 D.R. Fulkerson 也在同年证明了该定理。