《经典网络流教程》由会员分享，可在线阅读，更多相关《经典网络流教程（51页珍藏版）》请在金锄头文库上搜索。
1、网络流 楼主亲阅 很详细的教程 网络流问题 由于人类对自然资源的消耗 人们意识到大约在2300年之后 地球就不能再居住了 于是在月球上建立了新的绿地 以便在需要时移民 令人意想不到的是 2177年冬由于未知的原因 地球环境发生了连锁崩溃 人类必须在最短的时间内迁往月球 现有n个太空站位于地球与月球之间 且有m艘公共交通太空船在其间来回穿梭 每个太空站可容纳无限多的人 而每艘太空船i只可容纳H i 个人 每艘太空船将周期性地停靠一系列的太空站 例如 1 3 4 表示该太空船将周期性地停靠太空站134134134 每一艘太空船从一个太空站驶往任一太空站耗时均为1 人们只能在太空船停靠太空站 或月球
2、 地球 时上 下船 初始时所有人全在地球上 太空船全在初始站 试设计一个算法 找出让所有人尽快地全部转移到月球上的运输方案 网络流问题 由文件input txt提供输入数据 文件第1行有3个正整数n 太空站个数 m 太空船个数 和k 需要运送的地球上的人的个数 其中1 m 13 1 n 20 1 k 50 接下来的n行给出太空船的信息 第i 1行说明太空船pi 第1个数表示pi可容纳的人数Hpi 第2个数表示pi一个周期停靠的太空站个数r 1 r n 2 随后r个数是停靠的太空站的编号 Si1 Si2 Sir 地球用0表示 月球用 1表示 时刻0时 所有太空船都在初始站 然后开始运行 在时刻1
3、 2 3 等正点时刻各艘太空船停靠相应的太空站 只有在0 1 2 等正点时刻才能上下太空船 将全部人员安全转移所需的时间输出到文件output txt中 如果问题无解 则输出0 网络可以被想象成一些输水的管道 括号内右边的数字表示管道的容量 左边的数字表示这条管道的当前流量 最大流为5 一个简单的例子 网络的最大流问题 一些符号和定义 V表示整个图中的所有结点的集合 E表示整个图中所有边的集合 G V E 表示整个图 s表示网络的源点 t表示网络的汇点 对于每条边 u v 有一个容量c u v c u v 0 如果c u v 0 则表示 u v 不存在于网络中 如果原网络中不存在边 u v 则
4、令c u v 0对于每条边 u v 有一个流量f u v 网络流的三个性质 1 容量限制 f u v c u v 2 反对称性 f u v f v u 3 流量平衡 对于不是源点也不是汇点的任意结点 流入该结点的流量和等于流出该结点的流量和 结合反对称性 流量平衡也可以写成 只要满足这三个性质 就是一个合法的网络流 也称为可行流 可行流至少有一个零流 最大流问题 定义一个网络的流量 记为 f 最大流问题 就是求在满足网络流性质的情况下 f 的最大值 弧的分类 若给定一个可行流F Fij 我们把网络中Fij Cij的弧称作饱和弧 Fij0的弧称作非零流弧若P是网络中联结源点s和汇点t的的一条路
5、不用管边的有向性 我们定义路的方向是从Vs到Vt 则路上的弧被分为两类 一类与路的方向一致 称为前向弧 另一类和路的方向相反 称为后向弧 残量网络 为了更方便算法的实现 一般根据原网络定义一个残量网络 其中r u v 为残量网络的容量 r u v c u v f u v 通俗地讲 就是对于某一条边 也称弧 还能再有多少流量经过 Gf残量网络 Ef表示残量网络的边集 a b 表示 流量f 容量c 如果网络中一条边的容量为0 则认为这条边不在残量网络中 r s v1 0 所以就不画出来了 另外举个例子 r v1 s c v1 s f v1 s 0 f s v1 f s v1 4 图1原网络 图2残
6、量网络 从残量网络中可以清楚地看到 因为存在边 s v2 3 我们知道从S到v2还可以再增加3单位的流量 因为存在边 v1 t 2 我们知道从v1到t还可以再增加2单位的流量 为什么要建立后向弧 其中像 v1 s 这样的边称为后向弧 它表示从v1到s还可以增加4单位的流量 但是从v1到s不是和原网络中的弧的方向相反吗 显然 从v1到s还可以增加4单位流量 这条信息毫无意义 那么 有必要建立这些后向弧吗 v1 t s v2 2 3 2 4 2 2 为什么要建立后向弧 显然 例1中的画出来的不是一个最大流 但是 如果我们把s v2 v1 t这条路径经过的弧的流量都增加2 就得到了该网络的最大流 注
7、意到这条路径经过了一条后向弧 v2 v1 如果不设立后向弧 算法就不能发现这条路径 从本质上说 后向弧为算法纠正自己所犯的错误提供了可能性 它允许算法取消先前的错误的行为 让2单位的流从v1流到v2 可改进路 增广路 可改进路定义 在残量网络中的一条从s通往t的路径 其中任意一条弧 u v 都有r u v 0 每一条前向弧都是非饱和弧 每一条后向弧都是非零流弧 绿色的即为一条可改进路 v1 t s v2 2 3 2 4 2 2 可改进路算法 可改进路算法 每次用BFS找一条可改进路 然后沿着这条路径修改流量值 实际修改的是残量网络的边权 使得总流量变得更大 修正的方法是 1 不属于可改进路P的
8、弧一概不变2 对于可改进路P上的所有前向弧加上a 后向弧减去a 这里a是一个可改进量 a既要尽量大 又要保证变化后0 Fij Cij 满足容量限制和平衡条件 因此a min min C前向弧ij F前向弧ij min F后向弧ij 如果不存在Vs到Vt的可改进路 算法停止 此时的流就是最大流 可改进路算法 如何很快找到可改进路 截集的定义 一个截集 S T 由两个点集S T组成 S T Vs属于S t属于T 一种定义S的方法 一旦Vt进入S集合 就表明找到一条可改进路 如果S集合扩展不下去而Vt又尚未进入S集合 则说明不存在可改进路 此时 除S外的顶点进入T集合 最大流最小截定理 截集间的流量
9、和 f S T 即 S中的任意一点与T中的任意一点组成的所有边上的流量之和 边的方向为从S中的节点到T中的节点 c r等函数都有类似的定义 截集的容量和 截集的残量网络容量和 任一个网络D中从Vs到Vt的最大流的流量等于分离Vs和Vt的最小截集的容量 最大流等价条件 网络流中这三个条件等价 在同一个时刻 1 f是最大流2 残量网络中找不到增广路径3 f c S T 结论1 1 f X X 0 由流量反对称性 2 f X Y f Y X 由流量反对称性 3 f X Y Z f X Z f Y Z 显然 4 f X Y Z f X Y f X Z 显然 1 f是最大流2 残量网络中找不到增广路径3
10、 f c S T 1 2证明 显然 假设有增广路径 由于增广路径的容量至少为1 所以用这个增广路径增广过后的流的流量肯定要比f的大 这与f是最大流矛盾 结论2 点集总流量为零 不包含s和t的点集 与它相关联的边上的流量之和为0 证明 f X V 由流量平衡 0 结论3 任意割的流量等于整个网络的流量 证明 f S T f S V f S S 由辅助定理1 f S V 由辅助定理1 f S V f S s V 同上 f s V 由辅助定理2 f 由 f 的定义 结论4 网络的流量小于等于任意一个割的容量 注意这个与辅助定理3的区别 这里是容量 即 f c S T 证明 f f S T 由定义 由
11、流量限制 c S T 2 3证明 定义S s v 在残量网络中s到v有一条路径 T V S 则 S T 是一个割 f f S T 由辅助定理3 而且 r S T 0 假设不为0 则在残量网络中 两个集合间必定有边相连 设在S的一端为v 在T的一端为u 那么 s就可以通过v到达u 那么根据S的定义 u就应该在S中 矛盾 所以 f f S T c S T r S T c S T 1 f是最大流2 残量网络中找不到增广路径3 f c S T 3 1证明 f 0 那么 f d肯定不能满足上面的条件 1 f是最大流2 残量网络中找不到增广路径3 f c S T 标号法寻求可改进路 Ford Fulker
12、son算法 从一个可行流F出发 可以设为零流 经过标号过程和调整过程 标号过程 网络中的顶点或者是标号点 分为已检查和未检查两种 或者是未标号点 每个标号点分为两部分 标号从哪个顶点得到 确定可改进量a 标号过程开始 总先给Vs标上 0 这时是标号而未检查的顶点 其余都是未标号点 取一个标号而未检查的标号Vi 对一切未标号点Vj 在Vi的全部相邻顶点都已标号后 Vi成为标号而已检查过的顶点 重复上述步骤 一旦Vt被标上号 表明得到一条从Vs到Vt的可改进路P 转入调整过程 标号法寻求可改进路 Ford Fulkerson算法 调整过程 采用 倒向追踪 的方法 从Vt开始 利用第一个标号找出可改
13、进路P 并以Vt的第二个标号L Vt 作为改进量a 改进P上的流量 例如 设Vt的第一个标号为Vk 或 Vk 则弧 Vk Vt 或 Vt Vk 是P上的弧 接下来再检查Vk的第一个标号 如此继续下去 直到查倒Vs为止 这时被找出的弧构成了P 令改进量a L Vt 即Vt的第二个标号 去掉所有的标号 对新的可行流Fij 重新进入标号过程 直到标号过程无法继续 例1求如下网络的最大流 标号法分析例1 1 标号过程首先给Vs标上 0 检查Vs 弧 Vs V2 上 Fs2 Cs2 3 不满足标号条件 弧 Vs V1 上 Fs1 10 则给V2记下标号为 V1 L V2 其中L V2 min L V1
14、F21 min 4 1 1 标号法分析例1 检查V2 弧 V2 V4 上 F24 3 C24 4 则给V4标号 V2 L V4 其中L V4 min L V2 C24 F24 min 1 1 1同理 标注V3为 V2 1 在V3 V4中任选一个进行检查 如V4 弧 V4 Vt 上 F4t 3 C4t 5 则给Vt标号 V4 L Vt 其中L Vt min L V4 C4t F4t min 1 2 1Vt有了标号 转入调整过程 标号法分析例1 2 调整过程如图为按照标号的第一个顶点找到的一个可改进路前向弧集合后向弧集合按a 1在P上调整对调整后的图重新进入标号过程 标号法分析例1 3 重新开始标
15、号过程当算法进行到检查V1时F21 0 F13 C13均不符合条件 标号无法继续 这时的可行流为最大流5 同时找到最小截集 S T S Vs V1 T V2 V3 V4 Vt C S T 5这也验证了最大流最小截定理的正确性 0 Vs 3 多源多汇网络的最大流 将其转换为单源单汇的问题 容量有上下界的网络的最大流 网络中的每条弧e对应两个数字B e 和C e 分别标识弧容量的上界和下界 那么如何求满足条件B e F e C e 的最大流 标号法中的网络是有上下界网络的一种特例 即B e 0 但当B e 0时有上下界的网络不一定存在可行流了 那么如何判断一个有上下界的网络有无可行流呢 容量有上下
16、界的网络的最大流 算法思路 将原网络转换为一个附加网络 新增加两个顶点和 分别称为附加源和附加汇对原网络N的每个顶点U加一条新弧 这条弧的容量为以U为尾的弧的容量下限之和 对原网络N的每个顶点U加一条新弧 这条弧的容量为以U为头的弧的容量下限之和 原网络的弧仍保留 弧容量修正为C e B e 再添两条新弧e st e ts 其容量均为 用标号法求此新网络的最大流 若结果能使流出的一切弧都满载 则原网络有可行流F e F e B e 否则无可行流 在原网络中运用标号法将可行流放大 从而得出最大流 容量有上下界的网络的最大流 例原网络 第一个数字为B e 第二个为C e 容量有上下界的网络的最大流 按照上述算法求得附加网络 并用标号法求此网络的最大流 发现从流出的流都满载 所以有可行流 容量有上下界的网络的最大流 按照F e F e B e 将此最大流还原为原网络的最大流 容量有上下界的网络的最大流 用标号法进行可行流放大 得到最大流10 容量有上下界的网络的最小流 按照前述附加网络方法求得可行流 只不过在放大可行流时 以t为源点 s为汇点进行 倒向求出的最大流为从s到t到的最小流 最小费
