我正在实现最小割集图聚类,并且我需要能够将一个图分成两个部分-- S和T,根据在每个聚类步骤上构建的针对的和t顶点的st min裁剪。基本上,我希望有一个函数,它接受图G、节点s和节点t,并返回两个不相交的节点集S和TE 217
。
据我所知,找到最小流量的最简单方法是利用最小切割~最大流量对偶,并使用推挽算法进行最大流量计算。但是推挽算法并没有给我们任何关于、S、和T集的信息。
那么,获得S和T最小剪切子集的正确方法是什么?有一种方法可以使用推挽算法吗?这在C++或Python中有实现吗?
发布于 2013-10-18 08:40:42
您可以使用推挽算法计算的信息来确定最小切割。众所周知,推挽算法为每个顶点分配一个值h( v ),h(v)的可能值在区间0,N中,其中N是图的顶点数。很容易证明,对于每个顶点v,都存在一些数h‘以至于h(v) != h’(见Cormen书,第二版,练习26.4-3 )。在找到这样的h‘后,h(v) < h’的每个顶点v都在割集的一侧,而h(u) > h‘的每个顶点u都在另一边。
https://stackoverflow.com/questions/17673393
复制相似问题