发布时间 : 星期日 文章图论基础知识汇总(适合建模)更新完毕开始阅读c182da290066f5335a812165
点发送到网络外部的“物质”数量（di?0时）。下面我们给出严格定义。
定义 对于流网络N?(V,A,L,U,D)，其上的一个流（flow）f是指从N的弧集A到R的一个函数，即对每条弧(i,j)赋予一个实数fij（称为弧(i,j)的流量）。如果流f满足
ijj:(i,j)?A?f?j:(j,i)?A?fji ?di,?i?V, （1）
lij?fij?uij,?(i,j)?A， （2）
则称f为可行流（feasible flow）。至少存在一个可行流的流网络称为可行网络（feasible
network）．约束（1）称为流量守恒条件（也称流量平衡条件），约束（2）称为容量约束。
可见，当di?0时，表示有di个单位的流量从该项点流出，因此顶点i称为供应点（supply node）或源（source），有时也形象地称为起始点或发点等；当di?0时，表示有|di|个单位的流量流入该点（或说被该顶点吸收），因此顶点i称为需求点（demand node）或汇（sink），有时也形象地称为终止点或收点等；当di?0时，顶点i称为转运点（transshipment node）或平衡点、中间点等。此外，根据（1）可知，对于可行网络，必有
?di?Vi ?0 （3）
也就是说，所有节点上的供需量之和为0是网络中存在可行流的必要条件。
一般来说，我们总是可以把L?0的流网络转化为L?0的流网络进行研究。所以，除非特别说明，以后我们总是假设L?0（即所有孤(i,j)的容量下界lij?0），并将
L?0时的流网络简记为N?(V,A,U,D)。此时，相应的容量约束（2）为 0?xij?uij,?(i,j)?A。
定义 在流网络N?(V,A,U,D)中，对于流f，如果 fij?0,?(i,j)?A，
则称f为零流，否则为非零流。如果某条弧(i,j)上的流量等于其容量（fij?uij），则称该弧为饱和弧（saturated arc）；如果某条弧(i,j)上的流量小于其容量（fij?uij），则称该弧为非饱和弧；如果某条弧(i,j)上的流量为 0（fij?0），则称该弧为空弧（void arc）。
7.1.2 最大流问题
考虑如下流网络N?(V,A,U,D)：节点s为网络中唯一的源点，t为唯一的汇点，而其它节点为转运点。如果网络中存在可行流f，此时称流f的流量（或流值，flow value）为ds（根据（3），它自然也等于?dt），通常记为v或v(f)，即
v?v(f)?ds??dt。
对这种单源单汇的网络，如果我们并不给定ds和dt（即流量不给定），则网络一般记为N?(s,t,V,A,U)。最大流问题（maximum flow problem）就是在
N?(s,t,V,A,U)中找到流值最大的可行流（即最大流）。我们将会看到，最大流问题
-21-
的许多算法也可以用来求解流量给定的网络中的可行流。也就是说，当我们解决了最大流问题以后，对于在流量给定的网络中寻找可行流的问题，通常也就可以解决了。
因此，用线性规划的方法，最大流问题可以形式地描述如下：
maxv
?v,i?s?s.t. ?xij??xji???v,i?t ， （4）
j:(i,j)?Aj:(j,i)?A?0,i?s,t? ?(i,j)?A. （5）
定义 如果一个矩阵A的任何子方阵的行列式的值都等于0，1或?1，则称A是全幺模的(totally unimodular TU，又译为全单位模的)，或称A是全幺模矩阵。
定理8（整流定理） 最大流问题所对应的约束矩阵是全幺模矩阵。若所有弧容量均为正整数，则问题的最优解为整数解。
最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点，解决这个问题的方法较之线性规划的一般方法要方便、直观得多。
7.1.3 单源和单汇运输网络
实际问题往往是多源多汇网络，为了计算的规格化，可将多源多汇网络G化成单源单汇网络G'。设X是G的源，Y是G的汇，具体转化方法如下：
（i）在原图G中增加两个新的顶点x和y，令其分别为新图G'中之单源和单汇，则G中所有顶点V成为G'之中间顶点集。
（ii）用一条容量为的弧把x连接到X中的每个顶点。 （iii）用一条容量为的弧把Y中的每个顶点连接到y。
0?xij?uij,??G和G'中的流以一个简单的方式相互对应。若f是G中的流，则由
若a是G的弧?f(a),?f'(a)??f?(v)?f?(v),若a?(x,v)
?f?(v)?f?(v),若a?(v,y)?所定义的函数f'是G'中使得v(f')?v(f)的流。反之，G'中的流在G的弧集上的限制就是G中具有相同值的流。
7.2 最大流和最小割关系
设N?(s,t,V,A,U)，S?V，s?S，t?V?S，则称(S,S)为网络的一个割，其中S?V?S，(S,S)为尾在S，头在S的弧集，称
C(S,S)?(i,j)?Ai?S,j?S?uij
为割(S,S)的容量。
定理9 f是最大流，(S,S)是容量最小的割的充要条件是
v(f)?C(S,S)。
在网络N?(s,t,V,A,U)中，对于轨(s,v2,?,vn?1,t)（此轨为无向的），若vivi?1?A，则称它为前向弧；若vi?1vi?A，则称它为后向弧。
-22-
在网络N中，从s到t的轨P上，若对所有的前向弧(i,j)都有fij?uij，对所有的后向弧(i,j)恒有fij?0，则称这条轨P为从s到t的关于f的可增广轨。
令
?uij?fij,当（i,j)为前向弧?ij??，
当（i,j)为后向弧?fij,??min{?ij}
则在这条可增广轨上每条前向弧的流都可以增加一个量?，而相应的后向弧
的流可减少?，这样就可使得网络的流量获得增加，同时可以使每条弧的流量不超过它的容量，而且保持为正，也不影响其它弧的流量。总之，网络中f可增广轨的存在是有意义的，因为这意味着f不是最大流。
7.3 最大流的一种算法—标号法
标号法是由Ford和Fulkerson在1957年提出的。用标号法寻求网络中最大流的基本思想是寻找可增广轨，使网络的流量得到增加，直到最大为止。
7.3 最大流的一种算法一标号法
标号法是由Ford和在1957年提出的。由标号法寻求网络中最大流的基本思想是寻找可增广轨，使网络的流量得到增加，直到最大为止。
-23-