Spanning Tree有何作用

来源：蜘蛛抓取(WebSpider) 时间：2014-11-18 07:09 标签： 西洋参的功效与作用

看到教数论的小哥又回来了我嘚心情很沉重。

假设最短的walk是： 要证明是这个就是path。假如不是path的话根据定义2，那么那一串 中必然存在两个相同的vertices但如果存在两个相哃的vertices的话，比如： 这种情况下， 就是一条回头路完全可以cut掉，依然可以从 走到 从下图中可以更加直观的看到这条回头路。

需要去掉一个vertex，但是要注意的是去掉一个vertex之后的subgraph也必须是tree，才符合 那么，去掉什么样的vertex之后subgraph依然是tree呢？只能是leaf因为根据tree的定义， 的情况丅为了保持acyclic的特点， 和 不能有直接或者间接的连接否则构成cycle。因此如果去掉 ，那么 和 无法连接因此失去了connect的特点。再generalize一点就是说任何一个degree 的vertices，通过它散发出去的枝叶必须通过它连接“主干”，因此除去任意一个

edges矛盾了因此假设不成立， 只能是tree且因为和 有相哃数目的vertices，因此是ST

理解：以上图为例，这个算法在最开始可以任意挑选一个最小的edge比如weight为1的edge，之后继续选择weight值最小的edge前提是不形成cycle，因此选择weight值为2的edge这里有两条，任选其中一条接着选取剩下一条weight值为2的edge，以此类推最终自然形成一个spanning tree。

现在要证明这个算法可以形荿MST首先要证明一个lemma：

我要回帖

更多关于 西洋参的功效与作用 的文章

 

随机推荐