文档介绍：最 大 流 问题
第一页，共22页。
一、基本概念
1．容量网络：
（1）   容量：有向图中，每条弧上给出的最大通过能力（即加在每条弧上的最大可能负载）称为该弧的容量。记为: C（vi，vj） 最 大 流 问题
第一页，共22页。
一、基本概念
1．容量网络：
（1）   容量：有向图中，每条弧上给出的最大通过能力（即加在每条弧上的最大可能负载）称为该弧的容量。记为: C（vi，vj）或Cij，也常记为bij。
（2）   容量网络：对所有的弧都给出了容量的有向网络，记为D=（V，A，C）或D=（V，A，B）。
第二页，共22页。
（1）求v1到v10的最大流及最大流量；
（2）求最小割集和最小割量。
第三页，共22页。
（1）流：①弧上的流——网络中加在弧上的负载 量。记为fij或xij。
②图上的流——加在网络中各条弧上
的一组负载量（即定义在弧集上的一个函数）。记为 f={f（vi，vj）}={fij}或X={xij}
2．流与可行流
（2）零流：若网络上所有弧上的流均为0，即对所有的i和j，都有xij=0，则称相应的图上的流为零流。
第四页，共22页。
（3）可行流：在容量网络上，满足容量限制条件和中间点平衡条件（连续性定理）的图上的流。
即 0≤Xij≤bij;
其中f为网络中从起点s到终点t的流量。
问： 零流是不是可行流？
第五页，共22页。
3．  割（割集、截集）：
设V为网络中所有顶点的集合，
将V剖分为两个子集 和 ，满足:
称弧集 为分离起点和终点的的割集。组成割集的各条弧容量之和称为割容量（截量），所有割集中容量最小的割集称为最小割。
第六页，共22页。
4、弧的分类
（1）在可行流X={xij}中，按流量的特征分有：
①饱和弧——xij=bij
②非饱和弧——xij<bij
③零流弧——xij=0
④非零流弧——xij>0
第七页，共22页。
（2）在容量网络中从起点vs到收点vt的一条链中，按弧的方向分
①前向弧（正向弧）——与链的方向一致的弧。前向弧全体记为μ+；
②后向弧（反向弧）——与链的方向相反的弧。后向弧全体记为μ_；
其中,链的方向规定为:
从起点vs指向终点vt。
第八页，共22页。
(3)按点来分 任一顶点vi处，流入的弧称为对节点vi的后向弧，流出的弧称为对节点vi的前向弧。
例：
：{S，e1，V1，e2，V2，e3，V4，e4，V3，e5，T}
V2
T
V1
S
V3
V4
e1
e2
e3
e4
e5
e7
e6
e8
e9
第九页，共22页。
（流量修正路线）：
设χ是一可行流，μ是从起点vs到终点vt的一条链，若μ满足下面两个条件，则称μ为关于可行流χ的一条增广链（或流量修正路线）：
①在弧（vi，vj）∈μ+上，
0≤xij<bij（即前向弧均为非饱和弧）
②在弧（vi，vj）∈μ-上，
0 < xij≤bij（即后向弧均为非零流弧）
第十页，共22页。
二、什么是最大流问题？
在满足容量限制条件和中间点平衡条件的要求下，求取流量值达到最大的可行流的一类优化问题。简言之，是求容量网络中具有最大流量值的可行流问题。
所求出的该可行流称为最大流。
第十一页，共22页。
三、Ford-Fulkerson标记化方法的 理论基础——最大流最小割定理 （最大流量最小截量定理）
在任一容量网络中，从发点到收点的最大流流量等于该网络最小割的割容量。
＃
第十二页，共22页。
四、标记化方法（标号算法） 步骤与举例：
1．确定初始可行流。
如果没有给定，也难以观察得出，则将零流作为初始可行流；
2．标号过程（目的是用标号法寻求增广链）
（1）标号的意义——符号vi（vj , i）表示vi点的标号是（vj，i） ，其中vj表示点vi的标号来自vj ， i 表示流量的修正量。
第十三页，共22页。
给出初始流如下
第十四页，共22页。
(2)标号过程
给起点标上标号（-，+∞