基于标号法求解网络最大流算法的研究
第23卷第4期2009年7月甘肃联合大学学报(自然科学版)
Jour nal of Gansu Lianhe Univer sity (Natural Sciences) Vol. 23No. 4
Jul. 2009
文章编号:16722691X(2009) 0420064203
基于标号法求解网络最大流算法的研究
孙泽宇
(洛阳理工学院计算机与信息工程系, 河南洛阳471023)
摘 要:近年来, 随着各种网络的飞速发展, 对最大流问题的研究也取得了很大的进展. 本文简述了网络最大流问题的现状, 提出了一种求解网络最大流与最小截问题的算法. 此算法使得计算网络最大流变得简便, 且具有很强的实用性.
关键词:网络最大流; 算法; 最大流问题; 最小截中图分类号:TP393. 3 文献标识码:A
0 引言
研究网络能够通过的流量是图论经常遇到的实际问题. 例如, 交通网络中要对车辆的最大通过能力进行研究; 供水网络中要对水流量进行研究; 信息网络中要对信息传输能力进行研究等等[1]. 显然, 这些网络都具有起点(发点) 和终点(收点) 、且每一弧都有明确的最大通过能力(容量) . 但是因网络配置的原因, 各弧的实际能力往往达不到各弧的最大通过能力. 利用结点法求解网络最大流是目前最优秀的算法之一. 通过该算法能够计算出实际通过最大能力即网络的最大流量问题, 可以充分发挥网络的设备能力, 且能够明确得知如何改造网络可以使得最大流量增大.
[2]
对于发点v s 来说, 记6f s j -于v t 来说6f tj -
6
f js =v(f ). 于是对
6f
jt
=-v(f ) . 最大流问题就是
求流一个{fij }使得其流量v(f ) 达到最大, 并且满足:¹0[f ij [c ij , (v i , v j ) I A; ºv(f ) (i =¼6f sj -s) ; »6f s j -
6
[4]
F ij -
6
f ji =
6f
js
=.
0(i X s, t) ;
6f
js
=-v(f ) (i =t)
定义3 增广链与割集:若给一个可行流f ={fij },我们把网络中使f ij =c ij 的孤称为饱和孤, 使f ij 0的孤, 称为非零流孤. 孤的方向与链的方向一致时, 叫作前向孤, 用u 表示. 孤的方向与链的方向相反时, 称为后向孤, 用u 表示. 设f 是一个可行流, u 是从v s 到v t 的一条链, 若u 满足下面条件, 称之为关于可行流f 的一条增广链. ¹在孤(v i , v j ) I u +上, 0[f ij
定义4 给网络D =(V, A, G) , 若点集V 被剖分为两个非空集合V 1和 V 1, 使v s I V 1, v t I
1) 称为是截集. 记作K. 显然, 若V 1, 把孤集(V 1, V
--+
1 基本概念与定理
定义1 网络与流:给定一个有向图D =(V, A) , 在V 中指定了一点, 称为发点(记为v s ) , 和另
一点, 称为收点(记为v t ) , 其余的点叫中间点. 对于每一个孤(v i , v j ) I A, 对应有一个C(v i , v j ) \0(或简写为c ij ) , 称为弧的容量. 通常我们就把这样的D 叫作一个网络. 记作D =(V, A, C). 孤集合A 上的一个函数f ={f(v i , v j ) },并称为f (v i , v j ) 为孤(v i , v j ) 上的流量. 简记为f ij
[3]
把某一截集的孤从网络中删去, 则从v s 到v t 便不存在路径. 所以, 直观上说, 截集是从v s 到v t 的必经之道. 若对一个可行流f , 网络中有一个截集(V 1 V 1) 使得等式v(f
*
*
*
*
.
定义2 可行流:必须满足下面条件的流f 为
可行流; (1) 容量限制条件:对于每一孤(v i , v j ) I A, 0[f ij [c ij . (2) 平衡条件:对于中间点流出量等于流入量, 即对每个i(i X s, t) 有
收稿日期:2009202228.
基金项目:洛阳理工学院基金项目.
) =c(V 1, V 1) 成立, 则
*
f *必是最大流, 而(V *1V 1) 必定是D 的所有截集
6
f ij -
6
f ji =0.
中, 容量最小的一个, 即最小截集[3].
作者简介:孙泽宇(19772) , 男, 吉林长春人, 洛阳理工学院讲师, 主要从事操作系统分布式计算与算法研究.
定理1 设(V 1, V 1) 是网络D 的任一个割, 则有f st [c(V 1, V 1) [3].
定理2 一个可行流是最大流当且仅当不存在关于它的从v s 到v t 的增广链[3].
定理3 在任何网络中, 最大流的值等于最小割的容量, 即f
max
3 应用举例
求解图1的网络最大流与最小截集
[3]
.
=c min (k)
[3]
.
2 最大流的算法
寻求网络最大流的标号法一般包括两个步骤[5]
:标号过程和调整过程. (1) 在标号过程中, 网络图中的点分为两部分, 即标号的点和未标号的点, 标号的点又分为已检查点和未检查点. 每个标点v j 的标号包括两部分, 即(? v i , l(v j ) ) , 第一个标号表明v j 的标号是从哪一点得到的, 其中/+0是表示v j 的标号是通过前向孤(v i , v j ) 所得, /-0表示v j 的标号通过后向孤(v i , v j ) 所得, 以便于找出增广链; 第二个标号是为确定增广链的调整量H 用的. 具体标号过程如下:第一步:给发点v s 标上(0, +]) , 这时v s 是标号而未检查的点, 其余的点都是未标号点. 第二步:取一个标号而未检查的点v i , 对一切未标号的点v j , 按以下规则处理. ¹若孤(v i , v j ) I A, v j 未标号, 且f ij [c ij , 则给v j 标号(+v i , l(v j ) ) , 其中l(v j ) =Min (l(v i ) , (c ij -f ij ) ). º若孤(v j , v i ) I A, v j 未标号, 且f ji >0, 则给v j 标号(-v i , l(v j ) ) , 其中l(v j ) =Min (l(v i ) , f ij ) . 这时v j 成为标号而未检查的点, 而v i 成为标号并已检查的点. 第三步:重复第二步. 一旦v t 被标上号, 即表示得到了一条从v s 到v t 的增广链u, 转入调整过程; 若所有标号都已检查过了, v t 不能得到标号, 而且不存在其他可标号的顶点时, 算法终止, 这时的可行流就是最大流. 与此同时也得到一个最小截集(V *
*
*
1, V 1). 其中V 1为标号点的集合, V *
[6]
1为未标号点的集合. (2) 调整过程. 第一步:按v t 及其他点的第一个标号, 利用/反向追踪0的办法, 找到增广链u. 如设v t 的第一个标号为v k , 则孤(v k , v t ) 是u 上的孤, 接下来检查v k 的第一个标号, 若为v i , 则找出(v i , v k ) , 再检查v i 的第一个标号, 依次类推, 直到v s 为止. 这时被找出的链即为增广链. 第二步:调整增广链u 上的流量. 令调整量H =l(v t ) , 即v t 的第二个标号. ¹当(v i , v j ) I u +时f *ij =f ij +H ; º当(v i , v j ) I u -时, f *ij =f ij -H ; »当(v i , v j ) |u 时, f *ij =f ij . 这样就得一个新的流f *ij . 第三步:去掉所有标号, 对新的可行流重新进行标号过程.
图1 举例示意图
3. 1 标号过程
开始先给v s 标上(0, +]). 这时, v s 是标号而未检查的点[6]. 第一步:孤(v 1, v 4) , 因f s 1=3, c s 1=4. 则f s 1
由点的第一个标号找到一条增广链[7]
. 按H =1进行调整f s 1+1=4, f 15+1=2+1=3, f 54+1=4, f 4t +1=7, 其余f ij 不变, 调整后如图2所示. 再对这个可行流进行标号过程, 寻找增广链
.
图2 调整后示意图
3. 3 标号过程
开始先给v s 标上(0, +]). 第一步:对于(v s , v 2) , f s 2=2, c s 2=10, f s 2
(+], 10-4) =6. 第二步:对于孤(v 2, v 3) , f 23=4, c 23=4, 则f 23
23
) =Min (6, 4-2) =2. 第三
步:对于孤(v 3, v t ) , f 3t =3, c 3t =8, 则f 3t
由点的第一个标号找到一条增广链. 根据H =2, 进行调整f s 2+2=8, f 23+2=4, f 3t +2=5, 其他f ij 不变, 调整后得到如图3所示的可行流. 对这个可行流再次进入标号过程, 寻找增广链
.
研究工作[11]. 对于实际问题中寻求网络最大流解法, 可以帮助我们很快地解决问题. 本文采用标号算法完成了网络最大流算法的过程、通过最大流的值等于最小割的容量寻找到增广链并对增广链上各边进行调整, 并给出了算法调整过程, 进而使算法的功能得以实现, 这将是网络最大流问题组合算法研究的重要趋势[6]. 参考文献:
[1]凌永发, 徐宗本. 一种求解网络最大流问题的算法
[J]. 计算机科学, 2006, 33(6) :39241.
[2]丁芳, 秦寒冰. 基于网络最大流的交通控制时间研究
[J]. 微计算机信息, 2007, 23(9) 1412143.
[3]钱颂迪. 运筹学[M]. 北京:清华大学出版社, 2003. [4]卢向南. 应用运筹学[M ].浙江:浙江大学出版社,
2005.
[5]王晓东. 计算机算法设计与分析[M].北京:电子工业
出版社, 2005.
[6]谢凡荣. 求解网络最大流问题的一个算法[J]. 运筹与
管理, 2004, 13(4) :37240.
[7]党耀国, 刘思峰, 方志耕. 网络最大流的割集矩阵算法
[J]. 系统工程理论与实践, 2003, 9(9) :1252128. [8]仉志余. 运筹学基础[M ].北京:中国科学技术出版
社, 2006.
[9]钟守南. 运筹学理论基础[M]. 武汉:武汉大学出版
社, 2005.
[10]傅家良. 运筹学方法与模型[M]. 上海:复旦大学出
版社, 2005.
[11]邹豪思, 王志远. 网络最大流的矩阵算法[J]. 内蒙古
大学学报, 2001, 32(4) :4662469.
图3 再调整后示意图
3. 5 标号过程
首先给v s 标号(0, +]). 第一步:对于孤(v s , v 5) , f s 5=2, c s 5=3, 则f
s 5
(v s , L(v 5) ) . 这里L(v 5) =Min (L(v s ) , L s 5-f s 5) =Min (+], 3-2) =1. 第二步:对于孤(v 5, v 4) ,
f 54=4, c 54=4. 则v 4不能标号. 第三步:对于孤(v s , v 2) , f s 2=8, c s 2=10, 则f s 2
*1
*
) =f s 1+f
*1
54*1
+f
23
=4+4+4=12, 对
*1
应的最小截集为(v , v ) , 其中v ={vs , v 2, v 5},v ={v1, v 3, v 4, v t }.
4 结束语
网络最大流问题的应用是一项十分有意义的
Research in the Algorithm on the Solution to the Maximum
Network Flow Problem Base on Mark
SUN Ze 2yu
(Computer and Informat ion Engineering Depar tment Luoyang Institute of Science and T echnology, Luoyang 471023, China)
Abstr act:Various networks has got rapid development recently, the research on the maximum flow problem has made remarkable achievements. In this article, the condition of the maximum flow prob 2lem is proposed and presents a algorithm for the solution to the maximum flow problem and minimum cut. The way of the algorithm in the paper is not only simpler but is also more pr acticality than the other algorithm . s.
Key words:The maximum flows; A lgorithm; Maximum flow problem; T he minimum cut