基于通路法的通风网络最大流求解方法

Max-flow Solution in Ventilation Network Based on Path

最大流问题属于网络优化的范畴 ,在通风系统改造等方面具有重要作用 ,为此 ,笔者对网络最大流的算法进行了研究和探讨。利用图论和集合论的知识 ,结合通风网络特点 ,对通风网络最大流问题进行了深入研究 ,提出适合求解通风网络最大流问题的通路法。用通路法求解通风网络最大流时 ,用节点邻接矩阵 ,通过矩阵运算确定通路 ;通过对最小可增广通路 ,依次进行增广求得最大流 ,该方法简便快捷 ,易于程序实现。与Edmonds Karp修正算法相比 ,通路法具有运算量小的优点 ;与Dinic算法相比 ,通路法具有无需分层和无需确定向前边、后退边的优点。

Max flow is one of the research domains in optimization of the network, which is of great importance in reform of the ventilation system. For this purpose, the algorithm of network max flow is studied. By the method of graph and set theory, combined with characteristics of the ventilation network, the max flow in ventilation network is studied in depth. The path method, which is feasible in solving the max flow in ventilation network, is suggested. When using this method, by using node adjacent matrix to determine the path, max flow could be attained by augments to every minimum augment path. The method is convenient and easy to operate in program design. Compared with Edmonds Karp modified algorithm, path method could reduce operational quantity. Compared with Dinic algorithm, path method dispenses with the need for delamination and for determination of forward and retreated branches. The path method is meaningful in teaching and scientific research.