1.基本概念

联通的无圈图叫做树，记做为T。若图满足，则称是的生成树。图联通的充分必要条件为有生成树。一个连通数的生成树很多，用表示的生成树的公式，则有公式：

（代表有个顶点的完全图）
（代表从中删除边，表示把的长度）

树有下面常用的五个充要条件：

1.是树当且仅当中任二顶点之间有且仅有一条轨道。
2.是树当且仅当无圈，且
3.是树当且仅当联通，且
4.是树当且仅当联通，且不连通。
5.是树当且仅当无圈，恰有一个圈。

2.应用——连线问题

欲修筑连接n个城市的铁路，已知城和城之间的铁路造价为，设计一个线路图，使总造价最低。
连线问题的数学模型是在联通赋权图上求权最小的生成树。赋权图上具有最小权的生成树叫做最小生成树。
下面介绍构造最小生成树的两种常用算法。

2.1.prim算法构造最小生成解

设置两个集合和，其中用于存放的最小生成树中的边。令集合的初值为（假设最小生成树时，从顶点出发），集合的初值为。prim算法的思想是，从所有的边中，选取具有最小权值的边，将顶点加入集合中，将边加入集合中，如此不断重复，直到时，最小生成树构造完毕，这时集合中包含了最小生成树的所有边。

prime算法如下：
1.
2.while
找最小边，其中


end

例1 利用Matlab生成下面这张图的最小生成树

例1图

clc;clear;
a=zeros(7);%定义权值矩阵
a(1,2)=50; a(1,3)=60;
a(2,4)=65; a(2,5)=40;
a(3,4)=52;a(3,7)=45;
a(4,5)=50; a(4,6)=30;a(4,7)=42;
a(5,6)=70;%赋值
a=a+a';%对称矩阵 
a(find(a==0))=inf;%没有直接通路的定义为无限大
result=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
    temp=a(p,tb);temp=temp(:);
    d=min(temp);
    [jb,kb]=find(a(p,tb)==d);
    j=p(jb(1));k=tb(kb(1));
    result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end
result

2.2 Kruskal算法

1.选，使得。
2.若已选好，则从中选取，使得：
(1)中无圈
(2)
3.直到选得为止

Matlab程序：

a(4,7)=42; a(5,6)=70;
[i,j,b]=find(a);
data=[i';j';b'];index=data(1:2,:);
loop=max(size(a))-1;
result=[];
while length(result)<loop
    temp=min(data(3,:));
    flag=find(data(3,:)==temp);
    flag=flag(1);
    v1=index(1,flag);v2=index(2,flag);
    if v1~=v2
        result=[result,data(:,flag)];
    end
    index(find(index==v2))=v1;
    data(:,flag)=[];
    index(:,flag)=[];
end
result