数学与应用数学专业图论在农村自来水管网设计中的应用.docVIP

XX 理 工 学 院 毕业论文任务书 论文题目： 二级学院： 理学院 专业：数学与应用数学： ： ： ： 2011年3月10日 （系）教研室主任 （签名） 理学院院长 （签名） 1毕业论文的主要内容及基本要求 ⑴查阅相关文献资料，了解课题研究现状； ⑵确定并理清课题写作思路； ⑶寻找图论算法中的分析方法； ⑷解决问题，提出用最短路径解决水管网的安排； ⑸写出思路清晰，逻辑合理的论文。 2指定查阅的主要参考文献及说明 [1]耿素云.离散数学[M].北京:高等教育出版社,2009:273—291. [2]孙惠泉.图论及其应用[M].北京:科学出版社,2004:1—92. [3]岳延兵.图论在农村自来水管网设计中的应用[J],山西水利技术与应用,2010年,第5期. [4]管志忠.图论中最短路问题在MATLAB程序实现[J],安庆师范学院学报（自然科学报）第13卷第1期:2007. 3.进度安排 论文各阶段名称 起 止 日 期 1 2011年2月 28日-2011年3月 10日 2 查阅文献资料，完成文献综述和开题报告 2011年3月11日-2011年3月31日 3 完成论文初稿（手写稿） 2011年4月1日-2011年4月30日 4 完成论文修改稿 2011年5月 1 日-2011年5月25日 5 完成论文定稿 2011年5月26日-2011年6月15日 6 论文答辩 2011年6月16日-2011年6月24日 摘 要 图论具有设计巧妙，灵活多样，应用广泛的特点，结合农村自来水管网优化设计指标，应用图论的最优树生成法等分析自来水管网优化设计方案，应用图论的最短路径等方法分析水源的建设地理位置，结果显示图论方法在农村自来水管网设计中具有很好的应用优势。 关键词：图论，水管网，最短路径 ABSTRACT Graph theory has many distinguishing features, such as clever design, diversity and widespread application. Combining optimization design indexes of rural water pipe network, we analyse optimization design scheme of water pipe network in term of most superior spanning tree on graph. Furthermore, we discuss the construction position of water source by the shortest path method of graph. The results show that graph theory method has very good advantages in rural water pipe design. Keywords：Graph ，ater pipe network ，hortest path. 目 录 前 言 1 第一章 农村自来水管网优化设计指标 3 1.1 可靠性 3 1.2 水压水量的保证性 3 1.3 经济性 3 第二章 图论的应用以及算法在MATLAB中的实现 4 2.1 图的一些基本概念 4 2.2 图论中的树 6 2.2.1 图论中生成最小树的Kruskal算法 7 2.2.2 图论中生成最小树的Prim算法 8 2.3 图论中的最短路问题 8 2.4 算法在MATLAB中的实现 10 2.4.1 图论与矩阵的的定义 10 2.4.2 最短路Floyd算法在MATLAB中的实现 11 2.4.3 最短路Dijkstra算法在Matlab中的实现 12 2.4.4 Kruskal算法在MATLAB中的实现 12 第三章 图论在水管网中的算例 13 3.1 把实际问题转化成图论问题 13 3.2 运用Kruskal算法生成最小树 13 3.3 用最短路径法找水源建设地 15 3.4 问题解决的最后结果 16 结束语 17 参考文献 18 致 谢 19 附 录 20 文献综述 26 前 言 图论起源于的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸起来问题是要从这四块陆地中任何一块开始，通过每一座桥正好一次，再回到起点。然而无数次的尝试都没有成功。在1736年欧拉解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：