等分断开二分图的顶点
我得到了一个包含许多独立组件的图表。每个组件都是二分的。如何将顶点分配到两个集合 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}
当图形有很多时，您如何解决这个问题单独的二分组件 ?
I'm given a graph with many seperate components. Each component is bipartite. How do I distribute the vertices into two sets A and B such that the difference between the two sets is minimal ?
Example:
1: 1 -> 2 ->3 -> 4 -> 5
2: 6 -> 7 -> 8
The best solution is
A = {1, 3, 5, 7}
B = {2, 4 ,6, 8}
The other (non-optimal) solution is
A = {1, 3, 5, 6, 8}
B = {2, 4, 7}
How do you solve this when the graph has many seperate bipartite components ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这是稍微伪装的分区问题。对于每个二分分量，取独立集合中元素数量的差（实际上，它是绝对值）。这是划分问题的输入。对于您的示例，它将是 [1,1] （来自 (3-2) 和 (2-1)。）
现在将解决方案转换回图形。对于每个编号以集合 S1 结尾的图，将其较大的集合放入
A（将较小的放入B），对于每个编号以 S2 结尾的图，将其较小的集合放入在A中设置（在B中设置较大值。）在您的示例中，解决方案是 S1=[1] 和 S2=[1]。返回到相关图表，您可以从示例中获得最佳解决方案。It's the Partition Problem, slightly disguised. For every bipartite component, take the difference of the numbers of elements in the independent sets (actually, it's absolute value.) This is the input to the partition problem. For your example it would be [1,1] (from (3-2) and (2-1).)
Now for converting the solution back to graphs. For every graph whose number ended in set S1, put its bigger set in
A(and the smaller inB), for every graphs whose number ended in S2, put its smaller set inA(and the larger inB.) In your example, the solution is S1=[1] and S2=[1]. Going back to the associated graphs you get the optimal solution from your example.这是划分问题的一种变体，是 NP 完全问题。
对于每个组件，找到两侧的顶点数，例如 [m,n]，然后您必须决定是否将 m 放入池 A 或池 B 中，以便池 A 中的项总和与池中的项总和之间的差异池 B 最小。
现有的技术可以通过动态规划以及 IPP 的变体来解决此类问题。但对于大量的组件，你注定会因为 NP 完整性而注定失败。
This is a variation of partition problem, which is NP complete.
For each component find the number of vertices on either side, say [m,n] and then you have to decide whether to put m in pool A or pool B, such that the difference between the summation of terms in pool A and that in pool B is minimum.
There are existing techniques for solving this sort of problem by dynamic programming and also variations of IPP. But with a large number of components you are doomed by NP completeness alone.