把人分成两个小组，不要把彼此讨厌的人分成同一个小组

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 --使得：

对于U1中的每个集合，(v,u)不在E中(同样地，对于遵循规则(1)、(2)、|U1|+|U2| >= |U1'| + |U2'|的所有其他集合，U1中的(v,u)不在E中

在您的例子中，" people“是顶点，如果一个人不喜欢另一个人，那么两个人之间就会有一条边。

很容易看出，一个问题的最优解也是另一个问题的最优解。

由于问题是NP完全的，因此没有已知的有效最优解，但是确实存在一些近似算法，如果您的人数相当少，则可以使用蛮力(指数时间)解决方案。