图论在农村自来水管网设计中的应用

《图论在农村自来水管网设计中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、山西水利詈鲁技术与应用·2010年第5期图论在农村自来水管网设计中的应用岳延兵，范敏(山西水利职业技术学院，山西运城O44O04)[摘要]图论具有设计巧妙、灵活多样、应用广泛的特点。结合农村自来水管网优化设计指标，应用图论优化自来水管网布置，并以运城市万荣农村自来水管网建设为例，应用图论的最短路径等方法分析了农村自来水管网优化设计方法，结果显示图论方法在农村自来水管网设计中具有很好的应用优势。[关键词]管网建设；最短路径；最小生成树；优化设计；图论[中图分类号]TV991．33[文献标识码]B[文章编号]1004—7042(2010)05—0039—

2、02图论是组合数学的～一个分支，也是近几十年来最化设计时所要考虑的一个重要指标。管线的费用主要活跃的数学分支之一，具有以下特点：蕴含了丰富的与水管材料、长度和直径等有关，因此，在管网设计时思想、漂亮的图形和巧妙的证明；涉及的问题多且广应根据给水栓的布置确定最优的管网布置方案，减小泛，问题外表简单朴素，本质上却十分复杂深刻；解决管网的长度：在此基础上，确定管网的最优管径组合，问题的方法于变万化，非常灵活，常常是一种问题一以：朗达到整个管网的经济性。种解法。图论研究的内容非常广泛，如图的连通性、遍以上设计目标除了经济性外，其他方面都不易进历性、图的计数、

3、图的着色、图的极值问题、图的可平行定量评价。如用水量变化和管道损坏等原因使计算面性等。下面具体研究图论在农村自来水管网设计方流量不同于实际流量，泵站的运行方式、管理水平等面的应用。也会影响管网设计目标的实现。因此在管网设计中，1农村自来水管网优化设计指标主要是对管网的布置和管径的选择进行优化，选出最农村自来水管网优化设计的指标主要有可靠性、佳方案，尽量达到设计目标。水压水量的保证性和经济性。2应用图论优化自来水管网布置1．1可靠性在图论中，图是顶点与连接这些点的边的集合，可靠性是指在规定的使用状态下、规定的时间内表：示为G=(，E)，其中是顶点的集合

4、，表示边的完成预定功能的性能。对农村饮水工程供水管网而集合。在管网的优化布置中，将每个给水栓或配水水言，预定功能是指在正常工作条件下，保证给水栓所源：看成是图上的一个顶点，给水栓之间的连接管看作需的水量和水压。在工程设计中考虑到可靠性，就有是：边，从而形成图。通常以边的长度或造价为边的权可能减少因故障引起的损失和维修费用。在管网优化重，它与两给水栓之间的连接顺序无关，因此称之为设计时，其可靠性应达到在发生事故的情况下，水量赋权无向图。当图G有凡个顶点时，边的数目为(n一和水压不低于规定的限度，而在时间上不超过允许减1)／2条，称为无向完全图。如果图G

5、中有两个顶点少水量和降低水压的时间。c，和二者之间存在一条道路，则称和是连通1．2水压水量的保证性的，若图G中任意两顶点连通，则称图是连通的，否则在正常r=l作时，各个给水栓的水压、水量要达到称为非连通的。设计要求，以免水压过高引起水量和能量的浪费，防连通的没有回路的图称为树。它是图的一种特殊止下游因水压降低导致水压和水量的不足。形式，其数据元素(即给水栓的序号)有层次关系，某1．3经济性一层上的元素与上一层的一个元素联结，与下一层的在农村饮水供水工程中，经济性是在进行管网优多个元素联结。几个顶点时，只有凡一l条边，如多加一条：边即形成回路，成为环状

6、网，所以树是无向图中的注：本文系山西省高等职业教育教学研究与实践项目(晋：gc．~[2007]19号基金项目)。非完全图，且是极小连通子图。若图G的树包含图型!苎!里圃SHANXIWATERRES0URCESG的所有顶点，则称为图G的一棵生成树或支撑树。从理论上而言，上述方法可对管网进行优化计如果T=(V，E)是G的一个支撑树，则称E中所有边算，但在农村自来水工程管网优化设计中，由于其特的权之和为支撑树的权，记为()，如果支撑树殊性，在应用时必须考虑其各自工程的特殊情况。71的权()是G的所有支撑树的权中最小的，则称3算例及讨论是G的最小生成树。山西

7、省农村饮水任务很重，近几年投入力度不断2．1最小生成树法加大。在这方面也进行了不懈的实践，下面以万荣县图的最小生成树可采用Kruskal法和Prim法确农村自来水管网设计为例进行叙述，简化为示意图1。定。Kruskal法是按权值递增的顺序来构造最小生成树，又称避圈法。先将水源至各给水栓及各给水栓之间按递增顺序排列，再选最短两条线段连接起来，然后由小到大连接各顶点，但不可与已选取的边形成“圈”，如此将所有节点连接起来即可得到最小生成树。Prim法的基本思想是：从某一点开始设为，则作S—。，然后寻找V／S中的点与s中点距离最短者，设为(，)，其中V∈S，

8、V∈V／S，则将(，)边收入E到树中来，且l，进入S。依次反复进行，直到n个顶图1万荣县农村管网赋权示意图点