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

问题描述

精选答案

问题一：最大流一定量的水从源头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。结论：最大流 = 最小割我们可以一句话来表示最大流最小割的思想：最大流（水流流量和）取决于必须经过的那些水管的最小割（水管容量和）。