首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >根据s和t点间的最小割集将图分成两部分。

根据s和t点间的最小割集将图分成两部分。
EN

Stack Overflow用户
提问于 2013-07-16 09:53:59
回答 1查看 2.8K关注 0票数 1

我正在实现最小割集图聚类,并且我需要能够将一个图分成两个部分-- ST,根据在每个聚类步骤上构建的针对t顶点的st min裁剪。基本上,我希望有一个函数,它接受图G、节点s和节点t,并返回两个不相交的节点集STE 217

据我所知,找到最小流量的最简单方法是利用最小切割~最大流量对偶,并使用推挽算法进行最大流量计算。但是推挽算法并没有给我们任何关于、S、和T集的信息。

那么,获得S和T最小剪切子集的正确方法是什么?有一种方法可以使用推挽算法吗?这在C++或Python中有实现吗?

EN

回答 1

Stack Overflow用户

发布于 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都在另一边。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/17673393

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档