来自"NOCOW"

[编辑] 最大流最小割定理

英文[Maximum Flow Minimum Cut Theorem]

[编辑] 描述

源S到汇T的网络最大流等于S与T间最小边割集的容量和。

最大流理论是由福特和富尔克森于 1956 年创立的 ，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善 。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。