最大流在信息学竞赛中应用的个模型江涛.doc

《最大流在信息学竞赛中应用的个模型江涛.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、最大流在信息学竞赛中应用的一个模型江涛关键字：网络可行流最大流附加网络无源汇必要弧流的分离有上下界的最大流建模引言：最大流类的模型在当今信息学比赛中有相当广泛的应用。但在教学中，发现很多同学对流模型的原理和变形并不掌握，只是记下经典的算法和题目，以便比赛中套用。这当然有很大的局限性，也不是学习之正道。本讲想通过对最大流模型，特别是附加网络的一些分析、讨论，达到抛砖引玉目的。一、网络与流的概念一个实例：运输网络D3SABCTE3214235图1.1网络定义：l一个有向图G=(V，E)；l有两个特别的点：源点s、汇点t；l图中每条边(u,v)∈E，有一个非负值的容量C

2、(u,v)记为G=(V，E，C)68/22网络三要素：点、边、容量可行流定义：是网络G上的一个“流”，即每条边上有个“流量”P(u,v)，要满足下面两个条件：流的容量限制---弧：对任意弧(u,v)---有向边流的平衡---点：除源点和汇点，对任意中间点有：流入u的“流量”与流出u的“流量”相等。即：有网络的流量：源点的净流出“流量”或汇点的净流入“流量”。即：注意，我们这里说的流量是一种速率，而不是指总量。联系上面所说的实例，下面是一个流量为1的可行流：D3SABCTE3104234111图1.2标准图示法：D0/3SABCTE0/31/21/10/40/20/

3、31/568/22图1.3例1.1有一个n*m的国际棋盘，上面有一些格子被挖掉，即不能放棋子，现求最多能放多少个棋子“车”，并保证它们不互相攻击(即：不在同一行，也不在同一列)？分析：1)行、列限制---最多只能一个车控制；2)车对行、列的影响---一个车控制一个行和边；例子：图1.468/22123123st111111图1.5显然，我们要求车最多，也就是求流量最大---最大流问题。下面是一个解：123123st111111图1.6即(1,3)、(2,1)、(3,2)格上各放一个车，可得到一个最优方案。二、最大流问题寻找网络G上可能的最大流量(和一个有最大流量的

4、可行流方案)，即为网络G上的最大流问题。我们再来看看图1.1的运输网络例子，我们可能通过改进图1.3得到下面这样的可行流：D1/3SABCTE1/32/21/10/40/20/31/5图2.1求解过程中的困惑：[问题2.1]流量还可能增加吗？[问题2.2]如果能增加，怎样改进？68/22三、最大流算法的核心---增广路径退流的概念---后向弧仔细分析图2.1，我们发现，流量是可以增加的：D1/3SABCTE1/31/21/11/41/21/30/5图3.1D2/3SABCTE2/32/21/11/41/21/31/5把一个流量弧(B,C)和(C,T)上的流退回到B

5、点，改道从B-D-E-T走，就可以增加流量了，如下图：图3.2图3.1不能“直接寻找增大流的路径”，是因为当初有些弧上的流选择不“恰当”，要“退流”。一种直观的想法就是：调整或重新搜索“当初的选择”---难!能不能保留以前的工作，而在这之上改进呢？经过专家们研究发现，加入退流思想---后向弧，就能再次“直接寻找增大流的路径”。增广路径(可改进路径)的定义若P是网络中连结源点s和汇点t的一条路，我们定义路的方向是从s到t，则路上的弧有两种：l前向弧---弧的方向与路的方向一致。前向弧的全体记为P+；l后向弧---弧的方向与路的方向相反。后向弧的全体记为P-；68/2

6、2设F是一个可行流，P是从s到t的一条路，若P满足下列条件：在P+的所有前向弧(u,v)上，0≦f(u,v)

7、我们把已经有的流量从容量中分离出来表示，引入一个与原问题等价的附加网络1：残留网络。D2SABCTE200423411112图4.1其中，前向弧(黑色)上的容量为“剩余容量”68/22=C(u,v)-f(u,v)；后向弧(红色)上的容量为“可退流量”=f(v，u)。68/22改造后的网如下：D2SABCTE2423411112图4.2在这张图上，我们找增广路径显的非常直观了!结合增广路径，我们有如下定理：最大流定理如果残留网络上找不到增广路径，则当前流为最大流；反之，如果当前流不为最大流，则一定有增广路径。证明涉及最小割概念，不是本文重点，由于时间关系，从略。至此

8、，[问题2