最大流最小割定理

最大流最小割定理（Maximum Flow Min-Cut Theorem）是網路流最佳化中的一個基本定理，它指出在一幅有向圖（通常稱為流圖）中，從一個特定的源點（source）到匯點（sink）的最大流等於最小割（s-t cut）的大小。這裡的"流"指的是在圖中從一個點到另一個點的流量，而"割"指的是將圖分成兩個部分，使得源點在其中一個部分，匯點在另一個部分，並且沒有邊跨越這個分割。

這個定理的直觀解釋是，如果存在一個從源點到匯點的最大流，那麼這個最大流可以通過將圖中的邊逐個斷開（即形成割）來達到，直到到達一個割，在這個割中，斷開任何一條邊都會導致流量的減少。這個割的大小就是最大流的值。

最大流最小割定理是網路流理論中的一個基礎結果，它不僅為最大流問題提供了一個有效的解決方法，而且還為許多其他最佳化問題提供了理論基礎。在實際套用中，最大流最小割定理被廣泛套用於資源分配、交通最佳化、調度問題和計算機網路等領域。