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