1.最大流问题的数学描述

1.1图中的流

定义 在以为节点集，为弧集的有向图上定义如下的权函数：
1.为弧上的权函数，弧对应的权记为，称为弧的容量下界；
2.为弧上的权函数，弧对应的权记为，称为弧的容量上界，或直接称为容量；
3.为顶点上的权函数，节点对应的权记为，称为顶点的供需量。
此时构成的网络称为流网络，可以记为：

由于我们只讨论优先级和的情况，所以对于弧上的权函数和顶点上的权函数，可以直接用所有弧上对应的权和顶点上的权组成的有限维向量表示，因此有时直接称为权向量，或简称权。由于给定有向图，我们总是可以在它的弧集合和顶点集合上定义各种权函数，所以流网络一般也直接简称为网络。

在流网络中弧的容量下界和容量上界表示的物理意义是：通过该弧发送某种“物质”时，必须发送最少数量为，而发送的最大数量为，顶点对应的供需量则表示该顶点从网络外部获得的“物质”数量（时），或从该顶点发送到网络外部的“物质数量”（时）。下面我们给出严格定义。

定义：对于流网络其上的一个流是指从的弧集的一个函数，即对每条弧赋予一个实数（称为弧的流量）。如果流满足：


则称为可行流，至少存在一个可行流的网络称为可行网络，约束（1）称为流量守恒条件（也称流量平衡条件），约束（2）称为容量约束。

可见，当时，表示有个单位的流量从该顶点流失到网络外部，因此顶点称为供应点或源。同理的点称为吸收点或汇。特殊地，当，改点称为转运点或平衡点。

一般来说，我们总是假设容量下界为0，所以约束2可改为：

1.2.饱和弧，非饱和弧和空弧

定义：在流网络中，对于流，如果

则称为零流，否则为非零流，如果某条弧上的流量等于其容量，则称该弧为饱和弧；如果某条弧上的流量小于其容量，则称该弧为非饱和弧；如果某条弧上的流量为0，则称该弧为空弧。

2.最大流问题

2.1.问题的定义和辅助定理

考虑如下流网络；节点为网络中唯一的源点，为唯一的汇点，而其他节点为转运点。如果网络中存在可行流，此时称流的流量为（自然也等于），通常记为或，即

对于这种单源单汇的网路，如果我们并不给定和（流量不给定），则网络一般记为。最大流问题就是在中找到流值最大的可行流（即最大流）。我们将会看到，最大流问题的许多算法也可以用来求解流量给定的网络中的可行流。也就是说，当我们解决了最大流问题以后，对于在流量给定的网络中寻找可行流的问题，通常也就可以解决了。

用线性规划的方法，可将最大流问题描述如下：

为了解决这个问题，给出一些定义和定理：

全幺模矩阵（全单位模矩阵）：如果一个矩阵的任何子方阵的行列式的值都是0,1，-1，则称是全幺模的，或称A是全幺模矩阵。

整流定理：最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量均为正整数，则问题的最优解为整数解。

最大流问题虽然是一个线性规划问题，但是其可以利用图的优点，解决这个问题的方法较之线性规划的一般方法要方便，直观得多。

2.2.单源和单汇运输网络

实际问题往往是多源多汇网络，为了计算的规格化，可将多源多汇网络化成单源单汇网络。设为的源，是的汇

具体转化方法如下：
1.在原图中增加两个新的顶点和，令为新图中之单源和单汇，则中所有顶点成为的中间顶点集。
2.用一条容量为的弧把连接到的每个顶点。
3.用一条容量为的弧把中的每个顶点连接到。

和中的流以一个简单的方式相互对应。若是中的流，则由：

所定义的函数是中使得的流，这里表示流出的流量，表示流入的流量（在中）。

2.3.最大流和最小割关系

设，则称为网络的一个割，其中为尾在，头在的弧集，称

为割的容量。

定理：是最大流，是容量最小的割的充要条件是

在网络中，对于轨（此轨是无向的），若，则称它为前向弧；若，则称它为后向弧。

在网络中，从到的轨上，若对所有的前向弧都有，对所有的后向弧恒有，则称这条轨为从到的关于的可増广轨。

令


则在这条可增广轨上每条前向弧的流都可以增加一个量， 而相应的后向弧的流可减少 ，这样就可使得网络的流量获得增加，同时可以使每条弧的流量不超过它的容量，而且保持为正，也不影响其它弧的流量。总之，网络中可增广轨的存在是有意义的，因为这意味着不是最大流。