是否有任何算法或代码可以将图节点划分为两个或多个满足以下条件的不相交集合: 首先，只允许删除边缘。 其次，对边进行加权，并且要删除的边必须具有最小权重(最小切割算法)。 第三，所需的不相交集尽可能长地具有相同的大小。
最佳答案
看起来您正在尝试解决最小二分问题，其中给定图 G，您希望将 V[G] 划分为两个大小相等的不相交子集 A 和 B，使得A 和 B 之间的边被最小化。不幸的是，the Min-bisection problem is known to be NP-hard 。然而，Kernighan–Lin algorithm是一个非常简单的 O(n^2*logn) 启发式算法。虽然理论上对该算法知之甚少(相对于最佳解决方案，我们对其性能没有经过证明的界限)，但该算法在实验中被证明非常有效:Optimization by Simulated Annealing: an Experimental Evaluation; part 1, Graph Partitioning .
关于algorithm - 将图划分为具有最小割的相同大小的不相交集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39944979/