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

浅谈网络流算法与几种流模型吴迪1314010425摘要：最大流的算法,算法思想很简单,从零流开始不断增加流量，保持每次增加流量后都满足容量限制、斜对称性和流量平衡3个条件。只要残量网络中不存在增广路，流量就可以增大，可以证明他的逆命题也成立；如果残量网络中不存在增广路，则当前流就是最大流。这就是著名的增广路定理。s-t的最大流等于s-t的最小割，最大流最小割定理。网络流在计算机程序设计上有着重要的地位。关键词：网络流Edmonds-Karp最大流dinic最大流最小割网络流模型最小费用最大流正文：HYPERLINK"http://baike.baidu.com/view/79350.htm"\t"http://baike.baidu.com/view/_blank"图论中的一种理论与方法，研究网络上的一类最优化问题。1955年，T.E.HYPERLINK"http://baike.baidu.com/view/112060.htm"\t"http://baike.baidu.com/view/_blank"哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R.福特和D.R.富尔克森等人给出了解决这类问题的HYPERLINK"http://baike.baidu.com/view/7420.htm"\t"http://baike.baidu.com/view/_blank"算法，从而建立了HYPERLINK"http://baike.baidu.com/view/152760.htm"\t"http://baike.baidu.com/view/_blank"网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图D=（V、E、C），其中V是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示HYPERLINK"http://baike.baidu.com/view/1469393.htm"\t"http://baike.baidu.com/view/_blank"两城镇间的公路长度。现在要问：若从起点v1将物资运送到终点v6去，应选择那条路线才能使总运输距离最短?这样一类问题称为最短路问题。如果把上图看作一个输油管道网，v1表示发送点，v6表示接收点，其他点表示中转站，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。最大流理论是由福特和富尔克森于1956年创立的，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善。最大流问题的研究密切了图论和HYPERLINK"http://baike.baidu.com/view/24356.htm"\t"http://baike.baidu.com/view/_blank"运筹学，特别是与HYPERLINK"http://baike.baidu.com/view/92066.htm"\t"http://baike.baidu.com/view/_blank"线性规划的联系，开辟了图论应用的新途径。先来看一个实例。现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如下：每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。若有向图G=(V,E)满足下列条件：有且仅有一个顶点S，它的入度为零，即d-(S)=0，这个顶点S便称为源点，或称为发点。有且仅有一个顶点T，它的出度为零，即d+(T)=0，这个顶点T便称为汇点，或称为收点。每一条弧都有非负数，叫做该边的容量。边(vi,vj)的容量用cij表示。则称之为网络流图，记为G=(V,E,C)介绍完最大流问题后，下面介绍求解最大流的算法,算法思想很简单,从零流开始不断增加流量，保持每次增加流量后都满足容量限制、斜对称性和流量平衡3个条件。三个基本的性质:如果C代表每条边的容量F代表每条边的流量一个显然的实事是F小于等于C不然水管子就爆了这就是网络流的第一条性质容量限制(CapacityConstraints):F<x,y>≤C<x,y>再考虑节点任意一个节点流入量总是等于流出的量