algorithm - 用最小割将图划分为相同大小的不相交集

Question

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

Answer 1

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