首页 > 其他 > 详细

生成树相关问题

时间:2016-09-26 12:32:44      阅读:214      评论:0      收藏:0      [点我收藏+]

关于生成树的两个性质:

(1)切割性质。假定所有边权均不相同。设$S$为既非空集也非全集的$V$的子集,边$e$是满足一个端点在$S$内,另一个端点在$V \setminus S$内所有边权最小的一个,则图$G$的所有最小生成树均包含$e$。

说明:设$T=V\setminus S$,则图$G$的任一生成树包含$S-T$割中的一条边(连通性)。考虑$e$作为$S-T$中唯一权值最小的边,则$MST(V)= MST(T) + MST(S) + e$,这是显然的。

(2)回路性质。

生成树相关问题

原文:http://www.cnblogs.com/astoninfer/p/5908660.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!