将学生分为两组的图算法

Question

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

请注意,(X,Y)学生X必须与学生一起提供Y一些类型的约束,以及(A,B)学生A不能与学生一起使用的类型约束B.并非每个学生都对他有约束,有些学生有多种限制.

我认为是一个图形,其中每个学生都是一个节点,然后两个节点通过边连接,如果学生可以在同一个组(例如,它们要么有,他们必须要装配在一起和/或不具有约束约束他们不能在一起).但是,一旦我构造了这个图形表示,我不确定我可以应用什么算法来解决(或证明,给定一组约束这是不可能的).

任何建议表示赞赏？谢谢!

Answer 1

您可以使用以下步骤,然后使用Bipartite Graph算法.

1. 考虑一个图表,其中每个学生都是一个节点,如果学生不能在同一个组中,则两个节点通过边连接.

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

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

编辑PeterdeRivaz评论

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

1. 考虑一个图表,其中每个学生都是一个节点,如果学生不能在同一个组中,则两个节点通过边连接.

2. 如果学生A和B必须在同一组,则将A和B连接到想象中的学生.