图解:割边集、反圈 – 肥叉烧 feichashao.com |
您所在的位置:网站首页 › 什么是割边挂码的意思 › 图解:割边集、反圈 – 肥叉烧 feichashao.com |
被《通信网性能分析基础》这本书搞糊涂了。 说“反圈”的概念比较重要,却一直没搞懂。 原来“反圈”不是个圈,它只是个特定的割边集。(“反圈”到底是谁的发明...) 书上讲反圈,是为了讲后面的Prim算法,事实上知不知道“反圈”对理解Prim算法毫无影响。 割集:http://en.wikipedia.org/wiki/Cut_set Prim算法:http://zh.wikipedia.org/wiki/%E6%99%AE%E6%9E%97%E5%A7%86%E7%AE%97%E6%B3%95 割边集割边集,是图中某些边的集合,如果图中这些边都没有了,这个图就不再连通了。
比如,随便画一个连通图。
现在,比如说,我们就想要把这个图割裂成两个图,图一有点{v1, v2, v5, v6},图二有点{v3, v4}.
再举一例,能将图分成两图,图一有点{v1, v2},图二有点{v3, v4, v5, v6}的反圈,是这个割边集{e16, e26, e14, e23}
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |