浅谈网络流算法与几种模型转换.doc

浅谈网络流算法与几种流模型吴 迪 1314010425摘要：最大流的算法,算法思想很简单,从零流开始不断增加流量，保持每次增加流量后都满足容量限制、斜对称性和流量平衡3个条件。只要残量网络中不存在增广路，流量就可以增大，可以证明他的逆命题也成立；如果残量网络中不存在增广路，则当前流就是最大流。这就是著名的增广路定理。s-t的最大流等于s-t的最小割，最大流最小割定理。网络流在计算机程序设计上有着重要的地位。关键词：网络流 Edmonds-Karp 最大流 dinic 最大流最小割 网络流模型 最小费用最大流正文：图论中的一种理论与方法，研究网络上的一类最优化问题 。1955年 ，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D= （V、E、C） ， 其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点v1v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问 ：若从起点v1将物资运送到终点v6去 ，应选择那条路线才能使总运输距离最短?这样一类问题称为最短路问题 。 如果把上图看作一个输油管道网 ， v1 表示发送点，v6表示接收点，其他点表示中转站 ，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。最大流理论是由福特和富尔克森于 1956 年创立的 ，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善 。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。先来看一个实例。现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如下：每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。若有向图G=(V,E)满足下列条件：1、 有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点S便称为源点，或称为发点。2、 有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点，或称为收点。3、 每一条弧都有非负数，叫做该边的容量。边(vi, vj)的容量用cij表示。则称之为网络流图，记为G = (V, E, C)介绍完最大流问题后，下面介绍求解最大流的算法,算法思想很简单,从零流开始不断增加流量，保持每次增加流量后都满足容量限制、斜对称性和流量平衡3个条件。三个基本的性质:如果 C代表每条边的容量 F代表每条边的流量一个显然的实事是F小于等于C 不然水管子就爆了这就是网络流的第一条性质 容量限制(Capacity Constraints):F C再考虑节点任意一个节点 流入量总是等于流出的量 否则就会蓄水或者平白无故多出水这是第二条性质 流量守恒(Flow Conservation): F = F当然源和汇不用满足流量守恒最后一个不是很显然的性质 是斜对称性(Skew Symmetry): F = - F这其实是完善的网络流理论不可缺少的 就好比中学物理里用正负数来定义一维的位移一样百米起点到百米终点的位移是100m的话 那么终点到起点的位移就是-100m同样的 x向y流了F的流 y就向x流了-F的流把图中的每条边上的容量于流量之差计算出，得到参量网络。我们的算法基于这样一个事实：参量网络中任何一条从s到t的有向道路都对应一条原图中的增广路-只要求出该道路中所有残量的最小值d，把对应的所有边上的流量增加d即可，这个过程叫做增广。不难验证，如果增广前的流量满足3个条件，增广后仍满足。显然，只要残量网络中不存在增广路，流量就可以增大，可以证明他的逆命题也成立；如果残量网络中不存在增广路，则当前流就是最大流。这就是著名的增广路定理。“找任意路径”最简单的办法无疑是用DFS，但很容易找出让他很慢的例子。一个稍微好一些的算法是BFS，它足以应对数据不刁钻的网络流题目，这就是Edmonds-Karp算法。在下面的代码中，远点和回电保存在变量s和t中，运行结束后，s-t的净流量保存在变量f中。 queue q; memset(flow, 0, sizeof(flow); int f = 0; while(1) memset(a, 0, sizeof(a); as = INF; q.push(s); while(!q.empty() int u = q.front(); q.pop(); for(int v = 1;v flowuv) pv = u; q.push(v); av = aucapuv-flowuv?au:capuv-flowuv; if(at = 0) break; for(int u = t; u != s; u = pu) flowpuu += at; flowupu -= at; f += at; 最大流最小割定理：1. 在优化理论中，最大流最小割定理指：在一个网络流中，能够从源点到达汇点的最大流量，等于，如果从网络中移除就能够导致网络流中断的边的集合的最小容量和。2.定义：假设N=(V,E)是一个有向图，其中结点s和t分别是N的源点和汇点。边(u,v)的容量c(u,v)定义为：能够通过该边的最大流量。通过每条边的流f(u,v)的需要满足如下约束：（1）f(u,v) 0。最小费用最大流问题，就是求网络G的最大流f且使费用b(f)最小。这样的流称为最小费用最大流。二、算法思想用Ford-Fulkerson算法的思想，不断地在残留网络中寻找增广路，只不过这个增广路是当前网络中s到t的以单位流量费用为权的最短路，对这条增广路进行操作。由于费用有负值，建议用SPFA算法。网络流中最大流的dinic算法:简介：dinic网络流最大流的优化算法之一，每一步对原图进行分层，然后用DFS求增广路。时间复杂度是O(n2*m).算法介绍：层次图层次图，就是把原图中的点按照点到源的距离分“层”，只保留不同层之间的边的图。算法流程1、根据残量网络计算层次图。2、在层次图中使用DFS进行增广直到不存在增广路。3、重复以上步骤直到无法增广。时间复杂度因为在Dinic的执行过程中，每次重新分层，汇点所在的层次是严格递增的，而n个点的层次图最多有n层，所以最多重新分层n次。在同一个层次图中，因为每条增广路都有一个瓶颈，而两次增广的瓶颈不可能相同，所以增广路最多m条。搜索每一条增广路时，前进和回溯都最多n次，所以这两者造成的时间复杂度是O(nm)；而沿着同一条边(i,j)不可能枚举两次，因为第一次枚举时要么这条边的容量已经用尽，要么点j到汇不存在通路从而可将其从这一层次图中删除。综上所述，Dinic算法时间复杂度的理论上界是O(n2*m)。最大流问题的几种简单的变形1.多源多汇问题多源多汇问题的化归其实很容易想到增设总源、总汇，很容易地转化为单源汇问题。2.点有容量问题常用拆点法，一个点专门入边，另一个专门出边，入点向出点连一条边注明容量即可。3.多重边问题多重边问题要具体分析，有的只要把容量累加即可，有的考虑到其它信息的不同（如费用等），或许还需要对边排序。若出现反向边，则定义2中的反向边容量不为0，须谨慎处理。4.无向图问题若边可以随意指定方向，则可以通过枚举方向，或者用不断调整的思想解决。一种最小割问题模型建立：问题假设有n个项目和m种设备。项目pi能够产生效益r_pi，设备qj需要耗费c_qj。每个项目需要多种设备，每种设备可以被多种项目使用。问题是，决定实施哪几个项目，以及购买哪几种设备，使得效益最高。构建一个这样的网络：假设源点和汇点s和t，s与每个项目pi之间有一个边，其容量为r_pi；每个设备