1701009905
我和数学有约：趣味数学及算法解析 [:1701004265]
1701009906
我和数学有约：趣味数学及算法解析 8.5 最小树问题
1701009907
1701009908
【问题】何谓最小树？
1701009909
1701009910
【分析】
1701009911
1701009912
树：如果图G是一个无圈的无向连通图，则称图G为树，记作T。树中的边称为树枝。
1701009913
1701009914
树的性质：
1701009915
1701009916
（1）在图中任意两点之间必有一条而且只有一条通路。
1701009917
1701009918
（2）在图中划去一条边，则图不连通。
1701009919
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编程如下：