最大流算法在矿井通风系统中的应用

刘义磊，黄素果

毕节学院资源与安全工程学院，贵州毕节 551700

0 引言

在实际生产、生活过程当中，真实网络的结点和边都是有容量限制的，我们一般需要知道这样一个网络中源和汇这两个指定结点之间传输的最大流量，并找出达到这个最大流量的具体办法，网络最大流问题就是描个问题的数学模型。

矿井通风系统设计所需的一个重要的主要参数就是矿井通风所需最小风量，它也是对各种分风算法进行选择的前提条件。矿井通风系统形成之后，矿井最小总风量就是不受分风算法影响的一个定值。但是由于风速太大时会导致粉尘增多等现象，针对不同的巷道先顶了不同的风速上限，因此对于通风系统来说其最大风量和最小风量都是有限制的，最终都归结到网络的极值流问题，其中重要的也就是最大流问题。

1 最大流算法

最大流问题是网络流理论的核心问题之一，它牵涉到特殊的线性规划，是一个经典的优化组合问题。通俗地讲，最大流问题就是在网络当中以最快捷的办法把特定物质从某处输送至另一处。该问题源于美苏之间的争端，美国想准确获得有关苏联能够最快的获得国际补给的铁路线路，以及如何最大限度地切断其补给线路。最终通过调查计算发现这两个问题相互联系，不可分割对待，并且最大流问题得到合理处理的同时，也解决了最彻底地切断苏联补给的最小割问题。

最大流问题发展到今天，学者们建立了一系列较为完善的理论，也寻找出了许多的算法。如Ford-Fulkson算法、Dinic算法、Gold-berg推进和重标号算法以及Gold-berg和Rao的二分长度阻塞流算法等等，这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用。

1.1 Ford-Fulkson增载轨算法和Dinic阻塞流算法

Ford-Fulkson算法第一次将组合优化的方法应用到最大流问题。初次将剩余网络、增载轨等概念引入，把最大流问题的求解进行归纳总结，成为从一个初值开始不断递增直到求得最优解的迭代过程，打下了用组合方法进行求解的基础。

Ford-Fulkerson Algorithm可以概括为：Residual networks augmenting paths and cuts三大思想，最重要的一点的是利用Residue network的论点求解出maximum flow。

将最大流问题的求解过程当做一个迭代的过程，每次迭代都是为了使网络中的流量增大，那么如果想最大限度地减少计算量，那么只有想法设法将迭代次数减少，并且降低每一步的复杂程度。如果想将迭代次数降低，那么需要每次迭代时都要使网络中的流量递增程度尽可能的增大。比较方便的是找出网络中的一部分作为子图，然后求出该子图中所需的最大流，最终在剩余的网络里重复这一步骤。

Dinic算法首次将距离这一定义延伸到求解过程中来，它在网络中定义出了分层网络，这是一个非常独特的无环网络，分层网络就是仅保留距离相邻的结点之间的边，然后在定义出的分层网络中进一步求阻塞流。

1.2 Push-relabel algorithms算法

Push-relabel algorithms算法的主要思路是在网络中，流出的量可能比流进的量还要多，有流量进来就放其流入，流不出去时再做处理。Push-relabel algorithms算法的流程如下：

1）设定一个函数f(x)，它是一个高度函数，表示的意义是x点的高度，作为一个中间参考坐标，只有比其高的点能往比其低的点流动；

2）程序运行时，设source node的高度是x(node数)，除此之外的点的高度都是0，这样source node就足以流往其它任何一个点；

3）然后让source node往其它所有紧挨的node里都注入特定的流量，然后计算剩余网络的状态；

4）对每一个active node都重复Relabel的动作，如果在其中某个node有流体存在，但是和它所相邻的所有node的f(x)都高于它，这时要为它的f(x)增加一条可以流出去的支路；

5）然后对每一个能够做Push动作的node重复Push；

6）反复执行Relabe和Push的工作，直到无任何active node，最后从source node流出的总的流量就是最大流量。

Push-relabel algorithms提供了最大流的新的思路，并且它的效率也非常的高，复杂度仅仅为O(V2E)，比一般的算法占有一定的优势。

2 求解最大流的通路法在矿井通风系统中的应用

已知某矿井的通风网络结构简图G如图1所示，对其进行加虚分支，形成新的网络结构图G′，如图2所示，在通风网络系统的改造过程中，确定最大流是必不可少的，在此应用通路法来求解该网络的最大流。通路法确定通风网络最大流为以下四个步骤：1）增加虚分支；2）求通路；3）最小可增广通路；4）通路增广

图1中各分支的容量和容许流为 ：e1（12，0），e2（10，0），e3（20，0），e4（9，0），e5（8，0），e6（8，0），e7（7，0），e8（18，0）。

对于图2，a=9，b=10。所加虚分支的容量依次为：

c91=c12=12，c95=c56=12，c4，10=c34=20，c8，10=c78=18。

可确定出图2的通路为：

P1={e9，e1，e2，e3，e11}，P2={e9，e1，e2，e5，e8，e12}，

P3={e10，e6，e4，e2，e3，e11}，P4={e10，e6，e7，e8，e12}，

P5={e10，e6，e4，e2，e5，e8，e12}。

最小可增广通路为P4。

图1 某矿通风网络简图

图2 加虚分支后的通风网络图

对P4中的各分支进行增广，增广后P4中各分支的容量和容许流量分别为 ：e10（8，7），e6（8，7），e7（7，7），e8（18，7），e12（18，7）。然后继续搜索最小可增广通路，并进行通路增广，直到找不到可增广通路为止，随后依次进行增广的通路为P3，P2和P1，通路增广过程完成后，用下式计算最大流，

至于如何使风流按照一定的方式流动，可采用增阻法、降阻法或增能法进行风量调节。

3 结论

1）介绍了最大流问题的研究历史，总结了这段时期内人们建立的最大流问题较为完善的理论和算法，并分析了经典算法及相关技术对网络最大流问题的研究起到的推动作用；2）针对求解最大流在矿井通风系统中的应用实例进行分析，该实例用通路法求解最大流，只需进行4次增广，通过与其他方法的对比可知该方法具有运算量小的优点，能够在复杂的网络问题中极大地减小运算量，从而减小出错概率、减轻工作负担。

[1]张宪超，陈国良.小容量网络上的最大流算法[J].计算机研究与发展，2001(2).

[2]沈金龙，喻锦华.计算机通信网最大流算法的分析和实现[J].南京邮电学院学报，1994(4).

[3]凌永发，王杰，李正明.网络最大流问题典型组合算法研究[J].云南民族大学学报：自然科学版，2006(3).

[4]解季萍，杨超，谢刚.网络最大流问题和典型阻塞流算法研究[J].西南林学院学报，2005(2).