矿井通风网络压能图绘制算法研究

发布时间：2020-05-25 06:15

【摘要】：矿井通风网络图是井下通风系统的抽象表示,是矿井通风管理的重要图件之一;压能图能反映各井巷的阻力分布,对均压防灭火、衡量通风设计水平等问题具有参考价值。将二者结合,利用计算机自动绘制通风网络压能图,对于通风管理将具有重要的现实意义。传统的矿井通风网络图或压能图是依靠人工根据巷道拓扑关系及相关数据进行绘制的,然后形成对应的数据文件,整个过程繁琐且容易出错。在前人研究成果的基础上,主要分析了当前计算机自动绘制通风网络图的原理、算法和数据结构,根据通风压能图的特点,以分层法为主框架,用节点最长路径及压能值分层,对分层图构建树形结构减少分支间交叉;研究了以不同形状绘制通风网络压能图的算法及优缺点。使用C++语言在Visual Studio平台下编程封装成绘制模块,嵌入矿井通风管理信息系统(MVIS)中,利用MVIS生成的巷道拓扑数据,使通风网络压能图绘制实现初步的自动化,并以唐安矿为例,对绘制算法进行应用。
【图文】：

步骤,算法,移除

示v的出度和入度。该算法以空集合aE 开始，并以任意顺序逐个扫描 G 的所有节点。对于每个节点 v∈ V，如果 d( v)d(v)+-≥ ，则 EE∪δ (v)aa+← 。否则， EE∪δ (v)-aa← 。在处理节点v之后，将它从G 中删除，同时删除其所有相邻的边。该算法的时间复杂度为 O(| V|+ |E|)。 Berger 和 Shor 已经证明 ()aG' = V,E是一个DAG，因此 F = E\Ea是一个 FAS，在最坏的情况下， F 将包含一半的分支，这并不符合我们的预期。对于一个图来说，可以很容易观察到，源点和汇点不可能存在于环中，，基于此，Eades等人提出了 Greedy Cycle Removal 算法[25]，主要步骤如下：1）移除图 G 中所有-d 为 0 的点，将该点的-δ 存入aE ；2）移除图 G 中所有+d 为 0 的点，将该点的+δ 存入aE ；3）如果图 G 不为空，移除 d(v)-d(v)+-的值最大的节点，从图G 中移除该点的+δ ，反向该点的-δ 。重复执行上面三个步骤直到图G 为空。以图 2.2（a）为例：

流程图,流程

最长路径法流程
【学位授予单位】：辽宁工程技术大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TD724

【参考文献】