摘要在最小生成树的问题的求解中常用的是Prim算法和Kruskal算法，这两种算法都有各自的优缺点，在本文中,我们在这两种算法的基础上对经典算法进行了改进，提出了一种新的算法来有效的解决最小生成树问题，是针对网络通信问题以及组合优化中的度约束最小生成树问题。我们处在一个网络计算机时代，这个时代是由电话通信、运输网络、能源分派等各种网络组合而成的复杂的网络问题的时代。我们要对网络系统进行有效的计划、管理以及控制，使之能发挥出最大的经济效益和社会效益。本文要研究的度约束最小生成树问题就是网络优化中的一个常见的问题。

本文主要讲述的是如下几个部分：82313

在第二章节的内容中对图、边、顶点、树等这些基本的概念进行简单的介绍，然后介绍了Kruskal算法以及Prim算法。在第三章中，我们提出了度约束最小生成树问题，针对该问题给出了一种新的算法，从实验结果来看，该算法可以有效的解决度约束最小生成树问题。

毕业论文关键词：最小生成树；度约束；连通图

Abstract We used the Prim algorithm and Kruskal algorithm in solving the problem of minimum spanning tree。 Both of these two algorithms have their own advantages and disadvantages。 Based on these two algorithms, we improve the algorithm。 In this paper, we propose a new algorithm to solve the minimum spanning tree problem effectively。 This proplem is aimed at the problem of network communication and the minimum spanning tree problem in combinatorial optimization。 We are in an era of Internet, which is an era full of complex network problem, and composed of telephone communication, transportation network, energy distribution and so on。 We need to plan, manage and control the network system effectively, so as to achieve the maximum economic and social benefits。 This paper is to study the degree constrained minimum spanning tree problem which is a common problem in network optimization。

This paper is mainly about the following parts:

In the second chapter of this paper, we give the content of the graph, edge, vertex, tree and other basic concepts of graph theory, and then introduce the Kruskal algorithm and Prim algorithm。 In the third chapter, we propose a new algorithm for the minimum spanning tree problem, which is based on the experimental results, and the algorithm can solve the problem of minimum spanning tree problem more effectively。

Keywords: Minimum spanning tree; Degree constraint; Connected graph

目  录

第一章 绪论 -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算法，但如果我们在原来的生成树上再加上一定的限制，比如生成树中各顶点的度数不超过原先给定的数值，那么原本的问题的性质就不一样了。在现实生活中就有这样的例子，在道路系统设计上有许多十字路口，而十字路口是由2条路构成的，通信网络中为了防止一系列的故障（我们这里考虑节点故障）而带来的脆弱性，对节点的度会有限制，像这种对顶点度有约束的最小生成树问题我们称它为度约束最小生成树。可以更好的解决许多现实问题。论文网