最大流与最小费用流

-51- § 7 最大流问题 7.1 最大流问题的数学描述 7.1.1 网络中的流 定义 在以V 为节点集，A 为弧集的有向图),(AVG 上定义如下的权函数： （ i）RAL:为孤上的权函数，弧Aji),(对应的权),(jiL记为ijl ，称为孤),(ji的容量下界（ lower bound）； （ ii）RAU:为弧上的权函数，弧Aji),(对应的权),(jiU记为iju，称为孤),(ji的容量上界，或直接称为容量（capacity）； （ iii）RVD:为顶点上的权函数，节点Vi 对应的权)(iD记为id ，称为顶点i 的供需量（ supply／ demand）； 此时所构成的网络称为流网络，可以记为 ),,,,(DULAVN 。 由于我们只讨论AV ,为有限集合的情况，所以对于弧上的权函数UL,和顶点上的权函数D ， 可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示，因此DUL,,有时直接称为权向量，或简称权。由于给定有向图),(AVG 后，我们总是可以在它的弧集合和顶点集合上定义各种权函数，所以流网络一般也直接简称为网络。 在流网络中，弧),(ji的容量下界ijl 和容量上界iju表示的物理意义分别是：通过该弧发送某种“物质”时，必须发送的最小数量为ijl ，而发送的最大数量为iju。顶点Vi 对应的供需量id 则表示该顶点从网络外部获得的“物质”数量（0id时） ，或从该顶点发送到网络外部的“物质”数量（0id时） 。下面我们给出严格定义。 定义 对于流网络),,,,(DULAVN ，其上的一个流 （ flow）f 是指从N 的弧集A 到 R 的一个函数，即对每条弧),(ji赋予一个实数ijf （称为弧),(ji的流量）。如果流f 满足 AijjijiAjijijVidff),(:),(:,, （ 1） Ajiuflijijij),(,， （ 2） 则称f 为可行流（feasible flow）。至少存在一个可行流的流网络称为可行网络（feasible network）．约束（ 1）称为流量守恒条件（也称流量平衡条件），约束（2）称为容量约束。 可见，当0id时， 表示有id 个单位的流量从网络外部流入该项点，因此顶点i 称为供应点（ supply node）或源（source），有时也形象地称为起始点或发点等；当0id时，表示有||id个单位的流量从该顶点流失到网络外部（或说被该项点吸收），因此顶点i 称为需求点（demand node）或汇（sink），有时也形象地称为终止点或收点等；当0id时，顶点i 称为转运点（transshipment node）或平衡点、中间点等。此外，根据（1）可知，对于可行网络，必有 0Vii...