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

《数学与应用数学专业毕业论文图论在农村自来水管网设计中的应用.doc》由会员分享，可在线阅读，更多相关《数学与应用数学专业毕业论文图论在农村自来水管网设计中的应用.doc（31页珍藏版）》请在三一办公上搜索。

1、XX 理 工 学 院毕业论文任务书论文题目： 图论在农村自来水管网设计中的应用 二级学院： 理学院 专业：数学与应用数学 班级： 2007级1班 学号： 学生： 指导教师： 接受任务时间： 2011年3月10日 （系）教研室主任 （签名） 理学院院长 （签名）1毕业论文的主要内容及基本要求查阅相关文献资料，了解课题研究现状；确定并理清课题写作思路；寻找图论算法中的分析方法；解决问题，提出用最短路径解决水管网的安排；写出思路清晰，逻辑合理的论文。2指定查阅的主要参考文献及说明1耿素云.离散数学M.北京:高等教育出版社,2009:273291.2孙惠泉.图论及其应用M.北京:科学出版社,2004:

2、192.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

3、日-2011年6月24日摘 要图论具有设计巧妙，灵活多样，应用广泛的特点，结合农村自来水管网优化设计指标，应用图论的最优树生成法等分析自来水管网优化设计方案，应用图论的最短路径等方法分析水源的建设地理位置，结果显示图论方法在农村自来水管网设计中具有很好的应用优势。关键词：图论，水管网，最短路径ABSTRACT Graph theory has many distinguishing features, such as clever design, diversity and widespread application. Combining optimization design indexe

4、s 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

5、advantages in rural water pipe design.Keywords：Graph ，Water pipe network ，Shortest path.目 录前 言1第一章 农村自来水管网优化设计指标31.1 可靠性31.2 水压水量的保证性31.3 经济性3第二章 图论的应用以及算法在MATLAB中的实现42.1 图的一些基本概念42.2 图论中的树62.2.1 图论中生成最小树的Kruskal算法72.2.2 图论中生成最小树的Prim算法82.3 图论中的最短路问题82.4 算法在MATLAB中的实现102.4.1 图论与矩阵的的定义102.4.2 最短路Floy

6、d算法在MATLAB中的实现112.4.3 最短路Dijkstra算法在Matlab中的实现122.4.4 Kruskal算法在MATLAB中的实现12第三章 图论在水管网中的算例133.1 把实际问题转化成图论问题133.2 运用Kruskal算法生成最小树133.3 用最短路径法找水源建设地153.4 问题解决的最后结果16结束语17参考文献18致 谢19附 录20文献综述26前 言图论起源于举世闻名的柯尼斯堡七桥问题。在柯尼斯堡的普莱格尔河上面有七座桥将河中的岛及岛与河岸是连接起来的,有一个问题是要从这四块陆地中任何一块开始，通过每一座桥而且正好只能一次，再回到起点。然而许多人经过无数次

7、的尝试都没有成功。在1736年欧拉神奇般的解决了这个问题，他用抽像分析法将这个问题化为第一个图论问题：即用点来代替每一块陆地，将每一座桥用联接相应的两个点的一条线来代替，所以相当于得到一个“图”（如下图）。CABD(b) 柯尼斯堡七桥图 桥转换成图欧拉证明了这个问题是没有解的，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则。这项工作使得欧拉成为图论及拓扑学的创始人。 图论其实也是一门应用数学，它的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题。它具有以下特点：蕴含了丰富的思想、漂亮的图形以及巧妙的证明；涉及的问题很多而且广泛，问题外表简单朴素，本质

8、上却十分复杂深刻；解决问题的方法是千变万化，非常灵活，常常是一种问题就有一种解法。图论研究的内容非常广泛，如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等。历史上参与研究图论问题的人既有许多天才的数学家，也有不少的业余爱好者。 那么什么是图论中的图呢？在日常生活、生产活动以及科学研究中，人们常用点表示事物，用点与点之间是否有连线表示事物之间是否是有某种关系，这样构成的图形就是图论中的图。其实，集合论中的二元关系的关系图都是图论中的图，在这些图中，人们只关心点与点之间是否有连线，而不关心点的位置，以及连线的曲直。这就是图论中的图与几何中的图形的本质区别。 因此在现实世界中，

9、事物的许多状态可以由图形来描述，使其简单直观，便于理解，帮助思维，易于记忆，同时还可以根据图的特点，从不同角度来扩展讨论范围。构成图论中的图有三个要素1： 点抽象表示具体事物，既没有大小，又没有位置区别 边反映事物之间有联系，不考虑长度和形状 方向指明起点及终点，表示事物间的关系特征图论的定义1 设是有序二元组，如果满足以下条件： （1）是非空有限集； （2）是中不同元素的非有序对偶组成的集合；则称G为一个简单的无向图。因此本文打算结合农村自来水管网优化设计指标把农村供水处看着点，把水管看着线，把所有的点连接成一个n阶无向完全图，再根据实际情况给每条无向边附以权重，再根据图论的性质和MATLA

10、B软件找到水塔在农村何处建立，从而达到农村自来水管网最优化达到可靠性，水压水量保证性以及经济性的效果，为新农村的建设节约资金和环境的美化。第一章 农村自来水管网优化设计指标农村自来水管网优化设计的指标主要有可靠性、水压水量的保证性和经济性。1.1 可靠性计流量和布置在给水系统工程中，输水管分原水输水管和净水输水管，前者是指从水源地到水厂的输水管线。后者是指当水厂距供水区域较远时，从水厂到区域配水管网的输水管线。当无有利地形可供利用，无条件采用重力输水时，一般均采用密闭管道进行压力输水。输水管通常沿线无流量变化，其独立管段内的流量是沿程不变的。原水输水管的设计流量，应按照对水厂最高日平可靠性是指

11、在规定的使用状态下、规定的时间内完成预定功能的性能。输水管的设均需水量计算确定，一般包括综合生活用水量(包括居民生活用水和公共建筑用水)，对农村饮水工程供水管网而言，预定功能是指在正常工作条件下，保证给水栓所需要的水量以及水压。在工程设计中我们必须考虑到可靠性，有可能减少因为故障引起的损失和维修资金。管网优化设计时候，其可靠性就应该达到在发生事故的可能下，水量和水压不能低于规定的限度，在时间上也不超过允许减少水量和降低水压的时间。1.2 水压水量的保证性在输水正常工作时，根据人们平时生活用水量，即生产用水量和消防用水量，各个给水栓的水压、水量必须要达到设计要求，以免水压过的高引起水量以及能量的

12、浪费，防止下游因水压降低导致水压和水量的不足。1.3 经济性在农村饮水供水工程中，经济性是在进行管网优化设计时所要考虑的一个重要指标。管线的费用主要是与水管的材料和长度及其直径等有关，在管网设计时应由给水栓的布置确定最优化的管网布置方案，减小管网的长度；从而减少资金的浪费，因此，确定管网的最优管径组合是以期达到整个管网的经济性。另外除了经济性外，其他方面都有有一定难度进行定量评价。如用水量变化以及管道的损坏原因使计算流量很难等同于实际流量，泵站的运行方式和管理水平也会影响到管网设计目标的实现。因此在管网设计中，主要是对管网的布置和管径的选择进行优化（本文注重的是布置方面），选出最佳方案，尽量达

13、到设计目标。第二章 图论的应用以及算法在MATLAB中的实现本章首先介绍了图论中图的一些基本概念，然后在此基础上给出了图论中的树的定义与最短路径的算法以及算法在MATLAB中的实现。2.1 图的一些基本概念 我们从这些形形色色的具体的图中, 取出它们共同性的东西, 抽象出一般的图的概念。图的最基本要素是点, 以及点与点之间的连线! 通常用点表示我们所要研究的对象(如城市、运动队、状态等)用连线表示对象之间的某种特定的关系(如两城市之间有铁路线、两个运动队之间比赛过等)。因此, 可以说图是反映对象之间关系的一种工具! 如果两个对象之间有这种关系, 那么就用一条线连接这两个点, 由此可见, 对我们

14、来说, 重要的是哪些点之间有线相连, 而点的相对位置、线的长短曲直, 则往往不是重要的。 如果给了一些点, 并己知点与点之间的连接情况, 也就给出了一个图。我们把给定的点的全体称为点集合, 用表示, 把给定的连线的全体称为线集合, 用E表示! 如果图用G表示, 我们可以把图记成，我们记，总用,分别表示图的点数和线数! 如果线是连接点和的, 可以把记为（也可以记为）。给出图形（如下图2-1-1）图 2-1-1 图论中的图这个图中， ； ； ； ;按照以上所说的线的记法，也可以记为： 根据对图论中的图的定义,除了给出上面一个具体的例子外，与它有关的还有下面的一些概念和规定1。(1） 设为无向图，称

15、为的端点，与关联，若，则称与的关联次数为1；若，则称与的关联次数为2，并称为环。(2） 在无向图中，如果关联一对顶点的无向边多于1条，则称这些边为平行边，平行边的条数称为重数。如果关联一对顶点的有向边多于1条，并且这些边的始点和终点相同（也就是它们的方向相同），则称这些边为平行边。含平行边的图形为多重图，既不含平行边也不含环的图称为简单图。(3） 设为无向图，,称作为边的端点的次数为的度数，简称度。(4） 在任何无向图中，所有的顶点的度数之和等于边数的2倍。(5） 在任何有向图中，所有的顶点的度数之和等于边数的2倍；所有的顶点的入度之和等于所有顶点的出度之和等于边数。(6） 任何图无论是有向图

16、还是无向图中，奇度顶点的个数是偶数。(7） 非负整数列是可图化的当且仅当为偶数。(8） 设为两个无向图（两个有向图），若存在双射函数使得，当且仅当 (当且仅当），并且与 （与）的重数相同，则称与同构。图论的定理证明难度高低不等，有的简单易懂，有的难于理解，但其每一步证明都需要技巧，每一个定理都像艺术平一样值得品味与推敲。因此，尽管本文介绍的是较为基础的图论内容，但阅读理解与完成习题是学习图论必不可少的步骤。2.2 图论中的树在各种各样的图中, 有一类简单而重要的图, 即所谓“ 树” 。树之所以重要, 不仅在于它在许多不同领域中应用, 而且也在于图论本身。在图论中, 解决许多悬而未决的问题往往是

17、从树这一类图着手。很多问题对一般图未能解决或者没有简便的方法, 而对树则完满解决, 方法极其简单。树的定义2 给定无向图,如果图是连通，并且不含圈，则称为树。通常用来表示。本文要用到生成最小树的知识，所以提起树，还得着重介绍下图的树：设给定图,图，是它的一个部分图，如果是树，则称是的一个部分树。如下图2-2-1，图中由粗线所示的图是它的一个部分树。图2-2-1 图论中的树值得说的是，每一个完全无向图图中都有一部分树。下面再给出一些关于图论中的树的推论2：（1） 设是一棵树，则树中的线条总数=树中的点的总数-1，即有（2） 下述论断是等价的图是连通的无圈图；图中无圈，并且；图是连通的，并且。（3

18、） 若是树，则连通，但丢去任何一条线, 图便断成两个且仅仅两个连通片；无圈, 但添加任何一条线, 图便含有一个且仅仅一个圈。（4） 每棵非平凡树至少有两个度为为1的顶点了解这些定理对于下第三章提到到生成最小树的Kruskal算法和Prim算法有着很大的帮助。2.2.1 图论中生成最小树的Kruskal算法 如果在图的每条边上，都赋予一个非实数，则称为一赋权图（weitghed graph);称为边的权（weighted）。因此，是定义在上的一个非负实数。对于一个赋权图中必然包含了一个赋权的树，称中所有边的权的和,而利用Kruskal算法可以找到图中包含的树中最小值，即使最小树即，Kruskal

19、算法2如下；（1）选棱（link），使最小。（2）若已选定，则从中选取棱使 （a）无圈（b）是满足（a）之最小者（3）若（2）不能再进行下去时，停止。否则回到（2）。下面简单证明下用此算法求出来的的生成树是最优树。 反正法，假设不是的最优树。取的一最优树。令为中（按其顺序）第一个不属于的边，且令为最优树中使为最大者。 由于无圈，中唯一的圈中一定包含。又由于树不包含圈，中必含一条边不属于，所以可知的圈中的边不是的割边，因此乃连通，且边数等于，从而也是的生成树。 又由算法知，是使为无圈的边中权最小的，而的子图也不含圈，因此，从而即也是的最优树，且中第一个不属于的边的下标大于k，这就与的取法相矛盾。

20、2.2.2 图论中生成最小树的Prim算法（1）作为开始 令，并对每个令标号（2）如果停止；否则求一顶点使并记达到上述最小值的到的伴随边为。（3）令 通过新顶点更新。 （4）转到（2）。2.3 图论中的最短路问题路的定义2 设为无向标定图，中顶点与边的交替序列称为到的通路，其中，为的端点，分别称为始点与终点，中的边的条数称为它的长度，若又有，则称为回路。若的所有边各异，则称为简单通路。若又有，则称为简单回路，若所有的顶点（除与可能相同外）各异，所有的边也各异，则称为初级通路或路径，若又有，则为初级回路或圈，将长度为奇数的圈成为奇圈，长度为偶数的圈为偶圈。本文要考虑的问题是对任意给定的一个赋权图

21、,及中两个指点的顶点与，求出其最短（-路。易见。只要考虑简单连通图的情形就够了。这里我们假设每边的权都是大于0的实数。因为当一条边的权为0时。我们可以把和合并成一个顶点。又，我们约定边当且仅当。下面将要提到的Dijkstra（1959）算法，将求出从一指定顶点到的其余所有顶点的最短路。而不是最短-路。对的顶点真子集,及,将到的距离定义为设顶点使，而为最短-路，则易见：。是一最短-路 算法的原理是逐步求出顶点序列使记为最短-路，（1）求;使得。 （2）若已求得；及最短-路如图2-3-1图2-3-1 最短路示意图求使其中即，首先对中每个，按（*）式求出。使达到最小的就是，且这时有。至此，得；，某，

22、就是当时使（*）式右边达到最小的。当进行下一步时，易见，对每一个，我无需再直接用（*）式，重复通过中的每个去求，只要通过更新（updata）即可 下面的算法只求出从到其他各顶点之间的距离。若想求出从到其他各顶点之间的最短路，只需要按上述作一些改动即可。Dijkstra算法2： （1）作为开始： ； （2）（这时已求出，且对每个，有） ，再计算，设其最小值点为，令 （3)若，停止；不然，令，并回到（2）。2.4 算法在MATLAB中的实现2.4.1 图论与矩阵的的定义 关联矩阵7 设有向图G=(V,E), V=v1,v2, vn,E = e1,e2,em。 构造矩阵B =(bij)nm，称之为G

23、的关联矩阵，其中 关联矩阵的列举权矩阵7 对带权图 G=(V, R)， n=|V|，构造矩阵，其中称为图G的权矩阵。2.4.2 最短路Floyd算法在MATLAB中的实现求n个顶点的连通图G上任意两点间的最短路长的算法(它是下面要讲的Floyd(1962)算法的改进，但它只适用于非负权的最短路问题）。设为顶点到的距离，令图的权矩阵为算法的基本步骤7 （1）输入权矩阵。 （2）计算，其中表示从点到的距离，或者经过某一个中间点到达点的最短路。 （3）若，则就是到的最短路长，不然，取，转（2）。2.4.3 最短路Dijkstra算法在Matlab中的实现 Dijkstra算法的基本思想是：按距离由近

24、及远的顺序，依次求得到的各顶点的最短路和距离，直至（或直至的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。Dijkstra算法步骤7如下（1）令，对于，令，（2）对每个，用代替，当不相邻时，。计算，把达到这个最小值的一个顶点记为，令。（3）若，则停止，若，则用代替，转至（2）。2.4.4 Kruskal算法在MATLAB中的实现Kruskal算法的基本思想是：设无向连通网为G=（V，E），令G的最小生成树为T=（U，TE），其初始状态为U=V，TE=,这样T中各顶点各自构成一个连通分量。然后按照边的权值由小到大的顺序，依次考察边集E中的各条边。若被考察的边的两个顶点属

25、于T的两个不同的连通分量，则将此边加入到TE中去，同时把两个连通分量连接成一个连通分量；若被考察边的两个结点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。Kruskal程序流程图为11：（1） 相关变量初始化工作，将原图的邻接矩阵拷贝到temp矩阵中，避免程序对原矩阵直接进行修改；（2） 找最小生成树（采用while循环，因为循环次数事先并不确定）循环结束条件为找到了顶点数-1条最优边；（3） 求最小生成树的总代价并显示，并显示最小生成树的边，及其权值。第三章 图论在水管网中的算例3.1 把实际问题转化成图论问题我们把一个

26、县的八个村看成是八个点，用线段把每一个点与其相邻的点连接起来，从而形成一个无向图。再根据实际情况：村与村的水管长短问题；防腐程度深浅问题；水管安置工程的难易问题；水管的维修以及管线的费用问题等给相应的边赋上权值，最后得出一个赋权图，如图3-1-1：图3-1-1农村地图转换成图论中的图图中：1代表新万发镇新农村村：2代表林海镇交通村，3代表官屯村，4代表凤凰乡济公村，5代表花石沟村，6代表铜矿村，7代表牡丹阁村，8代表石田村。由此一来，我们就可以运用图论的知识进行科学的解决实际问题从而带来经济效益，减少不必要的支出。3.2 运用Kruskal算法生成最小树值得一提的是，在Kruskal算法中要运

27、用到权矩阵，为了简化在Matlab中简化程序，但此矩阵与上面的权矩阵有所不同，此矩阵一共只有三行，第三行的数是对应的第一与第二行数之间的赋权值，如下经过程序在Matlab中运行后得到了以下结果，（详细程序见附录一）T = 4 5 6 8 7 4 4 2 1 4 6 3 1 3c = 240这就说明以4为起点以2为终点的边保留，以5为起点以1为终点的边保留，以6为起点以4为终点的边保留，以8为起点以6为终点的边保留，以7为起点以3为终点的边保留，以4为起点以1为终点的边保留，以4为起点以3为终点的边保留，其这些边的权值和为240（应为最小值）。详看下图3-2-1图3-2-1 生成最小树后的图3.

28、3 用最短路径法找水源建设地相对于图论，运用前面所介绍的生成最小树的Kruskal法可以找到每个问题的最小解，但对于管网的优化布置，仅仅寻求最小生成树并不能实现投资最少的目标。最小生成树仅是管网投资减少的一个因素，它所寻求的是整个管网的总长度最短，即所有顶点之间的最短连接，而不是一点到其余各点之间的最短连接。在管网布置时，假定各个管段的直径是均一的，但当水源位置不同时，各段管径的大小有较大差异，因而对造价的影响较大。通过缩短流量和直径较大的管段长度，同时增加流量较小的直径较小的管道长度，使管网的总投资进一步降低。这一问题可采用最短路径法得以解决。首先把那生成的最小树飞赋权图的权矩阵写出来，如下

29、现在利用求最短路的dijkstra思想编辑Matlab程序可以求解出一点使得其余七点到达这点的所要经过的边的赋权值之和，在Matlab中运行程序后得到如下结果：。（详细程序见附录二） 0 130 190 90 60 150 260 210 130 0 140 40 190 100 210 160 190 140 0 100 250 160 70 220 90 40 100 0 150 60 170 120 60 190 250 150 0 210 320 270 150 100 160 60 210 0 230 60 260 210 70 170 320 230 0 290 210 160 2

30、20 120 270 60 290 0现在我们可以利用这个矩阵在matlab中编辑一个简单的程序求出这八个点中的一点，使得这点到其余七点的最短路径最短，而这点就是水源建设点，因为水源建设在这里，它提供的水压是最低的，而且在水压方面选择水管材料时，又可以节约一笔资金。下面简单的介绍下这程序的理论：我们已经知道了点ii到点jj之间的最短距离的矩阵D（D矩阵为对称矩阵，详看上图），点ii到点jj之间来回最短距离为D2=D+D=2*D，其中D为D的转置，行向量far=max（D)的第jj个元素表示若水源建设在jj点，最远的点到水源的来回距离，m,ii=min(far)就获得水源应建设在ii点，最远的点

31、到水源的来回距离为m。在Matlab中运行后的结果为（详细程序见附录三）340 4这一结果表明水源应该建设在点4即代表凤凰乡济公村，是最合理的，最优化的最具有经济效益的结果。3.4 问题解决的最后结果 本文的最终目的就是利用图论的知识把农村自来水管网设计达到最有经济效益的结果，经过把实际事物转化为点与线的关系即图论中的图，利用图的一些性质以及Matlab软件的优越性，经过编辑程序求得了最终结果，如图3-4-1图3-4-1最终结果示意图图中粗线表示应该铺设水管，细线表示不需要铺设水管，水源建设地在凤凰乡济公村结束语图论是一种对农村自来水管网设计进行有效优化的数学方法，是将复杂的农村自来水管网处理

32、为相应的网络图，并建立相应的数学模型，用原始数据来描述管网结构，输入的数据量少，不易出错，易于计算大型的复杂管网，其计算过程可同时考虑管网附件，如控制阀、加压泵、逆止阀、减压阀等，使计算结果更加符合实际，在农村自来水管网设计中具有很好的应用前景。由于自己的水平有限，在写论文的过程中遇到了很多困难，所以写的论文难免有不足之处。参考文献1耿素云.离散数学M.北京:高等教育出版社,2009:273291.2孙惠泉.图论及其应用M.北京:科学出版社,2004:192.3黄兆东.MATLAB2007科学计算与工程分析M,北京:科学出版社,2008:231299.4朱天开.图论在排水管网优化方面的应用J,

33、中国测试技术,第1期:2004.5毛玲玲.皖江城市带交通干线布局研究J,乐山师范学院学报,第25卷,第12期:2010.6艾素梅.数学建模中的图论方法J,沧州师范专科学校学报,第26卷,第4期:2010.7燕子宗.图论及其应用J,重庆科技学院学报（自然科学版）,第9卷,第2期:2007.8岳延兵.图论在农村自来水管网设计中的应用J,山西水利技术与应用,2010年,第5期.9管志忠,图论中最短路问题在MATLAB程序实现J,安庆师范学院学报（自然科学报）第13卷第1期:2007.10姚朝灼.图论算法的可视化操作平台设计J,福州大学学报（自然科学报）,第34卷第1期:2006.11王海英,黄强,李

34、传涛,褚宝增.图论算法及其MATLAB实现M.北京:北京航天大学出版社,2010:1234.致 谢本文是在张金山老师的热情关心和指导下完成的，他渊博的知识和严谨的治学作风使我受益匪浅，对顺利完成本课题起到了极大的作用。在此向他表示我最衷心的感谢！最后向在百忙之中评审本文的各位专家、老师表示衷心的感谢！附 录（一） Kruskal算法生成最小树主要程序代码：function T c=Krusf(d,flag)if nargin=1 n=size(d,2); m=sum(sum(d=0)/2; b=zeros(3,m); k=1; for i=1:n for j=(i+1):n if d(i,j)

35、=0 b(1,k)=i; b(2,k)=j; b(3,k)=d(i,j);k=k+1; end end endelse b=d;endn=max(max(b(1:2, : );m=size(b,2);B,i=sortrows(b,3);B=B;c=0;T=;k=1; t=1:mfor i=1:m if t(B(1,i)=t(B(2,i) T(1:2,k)=B(1:2,i); c=c+B(3,i); k=k+1; tmin=min(t(B(1,i),t(B(2,i); tmax=max(t(B(1,i),t(B(2,i); for j=1:n if t(j)=tmax t(j)=tmin; en

36、d end endif k=n break; endendT;c; b=2 3 4 4 4 5 5 6 6 6 7 7 8 8 8;1 2 1 2 3 1 4 3 4 5 3 6 5 6 7;65 75 45 20 50 30 45 50 30 45 35 70 70 30 80; T c=Krusf(b,1)运行结果为：T = 4 5 6 8 7 4 4 2 1 4 6 3 1 3c = 240（二）dijkstra思想求最短路主要程序代码：function a=dijkstra(a)n=length(a);for i=2:n for j=1:(i-1) a(i,j)=a(j,i); end

37、endfor k=1:(n-1) b=1:(k-1),(k+1):n; kk=length(b); a_id=k; b1=(k+1):n; kk1=length(b1); while kk0 for j=1:kk1 te=a(k,a_id)+a(a_id,b1(j); if tea(k,b1(j) a(k,b1(j)=te; end end miid=1; for j=2:kk if a(k,b(j)k miid1=find(b1=a_id); b1=b1(1:(miid1-1),b1(miid1+1):kk1); kk1=length(b1); end end for j=(k+1):n a

38、(j,k)=a(k,j); endenda; n=8; a=ones(n)+inf; for i=1:na(i,i)=0;end a(1,4)=45; a(1,5)=30; a(2,4)=20; a(3,4)=50; a(3,7)=35; a(4,6)=30; a(6,8)=30; dijkstra(a)；运行结果为：ans = 0 130 190 90 60 150 260 210 130 0 140 40 190 100 210 160 190 140 0 100 250 160 70 220 90 40 100 0 150 60 170 120 60 190 250 150 0 210

39、320 270 150 100 160 60 210 0 230 60 260 210 70 170 320 230 0 290 210 160 220 120 270 60 290 0（三）寻找水源建设地主要程序代码； a=0 130 190 90 60 150 260 210;130 0 140 40 190 100 210 160;190 140 0 100 250 160 70 220;90 40 100 0 150 60 170 120;60 190 250 150 0 210 320 270;150 100 160 60 210 0 230 60;260 210 70 170 32

40、0 230 0 290;210 160 220 120 270 60 290 0; a=a+a; far=max(a); m,ii=min(far); m,ii运行结果为：ans = 340 4文献综述图论在农村自来水管网设计中的应用学生姓名 曾绪波 专业 数学与应用数学 班级 2007级1班 学号 07121020130图论其实是一门应用数学，它的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题。它具有以下特点：蕴含了丰富的思想、漂亮的图形和巧妙的证明；涉及的问题多且广泛，问题外表简单朴素，本质上却十分复杂深刻；解决问题的方法千变万化。非常灵活，常常是一种问题一种解法。图论研究的内容非常广泛，如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等。在许多文章里在谈到图论的时候，首先都会给出图论中图的