Max-flow min-cut theorem

Материал из WikiGrapp
Перейти к навигации Перейти к поиску

Max-flow min-cut theorem --- теорема о наибольшем потоке и наименьшем разрезе.

Theorem. For any network, the maximum amount of flow from source to sink is equal to the minimum capacity of all cuts separating source and sink.

Another name is Ford-Fulkerson's theorem.