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
[
上一页 ]
[ :1.70100992e+09 ]
[
下一页 ]