龙源期刊?/p>
http://www.qikan.com.cn
最大流问题的算?/p>
作者:李娜
来源:《学校教育研究?/p>
2016
年第
11
?/p>
一、引言
最大流问题是指在满足容量限制条件和中间点平衡条件的要求下求取流量值达到最大的?/p>
行流的一类优化问?/p>
.
网络最大流问题的算法是一个传统的研究课题。本文对最大流问题的算
法进行了研究,介绍了最大流问题的两种算法:割集矩阵算法、表格算法?/p>
二、最大流问题简?/p>
给定一个网络图
,设
?/p>
的一个点集,若对?/p>
中的每一个顶?/p>
都是
中弧的发点,?/p>
?/p>
?/p>
发点集;
?/p>
的另一个点集,若对?/p>
中的每一个顶?/p>
都是
中弧的收点,?/p>
?/p>
的收点集?/p>
?/p>
的一个点集,对于
中的任一?/p>
,既?/p>
中一些弧的发点,又是
中一些弧的收点,?/p>
?/p>
中间
点?/p>
中的每一条弧
=
?/p>
?/p>
)都对应一个数
,简记为
,称为弧
的容量。在网络图中,把通过
?/p>
的运量记?/p>
,称为弧
上的流量。显然,
。网络上流量的集?/p>
={ }
称为网络上的流,?/p>
{ }
满足下列条件时:
?/p>
1
?/p>
0
?/p>
?/p>
2
)对于中间点
,有
?/p>
表示?/p>
流出的流量和?/p>
表示流入
的流量和,即流出量等于流?/p>
量;
?/p>
3
)对于发?/p>
,记
,即?/p>
表示
的净发出量;那么,对于收?/p>
,则?/p>
,即
的净收量?/p>
?/p>
的净发量?/p>
则称
为一可行流,此时
称为可行流的流量。任意网络中,可行流总是存在的。网络上最
大流的问题,就是要在给定的网络上,求一个可行流
={ }
,使流量
取得最大值?/p>
三、最大流问题的算?/p>
1.
割集矩阵算法
在一个网络图
中,假设
的总流?/p>
,每条弧
上的流量?/p>
?/p>
用矩阵运算来表示该算法:
矩阵的列数为网络图中边的个数再加
1
(方程组的常数列),矩阵的行数为中间点的个数
?/p>
1
,矩阵的元素为方程中变量(各弧的流量)的系数及方程的常数项,这些数只能是
0
?/p>
1
?