最大流
6.1 最大流问题
这部分我们定义一个网络流，然后试图解决最大流问题。 定义1：网络是一个有向图，由顶点),(E V G =V s ∈和连接顶点的边组成。每一条边从v 到都有一个承载能力（即边的容量）由或是表示。对于任何, E t ∈),(w v e =w )(e u ),(w v u E w v ∉),(e m w u ==,0),(ν以及v n =
分别表示图中边的个数以及顶点的个数。
图6.1：是一个4个顶点条边的网络图。每条边的承载能力都标在了边的上面。
在网络流问题中，我们为每一条边分配流。定义流的方法有两种：原始（总体）流和网络流。
定义2：对于给定的原始流:—>R 要满足下面的条件：
),(w v r 2v z 容量平衡条件：对于中间点（不包括起点和终点）：
0),(),(=−∑∑∈∈V
德国人的性格w V w v w r v w v r 即：流出量 = 流入量。
z 容量限制条件：),(),(0w v u w r ≤≤ν
对于每一个非端点的顶点，容量平衡条件要求流入该顶点的总流量必须和流出该顶点的总流量。而容量限制条件要求任何边上的流量不能超过这个变的容量。如果给定的流满足以上两个条件，我们称它为可行流。 v
图6.2：一个网络流的例子，总流量为2.
中华圣陶杯中学生作文大赛在原始流中我们既可以从 到v ，又可以从w ν到而在网络流中，这样不同的两个流的轨迹是相同的。
w 定义3：网路流：—>R 要满足下面的条件：
),(w v f 2v z 自反性： =
- ),(w v f ),(v w f z 容量平衡条件：对于中间点（不包括起点和终点）：
0),(=∑∈V w w v f
z 容量限制条件：对于所有顶点 ，w ν),(),(w v u w f ≤ν
原始流可以转换成为网络流 = - 例如，如果从到有7个单元流，而从到有四个单元流，则从到的网络流=3.自反性直接规定了原始流和网络流的关系，因为我们可以把原始流转换成为网络流，接下来我们将只考虑网络流的问题。
),(w v r ),(w v f ),(w v r ),(v w r v w w v w w ),(w v f 尽管自反性把和联系起来，注意到容量问题仍然是网络流问题的直接问题是很重要的。一个有向边的容量与它的反方向是无关的。
),(w v f ),(v w f ),(v w u ),(w v u 为了下文的方便我们用或者-表示
),(S v f ),(v S f ∑∈V w w v f ),( 定义4：流的流量定义为f ∑∈=V v v s f f ),(
一个流的流量是从端点流出方向的所有流的和。也等于流入端点t 的所有边的流量的和。这个流量值表示我们可以从起始点到终点可以运输的资源的总量。我们本节的目标就是解决最大流问题。
s
定义5：最大流问题：给定一个网络),(E V G =寻一个可行流使得总流量达到最大值。
在这部分，我们将显示任意可行流按照从起点到终点的不同链路分割。利用这个事实，可以依据网络割集得出最大流的较高的界限。
冀星高速
引理1：（流的割集）。在网络G 中我们可以把任意可行流分割成至多个循环和s-t 条链路。 m 证明：以下算法提取个链路及环。
m 1. 到一个链路上面的流与从s 到t 的方向相反。（如果这个流是无零流，则至少
存在一个这样的边）
2. 反向扩大这个链路上的流量，直到某些变的流量成为0.
3. 增加这条链路使之成为这个流的割集的一个元素。
4. 重复这样的操作，知道不存在从s 到t 的反向流为止。
5. 如果仍然存在一些边存在非零流，则剩余的流可以分解成环。为了出环：删
去任意一个非零流边以及流出的变是非零流的，直到发现环为止。
6. 反向扩大发现的环。
7. 把环作为流的割集的一个元素。
8. 继续寻环，知道没有非零流边为止。
当我们反向扩大一条链路或是一个环的时候，我们会使一些边的流量变为零。至多存在m 个反向增广链，因此在流的割集中有m 链路/环
电力工程与管理
在网络流问题中，这一点对于出图的割集尤其是s-t 割集非常有用。
定义6：在网络中，弱顶点集V 被分割成两个部分G S 及，其中每一部分都是一个割集。 S 定义7： s-t 分割是这样的割集S t S s ∈∈, 通常这样的割集都会成对出现类似),(S S 或者只记为，
我们把网络流的和边的容量的内容概括的定义为网络流及割量。
S
定义8：对于网络流割集),(S S 定义网络流∑∑∈∈=S v S w w v f S f ),()(
定义9：割量定义为∑∑∈∈=S v S w w v u S u ),()(
图6.3：s-t 割的一个例子。S t S s ∈∈,，这里既可以有从到S S 的边也可以有从S 到的
边
S
图6.4：网络的割的例子。这里用冲突线的方式显示了s-t 割。这里的割量等于3.这是一个s-t 最小割
概括来讲：割量就是从到S S 的边的容量的总和，这个定义中方向很重要。我们不计算从到反方向流的边的容量的和。
S
引理2：给定一个流对于任意一个割，f S f S f =)(。
性行为艺术换句话说，所有的s-t 割都携带与相等的流量。
f 证明：我们可以用引理1直接证明。我们把流分割成s-t 条链路以及环。每一个链路一定结束在S ，
所以是从到S S 的流一定大于从S 到的流。所以，一条运输x 流的s-t 链路， x 运输量会全部包含于割集的流量中。在环上从S S 到的流量一定与从S 到S S 的流量相同。所以环提供给个割集的值相当于0。所以割集的流量总值等于每一个s-t 链路上的流量总和，即为S f 。
方法2：我们还可以通过介绍的割量来证明这个引理。对于 ＝s ，声明是真的。现在，假设我们把一个顶点从S S v S 中移动到S 中。则的值将会按照下面的方法改变：
)(S f z
随 )(S f ),(S v f 而增加。 z 随而减小。
)(S f ),(),(S v f v S f −=总之，把一个顶点v 从S 中移动到中后，值的改变等于S )(S f 0),(),(),(==+V v f S v f S v f （由流的平衡条件得出）
对于网络流，我们定义最小割是图的最小承载能力的割集，引理3把这个值与流建立联系。
引理3：如果是一个可行流，那么对于任意割集，都有f S )(S u f ≤
登封教研网证明：对于所有的边，e )()(e u e f ≤所以)()(S u S f ≤（通过任何一个割集的流都 S 不会超过这个割集的承载能力割量的）由引理2可知，f S f =)(，所以)(S u f ≤
6.3最大流最小割定理
在这部分，我们由引理3导出给出最大流与最小割之间的联系，就是最大流与最小割定理。
为了证明这个定理，我们先介绍一下残余网络以及增广链的概念。
定义11：在残余图中增广链是一个从节点s 到t 的又向链。
f
G
图6.5：一个残余网络的例子。这个残余网络与图6.1上网络图的和6.2上的描述的流保持一致。虚线描述的是一个可能的从÷增广链。
注意如果在图中存在增广链，就意味着我们可以在这个网络中在沿着这条增广链可以通过更多的流量。更准确的说，如果存在增广链
，那么我们可以沿着这个增广链至少增加的流量，所以说，对于一个给定的网路G 以及流，如果存在一个增广链，则流一定不是最大流。
f G f G ),,...,,(21t v v v s k )}
,(),...,(),,(min{211t v u v v u v s u k f f f f f G f 更一般的讲，如果是中的一个可行流，则也是G 中的可行流。流仍
然满足平衡条件，因为流的平衡性是线性的。流是可行流因为我们可以变换不等式从而得到。结果，如果是G 中的一个可行流，那么在中也是可行的。
'f f G 'f f +'f f +'
f f +)()()()('e f e u e u e f f −=≤)()()('e u e f e f f ≤+'f f G 'f f −用残余网络增广链，我们可以证明最大流和最小割定理。
定理1（最大流最小割定理）。在网络中的流中，下面条件是等同的：
G f 1. 流是最大流。 f
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议