当前位置:   article > 正文

生成树_生成树的权是什么

生成树的权是什么

参考视频

生成树

首先定义一个无向连同带权图 

G=(V,E,W)  w(e)∈W是边e的权 (其中V表示顶点集合,E表示边集,W表示权)

G的一颗生成树T是包含G的所有顶点的树,树中各边的权之和W(T)称为树的权,具有最小权的生成树称为G的最小生成树

实例

G=(V,E,W) ,V={1,2,3,4,5,6}

E={{1,2},{1,3},{1,4},{2,3},{2,5},{3,4},{3,5},{3,6},{4,6},{5,6}}  如下图所示

最小生成树(权值最小)下图所示

生成树的性质

设G是n阶的连通图

  • T是G的生成树当且仅当T无圈且有n-1条边(无圈:没有回路)如下图

  • 如果T是G的生成树,e∈T,那么T∪{e}含一个圈c  如下图

  • 去掉c的任意一条边,就得到G的另外一棵树T‘ 如下图

算法步骤

生成树性质的应用

  • 算法步骤:选择边

       约束条件:不形成回路

       截至条件:边数达到n-1

  • 改进生成树的方法

       在T中加一条非树边e,形成回路c,在c中去掉一条非树边ei,形成一颗新的生成树T‘      W(T’)-W(T) = W(e)-W(e’)

       若W(e)<=W(e’)则W(T’)<=W(T)

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/在线问答5/article/detail/820771
推荐阅读
相关标签
  

闽ICP备14008679号