文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 算法合集之《最小生成树算法及其应用》
侵权投诉

算法合集之《最小生成树算法及其应用》

【摘要】 最小生成树是图论中的经典问题,也是一个重要部分,一般书上 往往只介绍求最小生成树的算法,而忽略了更精彩的算法应用部分。 本文将对最小生成树算法及其应用作全面的分析说明, 使大家对此有 更加深刻的认识。本文分三部分:一、基础篇,主要介绍基础概念、 求最小生成树的一般算法和常用算法。二、应用篇,具体问题具体分 析,侧重于思考和证明的过程。三、总结。

图1 一个图的割(S,V-S)

首先定义几个概念。有向图G=(V,E)的割(S,V-S)是V的一个分划。当一条边(u,v)∈E的一个端点属于S而另一端点属于V-S,我们说边(u,v)通过割(S,V-S)。若集合A中没有边通过割,就说割不妨碍集合A。如果某边是通过割的具有最小权值的边,则称该边为通过割的一条轻边。

如图1,集合S中的结点为黑色结点,集合V-S中的结点为白色结点。连接白色和黑色结点的那些边为通过该割的边。从边上所标的权值看,边(d,c)为通过该割的唯一一条轻边。子集A包含阴影覆盖的那些边,注意,由于A中没有边通过割,所以割(S,V-S)不妨碍A。

确认安全边的规则由下列定理给出。

定理1 设图G(V,E)是一无向连通图,且在E上定义了相应的实数值加权函数w,设A是E的一个子集且包含于G的某个最小生成树中,割(S,V-S)是G的不妨碍A的任意割且边(u,v)是穿过割(S,V-S)的一条轻边,则边(u,v)对集合A是安全的。

证明:设T是包含A的一最小生成树。如果T包含轻边(u,v),则T包含A∪{(u,v)},证明就完成了。否则,可设法建立另一棵包含A∪{(u,v)}的最小生成树T’,(u,v)对集合A仍然是安全的。

算法合集之《最小生成树算法及其应用》

图2 最小生成树T’的建立

图2示出了最小生成树T’的建立。S中的结点为黑色,V-S中的结点为白色,边(u,v)与T中从u到v的通路P构成一回路。由于边(u,v)通过割(S,V-S),因此在T中的通路P上至少存在一条边也通过这个割。设(x,y)为满足此条件的边。因为割不妨碍A,所以边(x,y)不属于A。又因为(x,y)处于T中从u到v的唯一通路上,所以去掉边(x,y)就会把T分成两个子图。这时加入边(u,v)以形成一新的生成树T’=(T-{(x,y)})∪{(u,v)}。

下一步我们证明T’是一棵最小生成树。因为(u,v)是通过割(S,V-S)的一条轻边,且边(x,y)也通过割,所以有w(u,v)≤w(x,y),因此w(T’)=w(T)-w(x,y)+w(u,v)

算法合集之《最小生成树算法及其应用》

上一页第3页

你可能喜欢

  • 最小生成树算法
  • 算法竞赛
  • 算法代码
  • 动态规划经典
  • ACM模板
  • 后缀数组
  • ACM算法

热门文档

相关文档

  • 算法合集之《生成树的计数及其应用》

    算法合集之《生成树的计数及其应用》 摘要 在信息学竞赛中,有关生成树的最优化问题如最小生成树等是我们经常遇到的,而对生成树的计数及其相关问题则少有涉及。事实...

  • 最小生成树算法及应用

    PPT最小生成树算法与运用 17页 2财富值 一种改进最小生成树算法在... 6页 5财富值喜欢此文档的还喜欢 算法合集之《最小生成树算... 29页 免费 图论 最小...

  • 最小生成树算法及其应用

    最小生成树算法及其应用_一年级数学_数学_小学教育_教育专区。最小生成树算法及其...算法合集之《最小生成树... 29页 免费 最小生成树的算法 7页 免费 最小生...

  • 算法合集之《最小生成树问题的拓展》

    1.2 求解最小生成树的算法 求最小生成树,比较常用的算法有 Prim 算法和 Kruskal 算法。前者借助 Fibonacci 堆可 以使复杂度降为 O(Vlog2V+E),后者一般应用...

  • 【论文】最小生成树算法及其应用

    最小生成树是数据结构中图的一种重要应用,对于具有n个...

  • 算法合集之《生成树的计数及其应用》

    算法合集之《生成树的计数及其应用》_IT/计算机_专业资料。算法合集本...关生成树的最优化问题如最小生成树等是我们经常遇到 的,而对生成树的计数及其...

  • 算法合集之《欧几里得算法的应用》

    容易想像,任何带“取模”操作并符合偏序的两个“数”7 都可以运用欧几里得算法...算法合集之《最短路算法... 30页 免费 算法合集之《最小生成树... 29页 免费...

  • 算法合集之《动态树问题及其应用》

    算法合集之《动态树问题及其应用》_IT/计算机_专业资料。算法合集之《动态树问题...Prim最小生成树算法的动... 5页 免费 算法合集之《浅谈贪心思... 15页 免费...

  • 算法合集之《生成树的计数及其应用》

    算法合集之《生成树的计数及其应用》_IT/计算机_专业资料。摘要 在信息学竞赛中,有关生成树的最优化问题如最小生成树等是我们经常遇到的,而对生成树的计数及其相...

  • 最小生成树算法(一)

    最小生成树算法(一)_计算机软件及应用_IT/计算机_专业资料。最小生成树算法(一...17页 1下载券 算法合集之《最小生成树... 29页 免费2014 Baidu 使用百度...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email