学年论文-网络最大流问题算法的研究

《学年论文-网络最大流问题算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、桂林理工大学理学院信息与计算科学专业2014级学年论文网络最大流问题算法的研究学生姓名：谢林志学号：3141342303指导教师：谢海摘要：网络最大流问题是网络最优化问题中至关重要的部分，而最小费用最大流问题是最大流问题的延伸，它在生活和各个科学领域和工程等领域应用也愈加广泛。许多线性规划的实际问题都可转化为网络最大流的模型来求解，密切了图论与线性规划问题，开辟了图论应用的新途径。随着交通、电力、物流等大规模发展以及计算机技术的广泛应用和计算机科学技术的进步，人们对最大流问题的研究越来越深入，逐渐建立了较为完善的理论体系，从而建立了一系列有效算法。本文主要通过生活中经常遇到的实际例子，

2、利用标号法求解网络最大流与最小截问题。关键词：网络最大流；算法；最大流问题；最小截1、引言针对问题“随着网络应用的不断深入，人们对网络传输容量和服务质量的要求和期望也越来越高，设计高性能网络成为一项迫切的工作。缓存的配置直接影响网络的时延和丢失率，网络缓存和[1]网络传输容量的合理匹配，能很好提高网络性能。”和目前网络最大流问题的现状：“近年来,随着计算机科学技术和网络的快速发展，网络最大流问题得到了更深入的研究，并极大地推动了最大流问题的研究进展。然而，研究工作仍未结束：首先，在理论算法研究方面，人们还没有发现最大流问题算法时间复杂度的精确下界，更没有任何一个通用算法达到或接近问题的

3、下界；其次，在算法的实际性能方面，目前算法的实际性能也不能满足许多应用问题的要求；同时，最大流问题作为特殊的线性规划问题，它远比一般线性规划问题容易解决，发现应用领域中的问题和最大流问题的[2]联系可以使应用问题更好地得到解决。”本文利用一种求解网络最大流问题的算法去研究网络最大流在生活中的应用实例。其实，研究网络能够通过的流量是图论经常遇到的实际问题，例如,交通网络中要对车辆的最大通行能力进行研究；供水网络中要对水流量进行研究；电力网络中要对电流量进行研究等等。显然，这些网络都具有起点(发点)和终点(收点)、且每一弧都有明确的最大通过能力(容量)。但是因网络配置的原因，各弧的实际能力

4、往往达不到各弧的最大通过能力，利用标号结点法求解网络最大流是目前最优秀的算法之一。通过该算法能够计算出实际通过最大能力即网络的最大流量问题，可以充分发挥网络的设备能力，且能够明确得知如何改造网络可以使得最大流量增大。2、基本定义与定理2.1基本定义2.1.1网络定义1对于图GV,E的每一条边e，赋予一个数值We，数值可代表实际距离，花费代价，行车时间，交通费用等，这个数值We称为权值。如果一个图的所有的边都具有权值，则称此图为赋权图，或者称为网络。2.1.2流、可行流、最大流定义2设NV,A,C为一网络，f为定义在弧集A上的函数，若满足下列条件时：0f(vi,vj)

5、cij,(vi,vj)A1）0,vis,t（,1）f(vi,vj)f(vj,vi)F,vis（,2）2）vjvvjvF,vit（,3）则称f为该网络的可行流，简记为{fij}，fij表示弧vi,vj的流量。显然对于fij0，（vi,vj）A是网络的一个可行流。既满足弧流量的平衡条件和限制条件，又具有最大流量的可行流，简称最大流。其中1）为容量限制条件（1）式是结点平衡条件，表示中间点的流入量等于流出量，（2）式与（3）式分别表示从始点s发出的流量和终点t收到的流量F，也即网络总流量。2.1.3割集定义3设NV,A,C为一网络，割集K是一

6、些弧的集合，当移除这些边时从始点s到终点t方向的流就中断；割集中弧的容量之和称为割的容量，记为CK。割集是网络流的一个瓶颈，网络可谢林志——网络最大流问题算法的研究1桂林理工大学理学院信息与计算科学专业2014级学年论文行流量的大小不会超过最小的割集容量。2.1.4增广链定义4在容量网络GV,E,C中,设ffij是一可行流，u是从vs到vt的一条链，若链u上各弧流量满足以下模型条件：fc,(v,v)uijijijfij0,(vi,vj)u那么u就是G中关于可行流f的一条增广链，或者称为增广路。2.2基本定理定理1设v1,v2是网络D的任一个割，

7、则有fstcv1,v2。定理2一个可行流是最大流当且仅当不存在关于它的从vs到vt的增广链。定理3在任何网络中，最大流的值等于最小割的容量,即fmincmax(k)。3、算法思想[3]求网络最大流的标号法一般包括两个步骤：标号过程和调整过程。第一步：从任一可行流f开始，首先给始点s标号为0，，括弧内的第一个数字表示这个ij结点得到标号的前一个结点的代号，第二个数字表示从上一个标号结点到这个标号结点允许的最大调整量，s点假定调整