我得到了一个有许多独立成分的图。每个组成部分都是二部的。如何将顶点分布到A和B两个集合中，使两个集合之间的差异最小？
例子：
1:1 -> 2 ->3 -> 4 -> 5
2:6 -> 7 -> 8
最好的解决办法是A = {1, 3, 5, 7}B = {2, 4 ,6, 8}
另一个（非最优）解决方案是A = {1, 3, 5, 6, 8}B = {2, 4, 7}
当图有许多独立的二部组件时，如何解决这个问题？
最佳答案
这是一个略带伪装的Partition Problem。对于每一个二部分量，取独立集合中元素的个数之差（实际上是绝对值），这是分区问题的输入对于您的示例，它将是[1,1]（from（3-2）和（2-1）。）
现在将解决方案转换回图形。对于数字以集合S1结尾的每个图，将其较大的集合放在A中（而较小的集合放在B中），对于数字以S2结尾的每个图，将其较小的集合放在A中（而较大的集合放在B中），在您的示例中，解是S1=[1]和S2=[1]回到关联图，您可以从示例中获得最佳解决方案。