最大流最小

最大流最小割定理（Maximum Flow Min-Cut Theorem）是網路流最佳化中的一個基本定理，它表明在一個帶權有向圖中，最大流和最小割具有等價性。這個定理由美國數學家羅納德·F·福布斯（Ronald F. Fulkerson）和丹尼爾·B·梅爾文（Daniel B. Minc）在1956年提出。

定理內容： 在一個帶權有向圖中，給定一個源點S和一個匯點T，以及一個流量函式f，最大流最小割定理指出，最大流問題（即找到從S到T的最大流量）的解等於最小割問題（即找到將圖分成兩部分，使得S和T分別位於不同的部分，且割邊的權值之和最小）的解。

證明通常涉及到福特-福爾克森算法（Ford-Fulkerson algorithm），這是一個用於找到最大流的貪心算法。該算法通過不斷地找到增廣路（augmenting path）來增加流，直到無法再增加為止。增廣路的定義是在當前流的基礎上，通過增加或減少某些邊的流量，可以使得流從S到T增加。

最小割問題可以通過構造圖的割集來證明。給定一個最大流，我們可以通過將所有滿流邊（fully-flowed edges）從圖中刪除來構造一個割集。這樣的割集將圖分成兩部分，S位於一部分，T位於另一部分，且割邊的權值之和等於最大流的值。這是因為每一條滿流邊都是通過增廣路達到滿流的，而增廣路的每一條邊都至少貢獻了一次流量。

反過來，給定一個最小割，我們可以通過將割邊按照它們的權值反向，並將反向後的邊視為從T到S的新邊，來構造一個最大流。這樣構造的流可以通過將增廣路中的邊按照它們的權值增加流量來逐步增加，直到達到最大流。

最大流最小割定理在理論計算機科學和運籌學中有著廣泛的套用，特別是在解決網路流問題時，它提供了一個有效的方法來找到最優解。