1701009920
（3）在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。
1701009921
1701009922
（4）图中边数有ne＝p-1（p为顶点数）。
1701009923
1701009924
生成树：如果图T是G的一个生成子图，而且T又是一棵树，则称图T为一棵生成树。
1701009925
1701009926
【问题】
1701009927
1701009928
如图8-20所示为一图模型，试求其最小生成树。
1701009929
1701009930
1701009931
1701009932
1701009933
图8-20 图模型
1701009934
1701009935
【分析】
1701009936
1701009937
Kruskal算法又称避圈法，对于求解最小树模型很有效，其具体求解流程如下：
1701009938
1701009939
（1）选择边e1，使得w（e1）尽可能小；
1701009940
1701009941
1701009942
1701009943
1701009944
（2）若已选定边，则从中选取，使得：
1701009945
1701009946
1701009947
①为无圈图；
1701009948
1701009949
1701009950
②是满足（i）的尽可能小的权。
1701009951
1701009952
③当第（2）步不能继续执行时，则停止。
1701009953
1701009954
采用计算机，MATLAB编程如下：
1701009955
1701009956
%避圈法 clc %清屏 clear all; %删除workplace变量 close all; %关掉显示图形窗口 b=[1 2 1; 1 3 4; 2 3 2; 2 4 3; 2 5 5; 3 4 1; 3 5 3; 4 5 2] [T,v,c]=kruskal(b)
1701009957
1701009958
其中Kruskal算法脚本文件如下：
1701009959
1701009960
%Kruskal算法 %b-图的边权矩阵 %T-最小生成树的边集合 %v-最小生成树的邻接矩阵 %c-最小生成树的权 %j-迭代的次数 %k-已经被选入生成树的边数 function [T,v,c]=kruskal(b) %根据边权矩阵求出图的边数 m=size(b,1); %根据边权矩阵求出图的顶点数，注意此处顶点的标号需要以自然数序 n=max(b(1:2*m)); %整理边权矩阵让其按照权值由小到大的次序重新排列 [B,index]=sortrows(b,3); B=B’; %数据的初始化 t=1:n; k=0; T=[]; c=0; %更新T,c,t(i) for i=1:m if t(B(1,i))~=t(B(2,i)) %判断第i条边是否与树中的边形成圈 k=k+1; T(1:2,k)=B(1:2,i); c=c+B(3,i); tmin=min(B(1,i),B(2,i)); tmax=max(B(1,i),B(2,i)); for j=1:n if t(j)==tmax t(j)=min(tmin,t(tmin)); end end end if k==n-1 break; end end %根据最小生成树的边集合构造邻接矩阵 v=zeros(n); k=size(T,2); for i=1:k v(T(2*i-1),T(2*i))=1; v(T(2*i),T(2*i-1))=1; end
1701009961
1701009962
运行程序输出结果如下：
1701009963
1701009964
b = 1 2 1 1 3 4 2 3 2 2 4 3 2 5 5 3 4 1 3 5 3 4 5 2 T = 1 3 2 4 2 4 3 5 v = 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 c = 6
1701009965
1701009966
由结果可知，最小树模型为：
1701009967
1701009968
1701009969