搜索
6-4最大流问题一、基本概念1．容量网络：–（1）容量：有向图中，每条弧上给出的最大通过能力（即加在每条弧上的最大可能负载）称为该弧的容量。记为:C（vi，vj）或Cij，也常记为bij。–（2）容量网络：对所有的弧都给出了容量的有向网络，记为D=（V，A，C）或D=（V，A，B）。（1）流：①弧上的流——网络中加在弧上的负载量。记为fij或xij。②图上的流——加在网络中各条弧上的一组负载量（即定义在弧集上的一个函数）。记为f={f（vi，vj）}={fij}或X={xij}2．流与可行流（2）零流：若网络上所有弧上的流均为0，即对所有的i和j，都有xij=0，则称相应的图上的流为零流。tiftsisifxxAjiAijjiij,0),(),(（3）可行流：在容量网络上，满足容量限制条件和中间点平衡条件（连续性定理）的图上的流。即0≤Xij≤bij;其中f为网络中从起点s到终点t的流量。问：零流是不是可行流？3．割（割集、截集）：设V为网络中所有顶点的集合，将V剖分为两个子集和，满足:SSStSsVSSSS称弧集为分离起点和终点的的割集。组成割集的各条弧容量之和称为割容量（截量），所有割集中容量最小的割集称为最小割。),(SS4、弧的分类（1）在可行流X={xij}中，按流量的特征分有：①饱和弧——xij=bij②非饱和弧——xijbij③零流弧——xij=0④非零流弧——xij0（2）在容量网络中从起点vs到收点vt的一条链中，按弧的方向分①前向弧（正向弧）——与链的方向一致的弧。前向弧全体记为μ+；②后向弧（反向弧）——与链的方向相反的弧。后向弧全体记为μ_；其中,链的方向规定为:从起点vs指向终点vt。(3)按点来分任一顶点vi处，流入的弧称为对节点vi的后向弧，流出的弧称为对节点vi的前向弧。例：：{S，e1，V1，e2，V2，e3，V4，e4，V3，e5，T}V2TV1SV3V4e1e2e3e4e5e7e6e8e95.增广链（流量修正路线）：设χ是一可行流，μ是从起点vs到终点vt的一条链，若μ满足下面两个条件，则称μ为关于可行流χ的一条增广链（或流量修正路线）：①在弧（vi，vj）∈μ+上，0≤xijbij（即前向弧均为非饱和弧）②在弧（vi，vj）∈μ-上，0xij≤bij（即后向弧均为非零流弧）二、什么是最大流问题？在满足容量限制条件和中间点平衡条件的要求下，求取流量值达到最大的可行流的一类优化问题。简言之，是求容量网络中具有最大流量值的可行流问题。所求出的该可行流称为最大流。三、Ford-Fulkerson标记化方法的理论基础——最大流最小割定理（最大流量最小截量定理）在任一容量网络中，从发点到收点的最大流流量等于该网络最小割的割容量。＃四、标记化方法（标号算法）步骤与举例：1．确定初始可行流。如果没有给定，也难以观察得出，则将零流作为初始可行流；2．标号过程（目的是用标号法寻求增广链）（1）标号的意义——符号vi（vj,i）表示vi点的标号是（vj，i），其中vj表示点vi的标号来自vj，i表示流量的修正量。(2)标号过程给起点标上标号（-，+∞）；考察起点的所有相邻未标号点：对正向弧(vs,vj)，检查其是否饱和？是，则不加标记；不是，则加标记为(vs+,j)，其中j=csj-xsj；对反向弧检查其是否是零流弧？是，则不加标记；不是，则加标记为(vs-,j)，其中j=xsj；重复步骤二，但要注意把vs换成已得到标号的点；可能出现两种结局：a.标号过程中断，收点得不到标号。说明该网络中不存在增广链，现行的可行流就是最大流；b.收点得到标号，反向追踪即可找到一条从起点到收点由标号点及相应的弧连接而成的增广链。3．调整过程：修改流量，其中流量调整量，指增广链上所有弧的流量修正量；jjminj在增广链的正向弧上增加；反向弧上减少；其它弧上流量不变。调整方法：（3）用上述同样的方法对修正流量后的网络图再次进行标记化工作，得各顶点的标号如下：起点vs（-，），顶点v2（vs+，2）顶点v3、v4、v5、v6等都不能标记。因此，终点也就得不到标记，即已不存在流量修正路线。故流量修正工作到此为止。图2就是最大流量网络图，由图中可知最大流流量为20。