论文部分内容阅读
一、引言
最大流问题是指在满足容量限制条件和中间点平衡条件的要求下求取流量值达到最大的可行流的一类优化问题.网络最大流问题的算法是一个传统的研究课题。本文对最大流问题的算法进行了研究，介绍了最大流问题的两种算法：割集矩阵算法、表格算法。
二、最大流问题简述
给定一个网络图 ，设 为 的一个点集，若对于 中的每一个顶点 都是 中弧的发点，称 为 的发点集； 为 的另一个点集，若对于 中的每一个顶点 都是 中弧的收点，称 为 的收点集； 为 的一个点集，对于 中的任一点 ，既是 中一些弧的发点，又是 中一些弧的收点，称 为 中间点。 中的每一条弧 =（ ， ）都对应一个数 ，简记为 ，称为弧 的容量。在网络图中，把通过弧 的运量记为 ，称为弧 上的流量。显然， 。网络上流量的集合 ={ }称为网络上的流，当{ }满足下列条件时：
（1）0 ；
（2）对于中间点 ，有 ； 表示由 流出的流量和， 表示流入 的流量和，即流出量等于流入量；
（3）对于发点 ，记 ，即用 表示 的净发出量；那么，对于收点 ，则有 ，即 的净收量等于 的净发量。
则称 为一可行流，此时 称为可行流的流量。任意网络中，可行流总是存在的。网络上最大流的问题，就是要在给定的网络上，求一个可行流 ={ }，使流量 取得最大值。
三、最大流问题的算法
1.割集矩阵算法
在一个网络图 中，假设 的总流量 ，每条弧 上的流量为 ，
用矩阵运算来表示该算法：
矩阵的列数为网络图中边的个数再加1（方程组的常数列），矩阵的行数为中间点的个数加1，矩阵的元素为方程中变量（各弧的流量）的系数及方程的常数项，这些数只能是0，1，-1。割集流量关系矩阵中对于变量的系数含义为，若 对应的系数为1，就是对应割集中弧 是从 流向 ，若系数为-1，对应割集中弧 是从 流向 ，若系数是0，则对应割集中弧 是 和 无关联；对于常数项列，数1对应的网络图中的割集，数0对应的不是网络图中的割集。因此，求割集就是对割集流量关系矩阵进行行运算，生成网络割矩阵。由于在矩阵中（常数项列除外）数字1所对应的为割集从 流向 的弧，数字-1所对应的为割集从 流向 的弧，因而割容量就是网络割矩阵中每行数字1所对应的弧的容量之和，然后比较所有割容量的大小，最小的一个即为最小割容量，因而也就是我们所求的网络最大流。
2.表格算法
（1）给网络一任意可行流（一般是零流）。
（2）寻找一条增流链 ，画出表1。
表1中 表示标号的点， 表示未获标号的邻点， 表示流量可增值， 。 为先行顶点 的流量可增值， 为弧 的流量可增值.如果弧 为正向弧，且 ，此时取 ；如果弧 为反向弧，且 ，此时取 ；如果 =0（不管 与 之间是正向弧还是反向弧），这时不给予 标号。
假如不出现 =0的情形，则 中增加一个顶点.继续上述过程，直至 中包含终点，这时就找到了一条由起始点到终点的增流链，然后进入下一个步骤；假如检查 中所有顶点的未标号的相邻顶点后，均不能使 中的任一個顶点获得标号，则不存在流量可增链，此时网络中的可行流就是所求的最大流。
（3）表1 中，从终点反向追踪其先行顶点，再反向追踪下一个先行顶点，直到起始点，就找到了一条增流链 ，终点 给出了增流链 的流量调整值，该链上各个弧调整后的流量为
调整后得到一个新的可行流，再进入步骤（2），直到不存在流量可增链为止.此时，将各条增流链上的流量调整值汇总就获得了最大流。
四、结束语
本文主要讨论了最大流问题两种算法，通过对两种算法的具体应用发现：割集矩阵算法通过求出网络图的割集流量矩阵从而得到网络割矩阵，省去了2F标号法中频繁的画图标号步骤，利用矩阵运算来求得最大流。但由于涉及到矩阵的行、列运算，若网络中节点与弧数目很多的情况下可能会给计算带来困难；利用表格法求解最大流问题可以很快找到主要的增流链，避免了重复计算，既节省计算时间，又不易漏掉增流链，直观性强，计算方便。
最大流问题是指在满足容量限制条件和中间点平衡条件的要求下求取流量值达到最大的可行流的一类优化问题.网络最大流问题的算法是一个传统的研究课题。本文对最大流问题的算法进行了研究，介绍了最大流问题的两种算法：割集矩阵算法、表格算法。
二、最大流问题简述
给定一个网络图 ，设 为 的一个点集，若对于 中的每一个顶点 都是 中弧的发点，称 为 的发点集； 为 的另一个点集，若对于 中的每一个顶点 都是 中弧的收点，称 为 的收点集； 为 的一个点集，对于 中的任一点 ，既是 中一些弧的发点，又是 中一些弧的收点，称 为 中间点。 中的每一条弧 =（ ， ）都对应一个数 ，简记为 ，称为弧 的容量。在网络图中，把通过弧 的运量记为 ，称为弧 上的流量。显然， 。网络上流量的集合 ={ }称为网络上的流，当{ }满足下列条件时：
（1）0 ；
（2）对于中间点 ，有 ； 表示由 流出的流量和， 表示流入 的流量和，即流出量等于流入量；
（3）对于发点 ，记 ，即用 表示 的净发出量；那么，对于收点 ，则有 ，即 的净收量等于 的净发量。
则称 为一可行流，此时 称为可行流的流量。任意网络中，可行流总是存在的。网络上最大流的问题，就是要在给定的网络上，求一个可行流 ={ }，使流量 取得最大值。
三、最大流问题的算法
1.割集矩阵算法
在一个网络图 中，假设 的总流量 ，每条弧 上的流量为 ，
用矩阵运算来表示该算法：
矩阵的列数为网络图中边的个数再加1（方程组的常数列），矩阵的行数为中间点的个数加1，矩阵的元素为方程中变量（各弧的流量）的系数及方程的常数项，这些数只能是0，1，-1。割集流量关系矩阵中对于变量的系数含义为，若 对应的系数为1，就是对应割集中弧 是从 流向 ，若系数为-1，对应割集中弧 是从 流向 ，若系数是0，则对应割集中弧 是 和 无关联；对于常数项列，数1对应的网络图中的割集，数0对应的不是网络图中的割集。因此，求割集就是对割集流量关系矩阵进行行运算，生成网络割矩阵。由于在矩阵中（常数项列除外）数字1所对应的为割集从 流向 的弧，数字-1所对应的为割集从 流向 的弧，因而割容量就是网络割矩阵中每行数字1所对应的弧的容量之和，然后比较所有割容量的大小，最小的一个即为最小割容量，因而也就是我们所求的网络最大流。
2.表格算法
（1）给网络一任意可行流（一般是零流）。
（2）寻找一条增流链 ，画出表1。
表1中 表示标号的点， 表示未获标号的邻点， 表示流量可增值， 。 为先行顶点 的流量可增值， 为弧 的流量可增值.如果弧 为正向弧，且 ，此时取 ；如果弧 为反向弧，且 ，此时取 ；如果 =0（不管 与 之间是正向弧还是反向弧），这时不给予 标号。
假如不出现 =0的情形，则 中增加一个顶点.继续上述过程，直至 中包含终点，这时就找到了一条由起始点到终点的增流链，然后进入下一个步骤；假如检查 中所有顶点的未标号的相邻顶点后，均不能使 中的任一個顶点获得标号，则不存在流量可增链，此时网络中的可行流就是所求的最大流。
（3）表1 中，从终点反向追踪其先行顶点，再反向追踪下一个先行顶点，直到起始点，就找到了一条增流链 ，终点 给出了增流链 的流量调整值，该链上各个弧调整后的流量为
调整后得到一个新的可行流，再进入步骤（2），直到不存在流量可增链为止.此时，将各条增流链上的流量调整值汇总就获得了最大流。
四、结束语
本文主要讨论了最大流问题两种算法，通过对两种算法的具体应用发现：割集矩阵算法通过求出网络图的割集流量矩阵从而得到网络割矩阵，省去了2F标号法中频繁的画图标号步骤，利用矩阵运算来求得最大流。但由于涉及到矩阵的行、列运算，若网络中节点与弧数目很多的情况下可能会给计算带来困难；利用表格法求解最大流问题可以很快找到主要的增流链，避免了重复计算，既节省计算时间，又不易漏掉增流链，直观性强，计算方便。