用最小割将图分成相同大小的不相交集 [英] Divide a graph into same size disjoint sets with minimum cut

问题描述

是否有任何算法或代码将图节点划分为满足以下条件的两个或多个不相交的集合:首先，只允许移除边缘.其次，边缘被加权，那些将被删除的必须具有最小权重(最小切割算法).第三，期望的不相交集合的大小尽可能长.

Is there any algorithm or code that divide graph nodes into two or more disjoint sets that satisfy following conditions: first, only edges allowed to remove. second, edges are weighted and those that would be removed must has minimum weight(minimum cut algorithm). third,desired disjoint sets have same size as long as possible.

推荐答案

看起来您正在尝试解决最小二分问题，其中给定图 G，您希望将 V[G] 划分为两个不相交的子集A 和 B 的大小相等，使得 A 和 B 之间的边的权重之和最小.不幸的是，最小-二分问题已知是 NP-hard.然而，Kernighan–Lin 算法是一个非常简单的 O(n^2*logn) 问题的启发式算法.虽然理论上对该算法知之甚少(我们没有证明其性能相对于最佳解决方案的界限)，但该算法 在实验中显示非常有效.

It looks like you're trying to solve the Min-bisection problem in which given a graph G you would like to partition V[G] into two disjoint subsets A and B of equal size such that the sum of weights of the edges between A and B is minimized. Unfortunately, the Min-bisection problem is known to be NP-hard. However, Kernighan–Lin algorithm is a very simple O(n^2*logn) heuristic algorithm for the problem. While very little is known about the algorithm theoretically (we do not have a proven bound on its performance relative to an optimal solution), the algorithm is shown to be quite effective in experiments.

这篇关于用最小割将图分成相同大小的不相交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！