是否有任何算法或代码将图节点划分为两个或多个满足以下条件的不相交集合：
首先，只允许删除边缘。
其次，对边进行加权，并且要删除的边必须具有最小权重（最小切割算法）。
第三，所需的不相交集尽可能长地具有相同的大小。
看起来您正在尝试解决最小二分问题，其中给定图 G，您希望将 V[G] 划分为两个大小相等的不相交子集 A 和 B，使得 A 之间的边的权重之和并且 B 被最小化。很遗憾，已知最小二分问题是 NP 困难问题 http://udel.edu/%7Eheinz/classes/2014/4-667/materials/readings/Garey%20and%20Johnson/Chapter%20One.pdf。然而，Kernighan-Lin 算法 https://en.wikipedia.org/wiki/Kernighan%E2%80%93Lin_algorithm是一个非常简单的 O(n^2*logn) 启发式算法。虽然理论上对该算法知之甚少（相对于最佳解决方案，我们没有证明其性能的界限），但该算法在实验中被证明非常有效：通过模拟退火进行优化：实验评估；第 1 部分，图分区 https://faculty.washington.edu/aragon/pubs/annealing-pt1.pdf.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
