最大流的基本概念

在网络图（有向图）中，为了讨论方便，我们称：

只有流出量而没有流入量的顶点为源，如图9-37中的vs；

只有流入量而没有流出量的顶点为汇，如图9-37中的vt；

既有流入量也有流出量的顶点为中间点，如图9-37中的v1、v4等.

每一条弧一般都标注有两个权数（cij，fij），其中前一个权数表示这条弧能容纳的最大流量，称为弧的容量，后一个权数fij表示该条弧现有的流通量，称为弧的现有流量.如（4，1）表示该条弧的容量为4，现在弧上的流量为1.如果现有流量等于弧的容量，则称该弧为饱和弧，否则称为不饱和弧，其中如果弧的现有流量为0，则称该弧为零流弧，否则称为非零流弧.如图9-37中的弧（v1，v2）为饱和弧，弧（v3，v4）为零流弧.

如果在一个网络图中，每一条弧的现有流量满足

而且中间点的流入量和流出量相等，并且源的流出量和汇的流入量也相等，则称该网络图存在可行流.

所谓最大流问题，就是在网络图中寻找流量最大的可行流.

例如，引例中求网络的最大流也就是要找到从源到汇的最大运输能力.从图9-38可知，现在从源到汇的流量为5，那么，该网络图有没有更大的运输能力.如果有，如何求出该网络图的最大流？