树与最小生成树在中学数学建模方法中的应用

一、基本概念

连通的无圈图叫做树，记之为T.若图G满足V (G )=V (T)，E (T)⊂E (G)，则称T是G的生成树.图G连通的充分必要条件为G有生成树.一个连通图的生成树的个数很多，赋权图的具有最小权的生成树叫做最小生成树.本节介绍最小生成树的算法及其应用.

二、prim算法构造最小生成树

（1）prim算法的思想.

设置两个集合P和Q，分别用于存放G的最小生成树中的顶点和边.令集合P的初值为P ={v1}（假设构造最小生成树时，从顶点v1出发），集合Q的初值为Q=∅.从所有p ∈P，v ∈V -P的边中，选取具有最小权值的边pv，将顶点v加入集合P中，将边pv加入集合Q中，如此不断重复，直到P =V时，最小生成树构造完毕，这时集合Q中包含了最小生成树的所有边.

（2）prim算法的步骤.

三、应用——连线问题(www.xing528.com)

欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为Cij（见图8.3.1），设计一个线路图，使总造价最低.此类问题我们称为连线问题.连线问题的数学模型是在连通赋权图上求权最小的生成树.构造最小生成树可使用prim算法.

图8.3.1　铁路网造价

我们用result3× n 的第一、二、三行分别表示生成树边的起点、终点、权，s表示最小权.MATLAB程序如下：

运行结果如下：

即应修筑1到2、2到5、5到4、4到6、4到7、7到3的铁路，总造价257.