運籌學最大流和最小割怎麼求

問題一：最大流

一定量的水從源頭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。

結論：最大流 = 最小割

我們可以一句話來表示最大流最小割的思想：最大流（水流流量和）取決於必須經過的那些水管的最小割（水管容量和）。