algorithm - 平均分割断开连接的二部图的顶点

Question

我得到了一个包含许多独立组件的图表。每个组件都是二分的。如何将顶点分配到两组 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}

当图形有许多独立的二分组件时，你如何解决这个问题？

Answer 1

这是Partition Problem , 略有伪装。对于每一个二分分量，取独立集合中元素个数的差(实际上是绝对值)。这就是分割问题的输入。对于您的示例，它将是 [1,1](来自(3-2)和(2-1)。)

现在将解决方案转换回图形。对于每个编号以集合 S1 结尾的图，将其较大的集合放入 A(将较小的集合放入 B)，对于每个编号以 S2 结尾的图，将其较小的集合放入 A在 A 中设置(在 B 中设置较大的值。)在您的示例中，解决方案是 S1=[1] 和 S2=[1]。返回到相关图表，您可以从您的示例中获得最佳解决方案。