一种改进的最小生成树问题animprovedminimumspanningtreeproblem(附件)【字数：5794
摘 要摘 要在最小生成树的问题的求解中常用的是Prim算法和Kruskal算法，这两种算法都有各自的优缺点，在本文中,我们在这两种算法的基础上对经典算法进行了改进，提出了一种新的算法来有效的解决最小生成树问题，是针对网络通信问题以及组合优化中的度约束最小生成树问题.我们处在一个网络计算机时代，这个时代是由电话通信、运输网络、能源分派等各种网络组合而成的复杂的网络问题的时代。我们要对网络系统进行有效的计划、管理以及控制，使之能发挥出最大的经济效益和社会效益。本文要研究的度约束最小生成树问题就是网络优化中的一个常见的问题。本文主要讲述的是如下几个部分在第二章节的内容中对图、边、顶点、树等这些基本的概念进行简单的介绍，然后介绍了Kruskal算法以及Prim算法。在第三章中，我们提出了度约束最小生成树问题，针对该问题给出了一种新的算法，从实验结果来看，该算法可以有效的解决度约束最小生成树问题。关键词最小生成树；度约束；连通图
目 录
第一章 绪论 1
1.1 研究背景1
1.2 研究现状以及发展1
1.3 主要内容1
第二章 Kruskal算法以及Prim算法3
2.1 基本概念3
2.2 Prim算法4
2.3 Kruskal算法7
第三章 基于最小度约束下的最小生成树算法9
3.1 度约束最小生成树问题的概述9
3.2 度约束最小生成树问题的相关概念9
3.3 基于最小度约束下的最小生成树算法10
3.3.1算法思想10
3.3.2算法步骤11
3.4 数值实例11
结论16
致谢17
参考文献18
绪论
1.1 研究背景
最小生成树问题是我们在解决计算机网络、通信网络、运输网络设计中一个常见的基本问题，人们对最小生成树问题的研究兴趣一直很浓厚，相关的理论也被应用到了更多的领域。现已经有比较成熟的算法可以有效的解决，例如Kruskal算法以及Prim算法，但如果我们在原来的生成树上再加上一定的限制，比如生成树中各顶点的度 *好棒文|www.hbsrm.com +Q: #351916072#
数不超过原先给定的数值，那么原本的问题的性质就不一样了。在现实生活中就有这样的例子，在道路系统设计上有许多十字路口，而十字路口是由2条路构成的，通信网络中为了防止一系列的故障（我们这里考虑节点故障）而带来的脆弱性，对节点的度会有限制，像这种对顶点度有约束的最小生成树问题我们称它为度约束最小生成树。可以更好的解决许多现实问题。
1.2 研究现状以及发展
对于最小生成树问题，现实世界的许多问题用文字描述特别不方便，而用图形来描写可能非常方便，这里的图形并不是几何当中的图形，而是客观世界中的某些具体事物之间联系的一个数学抽象，这种图是有一个个点的连线以及这些点组成的。这些点代表事物，称之为顶点；这些连线代表事物与事物之间的二元关系，称之为边。而有一族重要的图，我们称它为树，树应用于很多领域，特别是在计算机科学方面以及管理科学方面，树是一种特殊类型的二分图，具有很重要的地位。假设需要修建一个铁路系统，使得任意一个县城的人坐火车可以到达任意其他县城，如果县城很多，两两连接铁路线非常复杂，我们应该采用开销最小的系统，也就是采用树结构。我们用点表示县城，用一组边对应各个县城之间可以修建的铁路，得到的图一定是连通图，再把计算好的每条铁路修建的费用标注在边旁，就得到了一个连通赋权图。此连通复权图中具有最小权的生成树称为最小生成树，目前关于这个问题的研究已有较多的成果。
1.3 主要内容
首先我们先给出了图、边、顶点、树等基本概念，具备了这些知识之后才能进行后续的探讨，之后会介绍Kruskal算法以及Prim算法，这两种算法已经比较的成熟，用来解决一般的最小生成树问题已经是非常的方便，但是有些问题解决起来并不是那么容易，所以在第三章我们给出了一种新的算法来解决度约束最小生成树问题，这也是本文研究的关键所在。
Kruskal算法以及Prim算法
2.1 基本概念
研究最小生成树问题，我们首先对图，树，最小生成树要有基本的认识，然后才能解决改进后的最小生成树问题，也就是度约束的最小生成树问题，还涉及了许多现实问题，解决起来也不是那么容易。
目 录
第一章 绪论 1
1.1 研究背景1
1.2 研究现状以及发展1
1.3 主要内容1
第二章 Kruskal算法以及Prim算法3
2.1 基本概念3
2.2 Prim算法4
2.3 Kruskal算法7
第三章 基于最小度约束下的最小生成树算法9
3.1 度约束最小生成树问题的概述9
3.2 度约束最小生成树问题的相关概念9
3.3 基于最小度约束下的最小生成树算法10
3.3.1算法思想10
3.3.2算法步骤11
3.4 数值实例11
结论16
致谢17
参考文献18
绪论
1.1 研究背景
最小生成树问题是我们在解决计算机网络、通信网络、运输网络设计中一个常见的基本问题，人们对最小生成树问题的研究兴趣一直很浓厚，相关的理论也被应用到了更多的领域。现已经有比较成熟的算法可以有效的解决，例如Kruskal算法以及Prim算法，但如果我们在原来的生成树上再加上一定的限制，比如生成树中各顶点的度 *好棒文|www.hbsrm.com +Q: #351916072#
数不超过原先给定的数值，那么原本的问题的性质就不一样了。在现实生活中就有这样的例子，在道路系统设计上有许多十字路口，而十字路口是由2条路构成的，通信网络中为了防止一系列的故障（我们这里考虑节点故障）而带来的脆弱性，对节点的度会有限制，像这种对顶点度有约束的最小生成树问题我们称它为度约束最小生成树。可以更好的解决许多现实问题。
1.2 研究现状以及发展
对于最小生成树问题，现实世界的许多问题用文字描述特别不方便，而用图形来描写可能非常方便，这里的图形并不是几何当中的图形，而是客观世界中的某些具体事物之间联系的一个数学抽象，这种图是有一个个点的连线以及这些点组成的。这些点代表事物，称之为顶点；这些连线代表事物与事物之间的二元关系，称之为边。而有一族重要的图，我们称它为树，树应用于很多领域，特别是在计算机科学方面以及管理科学方面，树是一种特殊类型的二分图，具有很重要的地位。假设需要修建一个铁路系统，使得任意一个县城的人坐火车可以到达任意其他县城，如果县城很多，两两连接铁路线非常复杂，我们应该采用开销最小的系统，也就是采用树结构。我们用点表示县城，用一组边对应各个县城之间可以修建的铁路，得到的图一定是连通图，再把计算好的每条铁路修建的费用标注在边旁，就得到了一个连通赋权图。此连通复权图中具有最小权的生成树称为最小生成树，目前关于这个问题的研究已有较多的成果。
1.3 主要内容
首先我们先给出了图、边、顶点、树等基本概念，具备了这些知识之后才能进行后续的探讨，之后会介绍Kruskal算法以及Prim算法，这两种算法已经比较的成熟，用来解决一般的最小生成树问题已经是非常的方便，但是有些问题解决起来并不是那么容易，所以在第三章我们给出了一种新的算法来解决度约束最小生成树问题，这也是本文研究的关键所在。
Kruskal算法以及Prim算法
2.1 基本概念
研究最小生成树问题，我们首先对图，树，最小生成树要有基本的认识，然后才能解决改进后的最小生成树问题，也就是度约束的最小生成树问题，还涉及了许多现实问题，解决起来也不是那么容易。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/jsjkxyjs/746.html
