网络最大流问题

号。 再检查

，如前所述，标号也无法进行。

表示在图7-27中。最大流量为

与此同时，可找到最小截集

，其中

为最后一轮已标号点的集合，

为未标

至此已求得最大流。我们将最大流

号点的集合，即

最小截量为

所以

。

图7-27

由上述可见，用标号法找增广链以求最大流的结果，同时也得到一个最小截集。最小

截集的容量的大小影响总的运输量的提高。因此，为提高总的运输量，必须首先考虑增大最小截集中各弧的容量，提高它们的通过能力。反之，一旦最小截集中弧的通过能力降低，必然会使得运输量减少。

前面讨论都是对一个发点、一个收点的网络最大流问题。对于多个发点和收点的情形，我们可以采取虚设一个总发点

和总收点

，从总发点

到各发点

均以弧相联，并且

到总收点

亦

令这些弧的容量均为∞或某一具体值（根据情况而定）。同样，从各个收点以弧相联，也令这些弧的容量为∞或某一具体值。这样，原来的发点

与收点都变成了

转运点，原来的问题就转变成一个发点一个收点的网络图。例如图7-28所示是两个发点两个收点的网络，可以转换成一个发点一个收点的网络，见图7-29所示。

图7-29

[第一节]

[第二节]

[第三节]

[第四节]

[返回]