1701009900
七桥模型衍射出的图论模型在现今的道路交通规划中起到了重要作用，例如最短路问题、最小树模型和最大流模型等，这些问题的求解对于工程应用具有重要的意义。
1701009901
1701009902
1701009903
1701009904
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
