algorithm - 将图形分成两组

Question

问题来自Code jam .

问题:
有什么方法可以将图形的节点分成两组，使得不能留在同一组中的任何两个节点应该在不同的组中。
这有什么标准算法吗？

当每个组应该有相等的元素时，我应该如何解决这个问题。

Answer 1

首先，可行性问题(是否存在这样的集合/不存在这样的集合)是2-coloring problem ，其中:

G = (V,E)
V = { all nodes } 
E = { (u,v) | u and v are "troubling each other" } 

这个问题通过检查图是否为bi-partite来解决, 并且可以使用 BFS 来完成.

---

How to tackle the problem when each group should have equal element.

首先，我们假设该图是二分图，因此有一些解。

将图拆分为一组连通分量:(S1,S2,S3,...,Sk)。
每个连通分量实际上是一个子图 (Si = Li,Ri) - 其中 Li,Ri 是二分图的两侧(如果忽略 Li 和日)。

创建一个新数组:

arr[i] = |Li| - |Ri|   
where |X| is the cardinality of X (number of elements in the set)

现在，解决此问题与解决 partition problem 相同，这可以在伪多项式时间内完成(这是节点数的多项式)。

分区问题的解决方案将每个 arr[i] 拆分为 A 或 B，这样 sum{ A} 尽可能接近 sum{B}。如果 arr[i] 在 A 中，在您的解决方案中，为 Li 着色“1”，为 Ri与“2”。否则 - 做相反的事情。

解决方案将是O(k*n+m)，其中k是连接组件的数量，n是节点的数量图形，m 是图形中的边数。