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

Question

我正在研究一个问题，其中一个问题是通过创建流网络来基于某些约束来创建考试时间表。

• 一定数量的类(class) C
• 一定天数 D
• 一定数量的房间 R
• 学生 S 与其类(class)的映射

如果学生正在选修 c1 和 c2 类(class)，则这两个考试不能同时举行。

我在根据这些约束创建流网络时遇到了问题。这是我迄今为止尝试建立的网络之一。

黑色节点是源和汇。红色是学生。绿色是类(class)。橙色是天。蓝色是房间。

数字代表流量。

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

Answer 1

这不是流程问题。它实际上是 NP 完全的；您可以将图形着色问题简化为如下:

将图着色实例中图的顶点集作为类(class)集。对于该图中的每条边，比如 u 和 v 之间，创建一个只参加类(class) u 和 v 的学生>。时间段的数量与可用颜色的数量完全相同。

然后一个可行的时间表(没有学生同时参加他的两项考试)将为您的图表着色。

您可能更幸运地为您的问题构建一个整数规划模型。