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
