15(最大流问题)

2020/1/30山东交通学院信息工程系1最大流量问题本节内容相关概念与基本定理求解网络最大流方法2020/1/30山东交通学院信息工程系2流量网络定义给定一个n个顶点加权连通图，该图具有如下特性：包含1个没有输入边的顶点；该点称为源点。包含1个没有输出边的顶点；该点称为汇点。每条有向边的权重uij是一个正整数，称为该边的容量(这个数字表示该边所代表的链路把物质从i送到j的数量上限)。满足以上特性的有向图称为流量网络。2020/1/30山东交通学院信息工程系3设源点与汇点分别是物质流中惟一的出发地和目的地。进入中间点物质总量必须等于离开物质总量，这个条件称为能量守恒要求。如果用xij来标记通过边(i,j)传输量，则：2020/1/30山东交通学院信息工程系4容量约束：对于每条边(i,j)E来说，0xijuij可行解：一个给定一个网络的流，使得它满足流量守恒约束和容量约束。最大流量问题：2020/1/30山东交通学院信息工程系5最大流量求解方法最大流量问题求解有两种方法单纯形法增益路径法2020/1/30山东交通学院信息工程系6增益路径法从流量0开始，试着找一条可以传输更多流量的、从源点到汇点的路径。这样路径称为流量增益。如果找到了一条流量增益路径，沿路径调整边上的流量，以得到更大的流量值。迭代,直到找不到为止。2020/1/30山东交通学院信息工程系7增益路径的实现举例沿路径1→2→3→6，最多把流量增加2个单位。由于不能再进一步增加，算法结束，得到结果（b）。但此时不为最优结果，沿路径1→4→3←2→5→6流量还能增加。2020/1/30山东交通学院信息工程系8扩展增益路径法为求流量x的增益路径，需考虑两类边：前向边：从i连向j，该边具有正的未使用的容量rij=uij-xij。后向边：从j连向i，该边具有正的流量xjiij未使用的容量rij=uij-xijij流量xji前向边后向边2020/1/30山东交通学院信息工程系9扩展增益路径法对于给定容量的增益路径，设r是所有前向边中未使用的容量和后向边中具有正的容量xji中的最小值。如果在每条前向边上增加容量r，在向后边上减去r，得到一个更大的可行流量。2020/1/30山东交通学院信息工程系10扩展增益路径的实现举例上图b中，增益路径1→4→3←2→5→6。(1,4),(4,3),(2,5),(5,6)是前向边，(3,2)是后向边，最小值r=1，根据r值进行调整，得到c。2020/1/30山东交通学院信息工程系11增益路径法性能退化路径生成次序如果不恰当，会对该方法效率产生巨大的影响，如下图：沿路径1→2→3→4对流量0进行增益，会得到(b)中值为1的流量。沿路径1→32→4对流量0进行扩展增益，会得到(c)中值为2的流量。共迭代2U次才能得到最大流量值2U。2020/1/30山东交通学院信息工程系12增益路径法性能退化2次得到最大流量值方法：沿路径1→2→4对流量0进行增益。沿路径1→3→4对流量0进行增益。增益路径法依赖于路径生成次序，生成次序不恰当，会对该方法效率产生巨大的影响。2020/1/30山东交通学院信息工程系13最短增益路径法基本思想：用广度优先查找，用数量最少的边来生成增益路径。具体策略：两个记号来标记一个新的(未标记)顶点第一个标记指出从源点到被标记顶点还能增加多少流量。第二个标记指出另一个顶点的名字。2020/1/30山东交通学院信息工程系14两个记号来标记一个新的(未标记)顶点第一个标记指出从源点到被标记顶点还能增加多少流量。第二个标记指出另一个顶点的名字。第二个标记加上+或-号，用来指出该顶点是通过前向边还是后向边得到的。2020/1/30山东交通学院信息工程系15如果未标记顶点j是由从i到j的有向边和遍历队列中的前面顶点i相连接，而且j具有大于0的未使用容量rij=uij-xij,那么顶点j就标记为lj,i+，其中lj=min{li,rij}。2020/1/30山东交通学院信息工程系16如果未标记顶点j是由从j到i的有向边和遍历队列中的前面顶点i相连接，而且j具有大于0的流量xij,那么顶点j就标记为lj,i-，其中lj=min{li,xij}。2020/1/30山东交通学院信息工程系17处理2结点时，由于从1到2未使用容量为2，因此2顶点标记为min{,2},1+.处理3结点时，由于从2到3未使用容为5，因此3顶点标记为min{2,5},2+.这种标记的遍历结束于汇点6，沿着路径1→2→3→6用2对流量进行增益。2020/1/30山东交通学院信息工程系18下一次迭代时过程。这种标记的遍历结束于汇点6，沿着路径1→4→3→2→5→6用1对流量进行增益。2020/1/30山东交通学院信息工程系19再一次迭代时由于没有增益路径(汇点没有被标记)，当前流量已经是最大的了。2020/1/30山东交通学院信息工程系20标号法步骤如下：第一步找出一个初始可行流fij(0),例如所有弧的流量fij(0)=0.第二步利用广度优先搜对点进行标号找出一条增益路径。（1）起点标号（∞）（2）选一个点vi已标号且另一端未标号的弧沿着某条链向收点检查（a）如果弧是前向弧且有fij＜cij，则vj标号θj=cij﹣fij（b）如果弧是后向弧且有fij﹥0，则vj标号θj=fij2020/1/30山东交通学院信息工程系21当收点已得到标号时，说明已找到增益路径，依据v的标号反向追踪得到一条增益路径。当收点不能得到标号时，说明不存在增益路径，计算结束第三步调整流量(1)求增广链上点的vi标号的最小值，得到调整量号(2)调整流量jjmin=2020/1/30山东交通学院信息工程系22fij+θ（vi，vj）∈u+f1=fij﹣θ（vi，vj)∈u-fij（vi，vj)u得到新的可行流f1，去掉所有标号，返回到第二步从发点重新标号寻找增益路径，直到收点不能标号为止。2020/1/30山东交通学院信息工程系23定义：（截集或割集）如果N表示某网络中所有点的集合，将N分成两个子集S与S，使得发点v0在S内，收点vn在S内，则称（S，S）为分离发点与收点的割集。显然，SS=N，SS=，V0S，VnS2020/1/30山东交通学院信息工程系24v0vnv2v1a割集a：v0v1，v0v2，v0vn2020/1/30山东交通学院信息工程系25v0vnv2v1b割集b：v1vn，v2vn，v0vn2020/1/30山东交通学院信息工程系26v0vnv2v1c割集c：v1vn，v1v2，v2v1，v0v2，v0vn2020/1/30山东交通学院信息工程系27v0vnv2v1d割集d：v0v1，v1v2，v2v1，v2vn，v0vn2020/1/30山东交通学院信息工程系28定义（割的容量）从S中各顶点到S中各顶点全部容量之和称为割的容量（截量），用（S，S）表示。2020/1/30山东交通学院信息工程系29割集a:Ca=C01+C02+C0n割集b:Cb=C1n+C2n+C0n割集c:Cc=C1n+C12+C02+C0n割集d:Cd=C01+C21+C2n+C0n2020/1/30山东交通学院信息工程系30v0vnv2v1cSS在截集c中边v2v1是反向的，其容量视为零。2020/1/30山东交通学院信息工程系31v0vnv2v1dSS在截集d中边v1v2是反向的，其容量视为零。2020/1/30山东交通学院信息工程系32定义（最小截量）一个网络中，各种截集中容量最小的称为最小截量，用minC(S,S)表示。2020/1/30山东交通学院信息工程系33现在我们把一个网络看成是一个自来水管网络，煤气管网络，电力线网络或公路网络，铁路网络，水运交通网络等，都可以归纳成一个运输问题，称为网络流，值得关心问题是在这样一个网络中最大流为多少？2020/1/30山东交通学院信息工程系34定义（流）若对网络N，函数f满足如下条件：（1）0fijCij(i,j)E(N)（2）f-(vi)=f+(vi)iV(N)则称f为N的一个网络流，简称流。2020/1/30山东交通学院信息工程系35定义（最大流）若f为N的一个网络流，而N中不存在流f，使得ff，则称f为一个最大流，记Maxf。2020/1/30山东交通学院信息工程系36截量C与流f的关系任一有向网络流，如果f是从发点到收点的流量，C(S,S)是任一个截集，则fC(S,S)。等号什么时候成立？网络中最大流量等于它的最小割的容量。