图解:割边集、反圈

被《通信网性能分析基础》这本书搞糊涂了。
说“反圈”的概念比较重要,却一直没搞懂。
原来“反圈”不是个圈,它只是个特定的割边集。(“反圈”到底是谁的发明...)
书上讲反圈,是为了讲后面的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

割边集

割边集,是图中某些边的集合,如果图中这些边都没有了,这个图就不再连通了。
比如,随便画一个连通图。
graph1_base
graph2_cut
graph3_cut_set
去掉{ e16, e26, e56 }这些边,v6这个点就被孤立出来了,整个图就不连通了。
于是,{ e16, e26, e56 }就是这个图G={V, E}的其中一个割边集。

反圈

现在,比如说,我们就想要把这个图割裂成两个图,图一有点{v1, v2, v5, v6},图二有点{v3, v4}.
graph4_fq
那么,能这么切开这个图的方法只有一个,也就是说,这样切的割边集只有唯一一个。
我们把这唯一一个能把图切成这样子的割边集,称为“反圈”。
graph5_fq
于是,这里的反圈就是{e23, e35, e14, e45}

再举一例,能将图分成两图,图一有点{v1, v2},图二有点{v3, v4, v5, v6}的反圈,是这个割边集{e16, e26, e14, e23}
graph6_fq

《图解:割边集、反圈》有一个想法

  1. 来膜拜下学霸,从果壳网过来的,方便的话加个QQ:307300100 聊聊。

评论已关闭。