15最大流问题PPT优秀课件.ppt

最大流量问题n本节内容 u相关概念与基本定理u求解网络最大流方法2021/6/31流量网络定义n给定一个n个顶点加权连通图，该图具有如下特性：u包含1个没有输入边的顶点；该点称为源点u包含1个没有输出边的顶点；该点称为汇点u每条有向边的权重uij是一个正整数，称为该边的容量(这个数字表示该边所代表的链路把物质从i送到j的数量上限)n满足以上特性的有向图称为流量网络2021/6/32n设源点与汇点分别是物质流中惟一的出发地和目的地n进入中间点物质总量必须等于离开物质总量，这个条件称为能量守恒要求n如果用xij来标记通过边(i,j)传输量，则：2021/6/33n容量约束：u对于每条边(i,j)E来说，0xijuijn可行解：u一个给定一个网络的流，使得它满足流量守恒约束和容量约束n最大流量问题：2021/6/34最大流量求解方法n最大流量问题求解有两种方法u单纯形法u增益路径法2021/6/35增益路径法n从流量0开始，试着找一条可以传输更多流量的、从源点到汇点的路径这样路径称为流量增益n如果找到了一条流量增益路径，沿路径调整边上的流量，以得到更大的流量值迭代,直到找不到为止。

2021/6/36增益路径的实现举例n沿路径1→2 →3 →6，最多把流量增加2个单位 n由于不能再进一步增加，算法结束，得到结果（b）n但此时不为最优结果，沿路径1→4 → 3←2 →5 →6流量还能增加2021/6/37扩展增益路径法n为求流量x的增益路径，需考虑两类边：u前向边：从i连向j，该边具有正的未使用的容量rij=uij-xiju后向边：从j连向i，该边具有正的流量xjiij未使用的容量rij=uij-xijij流量xji前向边后向边2021/6/38扩展增益路径法n对于给定容量的增益路径，设r是所有前向边中未使用的容量和后向边中具有正的容量xji 中的最小值n如果在每条前向边上增加容量r，在向后边上减去r，得到一个更大的可行流量2021/6/39扩展增益路径的实现举例n上图b中，增益路径1→4 → 3←2 →5 →61,4),(4,3),(2,5),(5,6)是前向边，(3,2)是后向边，最小值r=1，根据r值进行调整，得到c2021/6/310增益路径法性能退化n路径生成次序如果不恰当，会对该方法效率产生巨大的影响，如下图：u沿路径1→2 →3 →4对流量0进行增益，会得到(b)中值为1的流量。

u沿路径1 →32 →4对流量0进行扩展增益，会得到(c)中值为2的流量n共迭代2U次才能得到最大流量值2U2021/6/311增益路径法性能退化n2次得到最大流量值方法：u沿路径1→2 →4 对流量0进行增益u沿路径1→3 →4 对流量0进行增益n增益路径法依赖于路径生成次序，生成次序不恰当，会对该方法效率产生巨大的影响2021/6/312最短增益路径法n基本思想：用广度优先查找，用数量最少的边来生成增益路径n具体策略：两个记号来标记一个新的(未标记)顶点u第一个标记指出从源点到被标记顶点还能增加多少流量u第二个标记指出另一个顶点的名字2021/6/313n两个记号来标记一个新的(未标记)顶点u第一个标记指出从源点到被标记顶点还能增加多少流量u第二个标记指出另一个顶点的名字u第二个标记加上+或-号，用来指出该顶点是通过前向边还是后向边得到的2021/6/314n如果未标记顶点j是由从i到j的有向边和遍历队列中的前面顶点i相连接，而且j具有大于0的未使用容量rij=uij-xij,那么顶点j就标记为lj,i+，其中lj=min{li,rij}2021/6/315n如果未标记顶点j是由从j到i的有向边和遍历队列中的前面顶点i相连接，而且j具有大于0的流量xij,那么顶点j就标记为lj,i-，其中lj=min{li,xij}。

2021/6/316n处理2结点时，由于从1到2未使用容量为2，因此2顶点标记为min{,2},1+.n处理3结点时，由于从2到3未使用容为5，因此3顶点标记为min{2,5},2+.n这种标记的遍历结束于汇点6，沿着路径1→2 →3 →6用2对流量进行增益2021/6/317n下一次迭代时过程n这种标记的遍历结束于汇点6，沿着路径1→4 →3 →2→5 →6用1对流量进行增益2021/6/318n再一次迭代时n由于没有增益路径(汇点没有被标记)，当前流量已经是最大的了2021/6/319标号法步骤如下：标号法步骤如下：第一步第一步 找出一个初始可行流找出一个初始可行流fij(0),例如所有弧的流量例如所有弧的流量fij(0) =0.第二步第二步  利用广度利用广度优优先搜先搜对点进行标号找出一条增益路径对点进行标号找出一条增益路径 （（1 1）） 起点标号（起点标号（∞∞）） （（2 2）） 选选一一个个点点vi已已标标号号且且另另一一端端未未标标号号的的弧弧沿沿着着某某条条链链向向收点检查收点检查       （（a）如果弧是前向弧且有）如果弧是前向弧且有fij＜＜cij，则，则vj标号标号 θ θj=cij﹣﹣fij （（b）如果弧是后向弧且有）如果弧是后向弧且有fij﹥﹥0，则，则vj标号标号θθj=fij2021/6/320 当收点已得到标号时，说明已找到增益路径，依当收点已得到标号时，说明已找到增益路径，依据据v的标号反向追踪得到一条增益路径。

当收点不能得的标号反向追踪得到一条增益路径当收点不能得到标号时，说明不存在增益路径，计算结束到标号时，说明不存在增益路径，计算结束第三步第三步  调整流量调整流量 (1) 求增广链上点的求增广链上点的vi标号的最小值，得到调整量号标号的最小值，得到调整量号  (2) 调整流量调整流量   2021/6/321 f fijij+ +θθ （（v vi i，，v vj j））∈∈u u+ +f f1 1= = f fijij﹣ ﹣ θθ （（v vi i，，v vj j)∈∈u u- - f fijij （（v vi i，，v vj j )      u u  得得到到新新的的可可行行流流f f1 1，，去去掉掉所所有有标标号号，，返返回回到到第第二二步步从从发发点点重重新新标标号号寻寻找找增增益益路路径径，，直直到到收收点点不能标号为止不能标号为止 2021/6/322定义：（截集或割集）定义：（截集或割集）如果如果N N表示某网络中所有点的集合，表示某网络中所有点的集合，将将N N分成两个子集分成两个子集S S与与S S，使得发点，使得发点v v0 0在在S S内，收点内，收点v vn n在在S S 内，则称（内，则称（S S，，S S）为分离发点与收点的割集。

显然，）为分离发点与收点的割集显然，S S S S=N =N ，，S S S S= = ，，V V0 0  S S ，，V Vn n S S 2021/6/323v0vnv2v1a a割集割集a a：：v v0 0v v1 1，，v v0 0v v2 2，，v v0 0v vn n2021/6/324v0vnv2v1b b割集割集b b：：v v1 1v vn n，，v v2 2v vn n，，v v0 0v vn n2021/6/325v0vnv2v1c c割集割集c c：：v v1 1v vn n，，v v1 1v v2 2，，v v2 2v v1 1，，v v0 0v v2 2 ，，v v0 0v vn n2021/6/326v0vnv2v1d d割集割集d d：：v v0 0v v1 1，，v v1 1v v2 2，，v v2 2v v1 1，，v v2 2v vn n，，v v0 0v vn n2021/6/327定义（割的容量）定义（割的容量）从从S S中各顶中各顶点到点到S S中各顶点全部容量之和中各顶点全部容量之和称为割的容量（截量），用称为割的容量（截量），用（（S S，，S S）表示。

表示2021/6/328割集割集a: Ca: Ca a=C=C0101+C+C0202+C+C0n0n割集割集b: Cb: Cb b=C=C1n1n+C+C2n2n+C+C0n0n割集割集c: Cc: Cc c=C=C1n1n+C+C1212+ C+ C0202+ C+ C0n0n割集割集d: Cd: Cd d=C=C0101+C+C2121+ C+ C2n2n+ C+ C0n0n2021/6/329v0vnv2v1c cSS在截集在截集c c中边中边v v2 2v v1 1是反向的，其容是反向的，其容量视为零量视为零2021/6/330v0vnv2v1d dSS在截集在截集d d中边中边v1v2v1v2是反向是反向的，其容量视为零的，其容量视为零2021/6/331定义（最小截量）定义（最小截量）一个网络中，各种截集中容量一个网络中，各种截集中容量最小的称为最小截量，用最小的称为最小截量，用min min C(S,C(S,S) S)表示2021/6/332 现在我们把一个网络看成是一现在我们把一个网络看成是一个自来水管网络，煤气管网络，电个自来水管网络，煤气管网络，电力线网络或公路网络，铁路网络，力线网络或公路网络，铁路网络，水运交通网络等，都可以归纳成一水运交通网络等，都可以归纳成一个运输问题，称为网络流，值得关个运输问题，称为网络流，值得关心问题是在这样一个网络中最大流心问题是在这样一个网络中最大流为多少？为多少？2021/6/333定义（流）定义（流）若对网络若对网络N N，函数，函数f f满足如下满足如下条件：条件：（（1 1））0 0   f fij ij   C Cijij (i,j) (i,j) E(N)E(N)（（2 2））f f- -(v(vi i) = f) = f+ +(v(vi i) i) i V(N)V(N)则称则称f f为为N N的一个网络流，简称流。

的一个网络流，简称流2021/6/334定义（最大流）定义（最大流） 若若 f f 为为N N的一个网络流，而的一个网络流，而N N中不存在流中不存在流 f f ，使得，使得 f f >f >f ，，则称则称 f f 为一个最大流，记为一个最大流，记Max Max f f 2021/6/335截量截量 C C与流与流 f f 的关系的关系 任一有向网络流，如果任一有向网络流，如果 f f 是从发点是从发点到收点的流量，到收点的流量，C(S,C(S,S)S)是任一个截集，是任一个截集，则则 f f   C(S, C(S,S)S) 等号什么时候成立？等号什么时候成立？ 网络中最大流量等于它的最小割的容网络中最大流量等于它的最小割的容量2021/6/336部分资料从网络收集整理而来，供大家参考，感谢您的关注！。