运筹学最大流和最小割怎么求

问题描述

精选答案

问题一：最大流

一定量的水从源头source中流出，流量最大（maximum flow）是多少？

注意：水一旦流出，是可以充满整个管道网的。

s - > t 同时有3条路径可走：

s - > a - > t q1 = 2;

s - > a - > b - > t 由于1的成立，容量为1的管道不可能装得下流量为2的水，此路不通，所以 q2 = 0;

s - > b - > t q3 = 3。

木桶效应：水桶能盛多少水，取决于最短的那片木板。

所以，最大流是 2 + 3 = 5。

问题二：最小割

如果我要把其中的一些管子割断，最少割断（minimum cut）哪些管子能够使得水流完全不通？

即割断

s - > a （容量为2）

b - > t （容量为3）

即可。

所以，最小割也是 2 + 3 = 5。

结论：最大流 = 最小割

我们可以一句话来表示最大流最小割的思想：最大流（水流流量和）取决于必须经过的那些水管的最小割（水管容量和）。