【运筹学】最小支撑树

最小支撑树

图的生成子图是树，则该树称之为对应的最小支撑树。
求支撑树有避圈法和破圈法

• 1.避圈法

在图中一条一条地抽取边，每次从剩余的边中取权重最小的边，并且保证取出来之后不会形成圈。选够n-1条边为止（n为顶点数），若选取的边数还没有达到n-1，而某条边不适合，则选取权重高一点的边。

• 2.破圈法

在图中随意找一个构成圈的图形，去除其权重最大的一条边。若存在权重相同的边，则随便去除一条即可，直至图中不再有圈为止。

案例分析

1.避圈法
（1）取v1——v2
（2）取v2——v3
（3）取v1——v3
（4）取v1——v4或v4——v5
结果如图：

2.破圈法
（1）v1 v2 v3中去除v1——v3
（2）v1 v2 v5中去除v2——v5
（3）v1 v4 v5中去除v1——v4或者v4——v5
（4）若上一步去除v1——v4，则还有一个圈，权重最大的是v3——v4，去除
结果还是和避圈法相同