algorithm - 将学生分成两组的图算法

Question

我正在努力创建一种有效的算法来确定一组学生是否可以分为两组。

请注意，对于 (X,Y) student X 必须与 student Y 和一些(A,B) student A 不能与 student B 类型的约束。不是每个学生都对他有约束，有的学生有多重约束。

我考虑过一个图，其中每个学生都是一个节点，然后如果学生可以在同一组中，则两个节点通过一条边连接(例如，他们要么有必须在一起和/或不在一起的约束没有他们不能在一起的限制)。但是我不确定我可以应用什么算法来解决(或证明，给定一组约束这是不可能的)，一旦我构建了这个图形表示。

有什么建议吗？谢谢你!

Answer 1

您可以使用以下步骤，然后使用 Bipartite Graph算法。

1. 考虑一个图，其中每个学生都是一个节点，如果学生不属于同一组，则两个节点通过边连接。

2. 如果学生 A 和 B 必须在同一组中，则将 B 连接到 A 连接的每个节点，并将 A 连接到 B 连接的每个节点。

现在你有一个图，你想检查顶点是否可以分成两个不相交的集合，并且同一集合中的两个节点之间没有边。这是二分图，您可以找到有关如何解决此问题的算法。

使用 PeterdeRivaz 评论进行编辑

这个答案更好，因为彼得说你可以改变我的步骤:

1. 考虑一个图，其中每个学生都是一个节点，如果学生不属于同一组，则两个节点通过边连接。

2. 如果学生 A 和 B 必须在同一组，则将 A 和 B 连接到一个假想的学生。