将人们分成两个团队，不要分配彼此讨厌的同一个团队

Question

有n个人，我想把他们分成两个小组。但是有些人讨厌彼此，所以不想分配同一个团队。我想要最大化小型团队成员的数量。

例如，有5个人和1-2, 2-3, 3-1, 4-5是互相讨厌的。那么{1,5}，{2,4}赋值是可能的。

和5人1- 2,1 - 3,1 - 4,1 -5是互相讨厌的。那么{2,3}，{4,5}赋值是可能的。

我该如何解决这个问题?

Answer 1

假设你想使用"，那么这个问题基本上就是极大二部子图的优化变体，是NP-Hard的。

极大双部子图问题:

给定图G=(V,E)，求两个集U1,U2 <= V -满足:

1. 对于U1中的每个v,u, (v,u)不在E中(U2也是如此)
2. U1 [intersection] U2 = {}
3. 对于所有遵循规则(1)，(2)的U1,U2, |U1|+|U2| >= |U1'| + |U2'|

在你的情况下，"人民";是顶点，如果一个人不喜欢另一个人，两个人之间就有一条边。
很容易看出，一个问题的最优解也是另一个问题的最优解。

因为这个问题是np完全的，所以没有已知的有效的最佳解决方案，但是一些近似算法确实存在，如果你的人数相当少，你可能可以使用蛮力(指数时间)解决方案。