最优生成树在实际中的应用
时间:2019-10-27 12:04 来源:毕业论文 作者:毕业论文 点击:次
| 摘要 在本文中，我们从图论的角度出发，将现实生活中的一些问题抽象为图论方面的问题，并运用Kruskal算法求解最优生成树，寻找出最合理，最科学的交通运输或者管道运输路线以及最优化的网络结构等等.再将理论联系实际，为现实生活中道路建设与分布，管道建设，网络分布等等提供一些参考，给予一些帮助.41490 毕业论文关键词 最优生成树；Kruskal算法；交通、网络结构. 1.引言 对于通过运用Kruskal算法求解最优生成树的方法来解决一些实际生活中的问题早已有人开始进行研究，但主要都是在网络结构方面，对网络的布局进行了研究.本文也有涉及，且还根据实际情况做出了些许改动，以便更合理解决问题.同时，本文还将理论应用于交通运输路线的选取和分布上面.相信本文的研究结果对城市中交通线路的建设一定能提供一些有价值的参考. 2.预备知识论文网 在进入主要定理的证明与应用之前，我需要给大家先提供一些定义： 图：一个图G是指 一个有序的三元组 .其中 是一个非空顶点集； 是不与 相交的边集；而 是它们的关联函数，它会使G的每条边对应于G的无序顶点（不必相异）. 无圈图：不包含圈的图我们称为无圈图. 树：连通的无圈图我们则称之为树. 子图：如果 , 在 上的限制，则图H是图G的子图. 生成子图：图G的生成子图是指满足 的子图H，当H是树时，则称H为生成树. 3.主要内容 在实际生活中，为了给一些村庄联合提供木材，必须要在各个村庄之间建立科学合理的交通运输路线，在设计和规划这些路线时，往往需要制作一个缩略图，用点表示村庄，用边与各村子之间的路线相对应.如此一来，这些点和线就构成了简单的连通图，我们将这个图记为图G，如图1所示: 很自然，每条线长短不一，造价自然也随之变化.我们把每条路线的总费用分别计算出来写在与之对应的每条边的旁边，这便是每条边的权，记为 ，这样我们就可以得到一个赋权图，如图2所示. 在这之后，我们所需要做的就是找出一个总造价最低的交通运输系统.而与之相对应的，就是在图中找出具有最小权和的链条生成子图.由于在这里的权表示的是路线的建造费用，所以一定是非负的.从而我们可以断定最小生成子图是图G的一棵生成树.又因为我们所找的树是权和最小的，所以便为最优生成树，如图3所示： 那么，究竟该如何简单又便捷的得到图3所示的最优生成树呢？这里，我们就要引入Kruskal算法了. 现在，我们就来看一下什么是Kruskal算法 （1） 在图 中选取边 ，使 尽可能的小. （2） 若以选定边 ，则从 中选取边 ，使得满足下列的两个条件： 1. 不含有回路. 2.在满足1.的情况下，使 尽可能小. （3） 重复执行（2），当（2）无法执行时结束. 在这里，需要说明的是： 1. 由Kriskal算法得到的图 是图G的生成树. 2. 生成树T是最优生成树. 我们先来说明第1.点.因为Kruskal算法的每一步都要求不出现回路，因此，我们得到的T没有回路.当 不是G的生成树时，即有 也不是生成子图.那么，我们就可以在 中选边 ，使得 至少有一个端点不在 上，从而 也没有回路.即存在满足Kruskal算法中第（2）步的边 .那也就是说，Kruskal算法在执行了k次之后还可以继续执行，这就产生了矛盾.另一方面，如果 不连通，又由于图G是连通的，所以我们可以在图G中找出一条边 与 相连.此时， 也是没有回路的，也就是说，Kruskal算法也是可以继续执行的，从而又产生矛盾.综上所述，我们就可以得到图 的生成树. (责任编辑：qin) |