网络流模型

时间：2022-02-12 理论教育版权反馈

【摘要】：L：A→R为弧上的权函数，弧（i，j）∈A对应的权L（i，j）记为lij，称为弧（i，j）的容量下界；U：A→R为弧上的权函数，弧（i，j）∈A对应的权U（i，j）记为uij，称为弧（i，j）的容量上界，或直接称为容量；由于只讨论V，A为有限集合的情况，所以对于弧上的权函数L，U和顶点上的权函数D，可以直接用所有弧上对应的权组成的有限维向量表示，因此L，U，D有时直接称为权向量，或简称权.由于给定

定义在以V为节点集，A为弧集的有向图G=（V，A）上定义如下的权函数：

L：A→R为弧上的权函数，弧（i，j）∈A对应的权L（i，j）记为l_ij，称为弧（i，j）的容量下界；

U：A→R为弧上的权函数，弧（i，j）∈A对应的权U（i，j）记为u_ij，称为弧（i，j）的容量上界，或直接称为容量；

D：V→R为顶点上的权函数，节点i∈V对应的权D（i）记为d_i，称为顶点i的供需量；

此时所构成的网络称为流网络，可以记为N=（V，A，L，U，D）.

由于只讨论V，A为有限集合的情况，所以对于弧上的权函数L，U和顶点上的权函数D，可以直接用所有弧上对应的权组成的有限维向量表示，因此L，U，D有时直接称为权向量，或简称权.由于给定有向图G=（V，A）后，总是可以在它的弧集合和顶点集合上定义各种权函数，所以流网络一般也直接简称为网络.

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

对于流网络N=（V，A，L，U，D），其上的一个流f是指从N的弧集A～R的一个函数，即对每条弧（i，j）赋予一个实数f_ij（称为弧（i，j）的流量）.如果流f满足

则称f为可行流.至少存在一个可行流的流网络称为可行网络.

可见，当d_i＞0时，表示有d_i个单位的流量从该项点流出，因此顶点i称为供应点或源，有时也形象地称为起始点或发点等；当d_i＜0时，表示有|d_i|个单位的流量流入该点（或说被该顶点吸收），因此顶点i称为需求点或汇，有时也形象地称为终止点或收点等；当d_i=0时，顶点i称为转运点或平衡点、中间点等.此外，对于可行网络必有∑_i∈V d_i=0

一般来说，总是可以把L≠0的流网络转化为L=0的流网络进行研究.所以，除非特别说明，以后总是假设L=0，并将此时的流网络简记为N=（V，A，U，D）.

在流网络N=（V，A，U，D）中，对于流f，如果f_ij=0，（i，j）∈A，则称f为零流，否则为非零流.如果某条弧（i，j）上的流量等于其容量（f_ij=u_ij），则称该弧为饱和弧；如果某条弧（i，j）上的流量小于其容量（f_ij＜u_ij），则称该弧为非饱和弧；如果某条弧（i，j）上的流量为 0（f_ij=0），则称该弧为空弧.

考虑如下流网络N=（V，A，U，D）：节点s为网络中唯一的源点，t为唯一的汇点，而其他节点为转运点.如果网络中存在可行流f，此时称流f的流量为d_s，通常记为v（f），即v（f）=d_s=-d_t.

对这种单源单汇的网络，如果并不给定d_s和d_t，则网络一般记为N=（V，A，U，D）.最大流问题就是在N=（V，A，U，D）中找到流值最大的可行流.可以看到，最大流问题的许多算法也可以用来求解流量给定的网络中的可行流.也就是说，当解决最大流问题以后，对于在流量给定的网络中寻找可行流的问题，也就可以解决了.

因此，用线性规划的方法，最大流问题可以形式地描述如下：

最大流问题是一个特殊的线性规划问题.将会看到利用图的特点，解决这个问题的方法较之线性规划的一般方法要方便、直观得多.实际问题往往是多源多汇网络，为了计算的规格化，可将多源多汇网络G化成单源单汇网络G′.设X是G的源，Y是G的汇，具体转化方法如下：

在原图G中增加两个新的顶点x和y，令其分别为新图G′中之单源和单汇，则G中所有顶点V成为G′之中间顶点集.

用一条容量为∞的弧把x连接到X中的每个顶点.

用一条容量为∞的弧把Y中的每个顶点连接到y.

G和G′中的流以一个简单的方式相互对应.若f是G中的流，则由

所定义的函数f′是G′中使得v（f′）=v（f）的流.反之，G′中的流在G的弧集上的限制就是G中具有相同值的流.

设N=（V，A，U，D），SV，s∈S，t∈V-S，则称（S，）为网络的一个割，其中=V-S，（S，）为尾在S，头在的弧集，称C（S，）=为割（S，）的容量.