1。2 研究现状以及发展

对于最小生成树问题，现实世界的许多问题用文字描述特别不方便，而用图形来描写可能非常方便，这里的图形并不是几何当中的图形，而是客观世界中的某些具体事物之间联系的一个数学抽象，这种图是有一个个点的连线以及这些点组成的。这些点代表事物，称之为顶点；这些连线代表事物与事物之间的二元关系，称之为边。而有一族重要的图，我们称它为树，树应用于很多领域，特别是在计算机科学方面以及管理科学方面，树是一种特殊类型的二分图，具有很重要的地位。假设需要修建一个铁路系统，使得任意一个县城的人坐火车可以到达任意其他县城，如果县城很多，两两连接铁路线非常复杂，我们应该采用开销最小的系统，也就是采用树结构。我们用点表示县城，用一组边对应各个县城之间可以修建的铁路，得到的图一定是连通图，再把计算好的每条铁路修建的费用标注在边旁，就得到了一个连通赋权图。此连通复权图中具有最小权的生成树称为最小生成树，目前关于这个问题的研究已有较多的成果。

1。3 主要内容

首先我们先给出了图、边、顶点、树等基本概念，具备了这些知识之后才能进行后续的探讨，之后会介绍Kruskal算法以及Prim算法，这两种算法已经比较的成熟，用来解决一般的最小生成树问题已经是非常的方便，但是有些问题解决起来并不是那么容易，所以在第三章我们给出了一种新的算法来解决度约束最小生成树问题，这也是本文研究的关键所在。

第二章Kruskal算法以及Prim算法

2。1 基本概念

研究最小生成树问题，我们首先对图，树，最小生成树要有基本的认识，然后才能解决改进后的最小生成树问题，也就是度约束的最小生成树问题，还涉及了许多现实问题，解决起来也不是那么容易。文献综述

在没有特殊指定的情况下，本章涉及的图均指简单的连通图，涉及到的网络均指简单的连通无向网络。

定义2。1。1 一个图定义为一个有序队,记为,其中

（1）是一个非空集合，称为点集或顶点集，其元素称为点或顶点

（2）是由的无序点对构成的集合，称为边集，其元素称为边，并且同一点对在中可出现多次。

在没有特殊指定的情况下，我们通常用和表示图的顶点集合与图的边集。

连通性是一个图的最基本的性质，下面我们来介绍连通图，连通分支相关概念。

定义2。1。2 连通图：设和是图的两个顶点，若在中存在一条路能够连接和，则称和是连通的。若图中任意两个不同的顶点都是连通的，则称图为连通图。

仅有一个顶点的图也是连通图。显然，当仅是一条路或一个回路时，是连通的，从连通的定义可知，至少有两个顶点的连通图不含孤立顶点。

定义2。1。3 连通分支：顶点集上顶点间的连通关系是上的等价关系，该等价关系确定了的一个划分使得和是连通的当且仅当两个顶点和属于同一个子集。在中的诱导子图称为的连通分支。同时用来表示图的连通分支数。

定义2。1。4 如果不是连通图，那么图的一个顶点被称为割点。

在第三章中实际上研究的就是含有一个或多个割点的图，对于这样的图，我们可以用基于最小度约束下的最小生成树算法来更快速的解决最小生成树问题（我们将在第三章中介绍这种改进的算法）。

2。2 Prim算法

在图论的发展史中，树是一类重要的图，也是一类特殊的图，下面我们来介绍树以及生成树的相关概念。