文档介绍：§ 最小树
1、最小树及其性质
支撑树T的权(或长):
最小支撑树:G中权最小的支撑树
设T是G的支撑树, 则T是G的最小树当且仅当对任意边有

其中为一个唯一的回路。
设T是G的支撑树, 则T是G的最小树当且仅当对任意边有

其中为一个唯一割集。
设T是G的支撑树,则T是G的唯一最小树当且仅当对任意边,e是C(e)中的唯一最大边。
设T是G的支撑树,则T是G的唯一最小树当且仅当对任意边,e是中的唯一最大边。
2、求最小树的Kruskal算法(贪心算法或避圈法)
基本思想:从图的条边中选取条权尽量小的边,并且使它们不构成回路。
理论基础:
具体步骤:首先选出一条权最小的边,再从剩下的边中选出一条权最小的, 并且与前面已经选出的边不构成回路。如此选下去,直到选出条边为止。

第1步开始把边按权的大小由小到大排列起来,即
置,,。
第2步若,则停。这时即为所求;否则, 转向第3步。
第3步若不构成回路,则置,,,,转向第2步;否则,置,转向第2步。
例:。
2
1
3
4
4
4
2
2
①
②
③
④
⑤

解:
②
4
3
1
⑤
④
①
2
2
4
2
4

③

3、求最小树的破圈法
具体步骤:任意选出图的一条回路,从中去掉一条权最大的边。重复这一过程,直到图不存在回路为止。
理论基础:
②
4
3
1
⑤
④
①
2
2
4
2
4

③
4、求最小树的Dijkstra算法(狄克斯托)
基本思想:从图的个独立割集中的每一个都选出一条权最小的边。
理论基础:
具体步骤:
(1):置
(2):取,置;
(3):若,则停止;否则,置,返回(2)。
上面是