2023年7月30日发(作者：)

⽹络流模型总结⽹络流模型总结福州⼀中肖汉骏【引⾔】：“许多问题可以先转化为⽹络流问题，再运⽤最⼤流算法加以解决。⽽发现问题本质，根据最⼤流算法的特点，设计与之相配的数学模型是运⽤最⼤流算法解决问题的重要步骤。”“⽹络流在具体问题中的应⽤，最具挑战性的部分是模型的构造。这没⽤现成的模式可以套⽤，需要对各种⽹络流的性质了如指掌（⽐如点有容量、容量有上下限、多重边等等），并且归纳总结⼀些经验，发挥我们的创造性。”注：本⽂⼤部分出⾃江涛⽼师讲稿及⽹络资料图1.1【理论部分】： ⼀、引⼊如同我们可以把⼀个实际的道路地图抽象成⼀个有向图来计算两点之间的最短路径，我们也可以将⼀个有向图看作⼀个流⽹络来解决另⼀类型的问题。流⽹络⽐较适合⽤来模拟液体流经管道、电流在电路⽹络中的运动、信息⽹络中信息的传递等等类似的过程。⼀个实例：运输⽹络参看下图，给定⼀个有向图G=(V ,E)，把图中的边看作管道，每条边上有⼀个权值，表⽰该管道的流量上限。给定源点s 和汇点t ，现在假设在s 处有⼀个⽔源，t 处有⼀个蓄⽔池，问从s 到t 的最⼤⽔流量是多少，类似于这类的问题都可归结为⽹络流问题。在流⽹络中，每条有向边可以被看导管。每根导管有⼀个固定的容量，代表物质流经这个导管的最⼤速率，例如⼀个管道每⼩时最多能流过200加仑液体或者⼀根电线最多能承载20安培的电流。流⽹络中的顶点可以看作是导管的连接处。除了源点和汇点之外，物质流进每个点的速率必须等于流出这个点的速率。如果我们把研究的物质特化为电流，这种“流的保持”属性就好像电路中的基尔霍夫电流定律⼀样。⼆、⽹络流相关定义1⽹络定义：⼀个有向图 G=(V ，E)；有两个特别的点：源点s 、汇点t ；图中每条边(u,v)∈E ，有⼀个⾮负值的容量C(u,v) 记为 G=(V ，E ，C)，⽹络三要素：点、边、容量可⾏流定义：是⽹络G 上的⼀个“流”，即每条边上有个“流量”P(u,v)，要满⾜下⾯两个条件：流的容量限制——弧：),(),(0v u C v u P ≤≤ 对任意弧(u,v)---有向边流的平衡限制——点：除源点和汇点，对任意中间点有：流⼊u 的“流量”与流出u 的“流量”相等。即：{,}(,)(,)0x Vx Vu V s t P x u P u x ∈∈?∈--=∑∑有⽹络的割：⼀个s-t 割是这样⼀个边的集合，把这些边从⽹络中删除之后，s 到t 就不可达了。或者，正式的说，⼀个割把顶点集合分成A,B 两个集合，其中s 在A 中,t 在B 中，⽽割中的边就是所有从A 出发，到达B 的所有边。割的容量就是割中所有边的容量的和。正式的说，就是所有从A 到B 的边的容量的和。⽹络的流量：源点的净流出“流量” 或 汇点的净流⼊“流量”。即：∑∑∑∑∈∈∈∈-=-Vx Vx Vx Vx x t P t x P s x P x s P ),(),(),(),(注意，我们这⾥说的流量是⼀种速率，⽽不是指总量。联系上⾯所说的实例，下⾯是⼀个流量为1的可⾏流：图2.2标准图⽰法：三、⽹络流相关定义2 下⾯我们⽤数学语⾔来进⾏相关概念的定义： 设G=(V ,E)是⼀个流⽹络，设c(u,v)>＝0表⽰从u 到v 的管道的流量上限。设s 为源，t 为汇。G 的流是⼀个函数f:V×V→R ，且满⾜下⾯三个特征：处理最⼩费⽤最⼤流，则反向边的费⽤为正向边的费⽤的相反数。四、解决最⼤流问题常⽤算法⼀览1. 预览寻找⽹络G 上可能的最⼤流量(和⼀个有最⼤流量的可⾏流⽅案)，即为⽹络G 上的最⼤流问题。它是⽹络流问题中最基本的问题，⽽⽹络流问题⼜可以归结为⼀类特殊的线性规划问题。解决最⼤流问题的常⽤到Ford-Fulkerson ⽅法，之所以称其⽅法⽽不是算法，是因为在这种思想下包含着若⼲种时间复杂度不同的实现，其中较多地是使⽤Edmonds-Karp 算法。与此相对，Push-relabel 算法采⽤了与Ford-Fulkerson ⽅法完全不同的思考⾓度，降低了渐进意义下的时间复杂度。⽽relabel-to-front 算法则是对Push-relabel 算法的改良和精炼，效率更佳。可以看出，当给定的有向图⽐较稀疏时，三种算法的效率不会相差太多，但当⽹络稠密时，relabel-to-front 算法在效率上有着明显的优势。图4.12. Ford-Fulkerson ⽅法求解过程中的困惑：[问题1]流量还可能增加吗？[问题2]如果能增加，怎样改进？ 退流的概念——后向弧仔细分析图4.1，我们发现，流量是可以增加的：把⼀个流量弧(B,C)和(C,T)上的流退回到B 点，改道从B-D-E-T ⾛，就可以增加流量了，如下图：图4.1不能“直接寻找增⼤流的路径”，是因为当初有些弧上的流选择不“恰当”，要“退流”。 ⼀种直观的想法就是：调整或重新搜索“当初的选择”——难！能不能保留以前的⼯作，⽽在这之上改进呢？经过专家们研究发现，加⼊退流思想——后向弧，就能再次“直接寻找增⼤流的路径”。2) 增⼴路径(可改进路径)的定义若P 是⽹络中连结源点s 和汇点t 的⼀条路，我们定义路的⽅向是从s 到t ，则路上的弧有两种：前向弧——弧的⽅向与路的⽅向⼀致。前向弧的全体记为P+；后向弧——弧的⽅向与路的⽅向相反。后向弧的全体记为P-； 设F 是⼀个可⾏流，P 是从s 到t 的⼀条路，若P 满⾜下列条件： 在P+的所有前向弧(u,v)上，0<=f(u,v)本图中：S-A-C-B-D-E-T 为⼀增⼴路径。其中(C,B)为后向弧，其它为前向弧。3) 增⼴路径上的改进算法求路径可改进量；}u)f (v, ),(),({min )(),(、后向弧前向弧v u f v u C P C Pv u f -=∈修改增⼴路径上的流量；4) 残留⽹络由于要考虑前向、后向弧，分析、描述时不简洁，直接在图上看也不容易看出增⼴路径。 因此我们把已经有的流量从容量中分离出来表⽰，引⼊⼀个与原问题等价的残留⽹络。其中，前向弧(⿊⾊)上的容量为“剩余容量”=C(u,v)-f(u,v)；后向弧(红⾊)上的容量为“可退流量”=f(v，u)。在这张图上，我们找增⼴路径显的⾮常直观了!结合增⼴路径，我们有如下定理：最⼤流-最⼩割定理：如果残留⽹络上找不到增⼴路径，则当前流为最⼤流；反之，如果当前流不为最⼤流，则⼀定有增⼴路径。最⼤流值对应最⼩割。任何图中，从s到t的最⼤流等于所有(s,t)割的容量的最⼩值。5)算法流程⼀般的Ford-Fulkerson⽅法具有迭代性质，我们把顶点u和v之间的流记作f(u,v)。那么在最开始，我们对所有的u,v∈V置f(u,v)=0。在每次的迭代过程中，通过找到⼀条增⼴路径来使|f|增加。在这⾥，我们可以简单地认为所谓的“增⼴路径”就是⼀条可以传送⽐当前更多流的从源点s到汇点t的路径，⼀旦找到了这样的路径，我们就可以得到⼀个⽐原流流量更⼤的新流。重复这个过程，直到不存在增⼴路径为⽌，这就是Ford-Fulkerson⽅法的主要过程，可以⽤伪码表⽰如下：FORD-FULKERSON-METHOD(G,s,t)将流f初始化为0while存在⼀条增⼴路径pdo顺沿p增加freturnf实现Ford-Fulkerson的时间复杂度主要取决于如何寻找增⼴路径p。常见的有深度搜索dfs、宽度搜索bfs以及优先搜索pfs——即类似Dijkstra算法的标号法。Edmonds-Karp实现正是通过采⽤了bfs的搜索策略得以使其复杂度达到O(V*E2)。3. ⼀般性的push-relabel算法很多渐进意义下最优的算法都是采⽤了push-relabel算法的思想，⽽且很多其他的相关问题，⽐如最⼩费⽤流问题，也可以⽤这种⽅法很好的解决。⾸先介绍的是⼀般性的push-relabel算法。不同于Ford-Fulkerson⽅法在残留⽹络中寻找增⼴路径的⽅式，push-relabel算法在运⾏的过程中只关注某⼀个顶点以及它的相邻顶点，在这个过程中，它并不像Ford-Fulkerson⽅法保持着“流的保持”性质，⽽是以⼀个“先流”进⾏运作。这个先流同样是⼀个V×V→R的函数，满⾜容量限制和斜对称性，同时，它对所有的u∈V-{s}满⾜f(v,u)>=0。我们记e(u)=f(v,u)。如果e(u)>0我们就说顶点u溢出。为了步⼊正题，我们还需要介绍push-relabel算法引⼊的⼀个额外的⾼度函数。设G=(V,E)是⼀个流⽹络，源点是s，汇点是t，f是G中的⼀个先流。如果函数h:V→N满⾜h(s)=|V|，h(t)=0，⽽且对残留⽹络中所有的边(u,v)有h(u)<=h(v)+1，那么称h是⼀个⾼度函数。正如其名称⼀样，push-relabel算法有两个基本操作:push和relabel。⼀般性的push-relabel 算法就是通过往复执⾏这两种操作完成的：GENERIC-PUSH-RELABEL(G)先流初始化while存在可以执⾏的push或relabel操作选择⼀个可以执⾏的push或relabel操作执⾏下⾯具体介绍⼀下这两个基本操作。1)普通实现通过证明，在⼀般性的push-relabel算法执⾏过程中，relabel操作的执⾏次数⼩于2|V|2，push操作的执⾏次数⼩于2|V||E|+4|V|3+4|E||V|2，⽽每个relabel操作的耗时在O(V)级，每个push的耗时在O(1)级，选择⼀个可以执⾏的操作也可以在O(1)内完成，因此，存在具体的实现使得⼀般性的push-relabel算法时间复杂度达到O(V2*E)。2)relabel-to-front算法通过引⼊邻接表和许可边的概念，relabel-to-front算法在push-relabel算法的基础上进⼀步提升了效率，使时间复杂度可以达到O(V3)，但是该算法的步骤和证明的过程⽐较繁琐，在这⾥就略去了，有兴趣的读者可以参考《算法导论》。五、最⼤流问题的⼏种变形1. 多源多汇问题多源多汇问题的化归其实很容易想到——增设总源、总汇，很容易地转化为单源汇问题。2. 点有容量问题常⽤拆点法，⼀个点专门⼊边，另⼀个专门出边，⼊点向出点连⼀条边注明容量即可。3. 多重边问题多重边问题要具体分析，有的只要把容量累加即可，有的考虑到其它信息的不同（如费⽤等），或许还需要对边排序。若出现反向边，则定义2中的反向边容量不为0，须谨慎处理。4. ⽆向图问题若边可以随意指定⽅向，则可以通过枚举⽅向，或者⽤不断调整的思想解决。六、最⼩费⽤最⼤流问题可以证明，只要把最⼤流算法中的每次“找增⼴路径”改为“找费⽤最⼩的增⼴路径”即可。每次⽤SPFA寻找费⽤最⼩的增⼴路径，沿它改进。还有⼀种找负权圈的算法。七、有上下界的⽆源汇可⾏流问题1. 定义在⼀个有上下界的流⽹络G中，不设源和汇，但要求任意⼀个点i都满⾜流量平衡条件：∑∑∈∈=EviEiuvifiuf),(),(),(),(且每条边(u,v)都满⾜容量限制B(u,v)≤f(u,v)≤C(u,v)的条件下，寻找⼀个可⾏流f，或指出这样的可⾏流不存在。不妨称这个问题为⽆源汇的可⾏流问题。实例：变形⼀笔画问题：在⼀个有向图，判断能不能⼀笔画访问所有的边，但有些弧上可以画多次。我们⽤容量C(u,v)表⽰弧(u,v)最多可以重复画的次数。2. 分析我们遇到了两个困难：⾸先，从没有下界到有了下界，我们在求最⼤流时，不⼀定能保证下界，使之成为可⾏流；其次，没有了源、汇，以前的最⼤流算法就成了⽆的之⽮，⼀定要有源和汇。但同时，⽆源汇也是⼀个契机，因为——没了旧的源、汇，我们可以更加⾃由地按需要设⽴新的源、汇。从⽽使⽹络模型变成⼀个新的等价⽹络!3. 必要性流的分离1)基本思想总体上看，下界是⼀条弧必需要满⾜的确定值，我们能不能把这个下界“分离”出去，从⽽使问题转为下界为0，也就是普通的最⼤流问题的可⾏流问题？2)朴素想法先观察⼀条路径情况图7.4如同例7.1直接把容量下界减掉怎样？2,6 3,41图7.53) 必要弧显然，如果图7.5中的流想通过加上下界来对应地得到图7.4中的解是不可能的。因此，这⾥流的分离不能⽤简单减掉的⽅法，⽽应该把⼀个弧分离成两个弧。即加⼀个容量等于下界的必要弧，使可⾏流分离在这两个弧上。如下图：图7.6⼀个⽆源汇的可⾏流的⽅案⼀定是必要弧是满的。因此现在我们先要找⼀个把必要弧充满的可⾏流(当然也要满⾜上界限制)。现在我们的⽬光焦点是必要弧，把他们集中起来：由于必要弧都是要饱和的，显然与下⾯图是等价的。图7.84. 问题的解决进⼀步，去除X,Y 之间的连线，使Y 、X 分别成为新的源和汇。4 123 3图7.9对这个⽹络求最⼤流，如果Y 到X 的最⼤流能为2+3+3，则显然有： 必要弧为满 满⾜容量上界限制 保持流平衡⾄此，有上下界的⽆源汇可⾏流问题已经圆满解决。⼋、有上下界的有源汇最⼤流问题1. 定义在⼀个有上下界的流⽹络G 中，设源和汇，要求其它任意⼀个点i 都满⾜流量平衡条件：∑∑∈∈=Ev i Ei u v i f i u f ),(),(),(),(且每条边(u ,v )都满⾜容量限制B (u ,v )≤f (u ,v )≤C (u ,v )的条件下，寻找⼀个可⾏且最⼤的流f ，或指出这样的可⾏流不存在。实例：餐厅问题2. 直观思想1) 思路对于有上下界的有源汇最⼤流问题，我们可以看成是在满⾜“必要”的下界情况时，求最⼤流(或最⼩费⽤等问题)。直观的⼀种思路就是：求⼀个满⾜下界的流f1;在f1基础上⽤寻找增⼴路径的⽅法，扩⼤流，直到没有增⼴路径； 实现的关键点在于：问题1：怎样求满⾜下界⽽⼜不超过上界的⼀个流f1？ 问题2：怎样增⼤流f1，⽽⼜同时不破坏下界？我们可以通过把有上下界的有源汇最⼤流问题，通过加条边(T,S)，容量+∞，改造成为有上下界的⽆源汇可⾏流问题，求出可⾏流，再还原成为原问题的可⾏流。2) 加边(T,S) ，改造为⽆源汇可⾏流问题通过加条边(T,S)，容量+∞，问题改造成为有上下界的⽆源汇可⾏流问题。3) 分离、割开必要弧，改造为普通最⼤流问题再来看看下例，先分离必要弧：割开所有必要弧，加两个附加源Y和汇X：⾄此：问题成功转化为求Y到X的普通最⼤流问题。4)还原为⽆源汇可⾏流问题当求出该模型的最⼤流为1+1+1+1+1=5时，我们再反过来做：把“进X”和“出Y”的对应边连上，则找到⼀个有上下界容量限制的⽆源汇可⾏流。再把弧(T,S)拿⾛，则问题1解决。1/+∞注意：原问题可⾏流存在⽆解情况，即附加⽹络3的最⼤流不能把源(或汇)相连的弧饱和。不同于普通最⼤流：因下界为0时，⼀定有解。5)还原为有源汇最⼤流的原问题在得到⼀个可⾏流f1之后，现在我们再来看看问题7.2。我们再去掉边(T,S)，还原成有源汇最⼤流的原问题。如果要求这时的最⼤流，则可在这个基础上，找增⼴路径来增⼤流，最终求得⼀个符合要求的最⼤流⽅案。但是要注意的是，对必要弧，我们不能退流，因此相应的残留⽹络应对必要弧要单独处理，或直接暂时拿⾛。另外，这种情况下的增⼴路径改进，不会影响必要弧——即：不破坏下界。6) 流程求容量有上下界最⼤流的直观思想：3. ⼆分思想1) 思路周源同学在IOI2004国家集训队作业《⼀种简易的⽅法求解流量有上下界的⽹络中⽹络流问题》，是对上⾯⽅法的简单化。简化的模型没有了上⾯的步骤A 和B ，避免了⼆次改造⽹络，使编程容易很多。当然，代价是要多次求最⼤流。这个⽅法中⽤⼆分法，确定容量下界的最⼤值，即⼆分(T,S)可能的最⼤流。另外，⽂中还提到：“在⼀个容量有上下界的流⽹络G 中，求源点s 到汇点t 的⼀个可⾏的最⼩流。…类似，只是在加⼊弧(t ,s )后⼆分(t ,s )的容量上界C (t ,s )即可。”可见这个简化的⽅法在竞赛中⽤途很⼴。2) 流程简化⽅法的基本思想：⾄此，我们已经清楚地阐述了⼀个关于⽹络流⽅⾯的模型：对于“必要的流量”，⽤必要弧分离出来，⽤⽆源汇可⾏流模型求得其上的⼀个可⾏流⽅案。当然，如果⽆解，也可以判断出。九、⼆部图的最⼤匹配与⽹络最⼤流的关系有⼀定离散基础的读者应当对⼆部图的最⼤匹配不陌⽣，但它和⽹络流之间有什么具体的联系呢，请看下图：是的，如果我们设⼆部图两部分的点集分别为L与R,现在添加源点s和汇点t,对所有的v∈L添加有向边(s,v)，再对所有的v∈R添加有向边(v,t)，再将原⼆部图中所有的⽆向边改为⾃L中的点指向R中的点的有向边，就构造了⼀个流⽹络。如果这个⽹络中每条边的容量限制都设为1，那么它的最⼤流数值就等于⼆部图的匹配数，⽽且这个最⼤流和⼆部图中的最⼤匹配是⼀⼀对应的。⽤邻接表存储的⼆部图可以⽤匈⽛利算法在O(VE)的时间内找到最⼤匹配，这意味着⽤⽹络流解决⼆部图最⼤匹配问题并⾮最具效率的选择，但是它⾄少向我们展⽰了⽹络流的⼀个侧⾯应⽤。除此之外，⽹络流的变形和演化还可以解决很多具有普遍意义的问题，⽐如最⼩路径覆盖等等。【总结归纳】：⽤与原问题等价的模型使问题的描述、思考⽅便简洁⽽统⼀。在信息学竞赛中很多最⼤流相关问题没有现成模式可以套⽤，但解决最⼤流问题的原理和思想是相通的，前⾯所说的构造等价的附加⽹络的思路和⽅法就是⼀种可以借⽤的“现成模式”。没有了源、汇，以前的最⼤流算法就成了⽆的之⽮，⼀定要有源和汇。那我们为什么还要把有源、汇的问题改成⽆源、汇呢？答案是破旧⽴新：没了旧的源、汇，我们可以更加⾃由地按需要设⽴新的源、汇。从⽽使⽹络模型变成⼀个新的附加⽹络!上⾯两节，我们对流的分离和流⽹络的等价变换做了进⼀步发挥。与之前所⽤⽅法技巧的⽐较：【参考资料】：[2001][江鹏]项⽬发展规划-试谈⽹络流的构造与算法[2002][⾦恺]浅谈⽹络流算法的应⽤最⼤流在信息学竞赛中应⽤的⼀个模型--江涛