algorithm - 具有中间节点的最大流二分

Question

我正在解决一个问题，即通过创建流网络基于某些约束来创建考试时间表。

• 一定数量的课程 C
• 固定天数 D
• 一组房间R
• 学生 S 到他们的课程的映射

如果学生正在学习 c1 和 c2 课程，这两个考试不能同时举行。

我无法根据这些约束创建流网络。这是迄今为止我尝试建立的网络之一。

黑色节点是源和汇。红色是学生。绿色是课程。橙色是天。蓝色是房间。

数字代表流量。

创建适当的流图后，我知道我会使用 Ford-Fulkerson 算法来找到最大流量。

Answer 1

This isn't a flow problem. It's actually NP-complete; you can reduce the graph colouring problem to it as follows:

Take as the set of courses the vertex set of the graph in your graph colouring instance. For each edge in that graph, say between u and v, create a student who's taking only courses u and v. Have exactly as many time slots as there are colours available.

Then a feasible schedule (where no student has both of his exams at the same time) will be a colouring of your graph.

You might have better luck building an integer programming model of your problem.