组合数学 | BETTER CALL ME

Modeling and Analysis of Course Scheduling Problem
Based on Combinatorial Mathematics

Solving practical problems using combinatorial mathematics

qzp¹

¹XiDian University, Xi'an, China, 710126

Email: xxxxxxxxx@stu.xidian.edu.cn

Abstract:
The course scheduling problem is a typical NP-complete combinatorial problem in educational management. In this paper, we model the course scheduling problem by using graph theory and graph coloring from combinatorial mathematics. Courses are abstracted as vertices and conflicts as edges, so that assigning time slots to courses is transformed into a vertex coloring problem. We analyze a greedy coloring algorithm and a recursive backtracking method, and conduct small-scale simulation experiments. The results show that the proposed combinatorial model can generate conflict-free timetables while keeping the number of time slots relatively small.

Keywords: course scheduling problem; combinatorial mathematics; graph coloring; greedy algorithm; recursive method

基于组合数学的课程排课问题建模与分析

使用组合数学原理解决实际问题

qzp¹

¹西安电子科技大学，陕西西安，中国，710126

Email: xxxxxxxxx@stu.xidian.edu.cn

摘要：
课程排课问题是教育管理中典型的 NP 完全组合问题。本文利用组合数学中的图论与图着色原理，对课程排课问题进行了建模与分析。将课程抽象为图的顶点，将“不能同时开课”的约束抽象为图的边，从而把“为课程安排时间槽”的过程转化为图的顶点着色问题。我们分析了基于贪心策略的图着色算法和基于递归回溯的搜索算法，并通过小规模模拟实验进行了验证。实验结果表明，所建立的组合数学模型能够在保证无冲突的前提下给出合理的排课方案，并尽量减少所需的时间槽数量。

关键词： 排课问题；组合数学；图着色；贪心算法；递归方法

1 引言

在高校和中学的教务管理工作中，课程排课是每学期必不可少的一项基础任务。排课的目标是在有限的时间槽内，为多门课程安排合理的上课时间，同时满足教师、教室和学生等多方面的约束。如果一门课程的任课教师在同一时间还要讲授另一门课，或者同一批学生在同一时间需要上两门不同的课，就会产生排课冲突，必须被避免。

从组合数学的角度看，排课问题属于典型的组合优化问题。简化后的课程时间表安排问题已经被证明是 NP 完全的，这意味着想在大规模实例中精确求得最优方案，在计算上非常困难。因此，如何在清晰的数学模型下构造“足够好”的排课方案，成为一个具有理论价值和现实意义的研究方向。

图论和图着色是组合数学中的经典内容。当我们把“课程”看成顶点，把“存在冲突关系的两门课程”看成一条边时，排课问题就可以自然地转化为图着色问题：为每个顶点指定一种“颜色”，使得所有相邻顶点的颜色都不相同；而颜色的种类数量就对应于排课中所需的时间槽个数。通过这种方式，我们可以利用大量已有的图论与着色算法，对排课问题进行分析与求解。

本文将以一个小型课程集合为例，使用组合数学中的图论工具，给出课程排课问题的一种建模方式，并分析两类典型算法：一类是简单高效的贪心着色算法，另一类是可以找到最优解的递归回溯算法。通过理论推导和计算机模拟，我们尝试说明图着色方法在排课问题中的可行性和局限性。

2 使用图着色方法对排课问题建模与分析

2.1 对问题的抽象

考虑一个学期内有门课程，记为

学校可以提供个不同的时间槽（如“周一第 1–2 节”“周一第 3–4 节”等），记为

如果暂不考虑任何冲突约束，那么为门课程安排时间槽的方式共有

种，每门课可以独立选择任意一个时间槽。这是一个典型的“从个盒子中为个球独立选择”的计数问题，方案数量呈指数级增长。

但是，在实际排课中，会存在如下典型约束：

同一教师主讲的多门课程不能在同一时间开课；
有共同选课学生的两门课程不能在同一时间开课；
同一间教室在同一时间只能安排一门课程。

这些约束迫使我们剔除大量不合法的方案。随着课程数量、教师数量与学生数量的增加，直接在个方案空间中做穷举搜索几乎是不可能完成的任务。

为使问题更加清晰，我们引入图论的描述。对每一门课程，用一个顶点表示；如果两门课程与存在上述任意一种冲突关系，则在顶点与之间连一条无向边。这样，我们获得了一个无向图

其中表示课程集合，表示冲突集合。

接下来，我们将“为每门课程分配时间槽”的问题转化为“对图的顶点进行着色”的问题。设一个映射

其中表示课程被安排的时间槽编号。排课无冲突的条件就等价于：对任意一条边，都有

这正是图着色的基本要求：相邻顶点颜色不同。

在图论中，一个图在满足上述条件下所需的最少颜色数被称为该图的色数，记作。在排课问题的语境下，就对应于在不产生冲突的前提下所需的最少时间槽数量。

2.2 图着色模型与组合性质

在上述模型下，可以利用一些基本的组合性质来估计排课问题的难度。

首先，如果图中存在一个大小为的完全子图（团），即有个顶点两两之间都有边，则至少需要种不同的颜色才能对这个顶点进行合法着色。因此，

其中是图中最大团的大小。这给出了排课所需最少时间槽数量的一个下界。

另一方面，图的最大度数也为色数提供了一个上界。经典结论表明，对任意简单图，有

直观理解为：在最坏情况下，为每个顶点着色时，最多会遇到个相邻顶点已经使用了不同的颜色，再多准备一个新颜色即可保证可着色。

将这些结论转回排课问题：

冲突最严重的一组课程（完全子图）决定了时间槽的最低需求；
每门课程的冲突数目（度数）决定了时间槽数量的上限；
在这两个界之间，通过合适的算法可以寻找实际排课中可用的时间槽数。

然而，一般图的精确色数计算是一个 NP 困难问题。因此，我们通常采用启发式算法来获得接近最优的着色方案，例如下面将要介绍的贪心着色方法。

2.3 贪心着色算法与递归算法

（1）贪心着色算法

贪心着色算法的基本思想是：按某种顺序依次为顶点着色，每次选取当前可用的最小颜色编号，只要不与已经着色的相邻顶点冲突即可。

具体步骤可以描述如下：

按顶点的度数从大到小对课程排序（冲突多的课程优先着色）；
依次取出每一个顶点，查看其所有已着色邻接顶点的颜色集合；
从颜色集合中选取一个最小的、未被邻居使用的颜色赋给；
如果所有已有颜色都不可用，则新增加一种颜色。

该算法的时间复杂度在稠密图中大致为。虽然在某些特殊图上贪心算法可能使用到种颜色，但在许多实际场景中，它给出的解往往较为接近最优，并且具有实现简单、计算速度快等优点，非常适合作为排课问题的一个实用求解方法。

（2）递归回溯算法

与贪心算法相比，递归回溯算法是一种“穷举 + 剪枝”的精确求解方法。它通过深度优先搜索的方式，尝试为每一个顶点分配颜色；一旦发现当前选择导致后续无法着色，便回溯到上一步重新选择。

简单描述如下：

选定一个顶点顺序；
对于第个顶点，依次尝试颜色；
如果某个颜色与已着色邻接点都不冲突，则递归处理；
若所有颜色都无法用于，则回溯到改变其颜色选择；
记录所有成功着色的方案，并取颜色种类最少的方案作为最优解。

递归回溯在最坏情况下需要考察所有可能的颜色分配组合，时间复杂度呈指数增长，因此只适用于课程数量较少的排课实例。不过，它可以很好地用于验证贪心算法的解是否已经达到最优，或者在小规模场景中获得严格的最优排课方案。

3 小规模排课实例的分析

为了直观展示上述模型和算法的运行效果，我们构造一个包含 6 门课程的小规模排课实例。设课程集合为

假设存在如下冲突关系：

四门课程两两冲突，形成一个完全子图；
与、冲突；
与、冲突。

据此可以画出课程冲突图。由于构成一个 4 阶完全子图，可知色数满足

也就是说无论如何都至少需要 4 个时间槽。

对该冲突图应用贪心着色算法（按度数从大到小排序），我们得到一种可行着色方案：

课程使用颜色 1；
课程使用颜色 2；
课程使用颜色 3；
课程使用颜色 4；
课程与无直接冲突，可以与共用颜色 3；
课程与、无直接冲突，可以与共用颜色 1。

在该方案中总共使用了 4 种颜色（时间槽），并且每一条边连接的两门课程都使用了不同的颜色，因此这是一个合法的无冲突排课方案。

进一步使用递归回溯算法对该实例进行搜索，结果表明不存在仅用 3 种颜色的合法着色。因而该实例的色数正是。这说明贪心算法在该实例中恰好达到了最优颜色数，验证了在某些实际结构下，简单的贪心策略也可以得到最优解。

该例从组合角度说明：

冲突子图的结构（如完全子图）直接影响所需时间槽的下界；
最大度数与顶点排序策略会影响贪心算法的着色结果；
在小规模场景中，可以借助回溯搜索验证着色方案的最优性。

4 计算机模拟验证

为了进一步验证图着色模型在排课问题中的适用性，我们可以编写简单程序，对更大规模的随机排课实例进行模拟。基本思路如下：

随机生成门课程，以及课程之间的冲突关系（例如，每对课程以一定概率产生冲突）；
将生成的冲突关系转化为图；
对该图依次应用贪心着色算法与递归回溯算法：
- 贪心算法用于快速得到一个可行着色方案；
- 在课程数量较少时，用回溯算法验证贪心解的最优性；
记录每次试验中使用的颜色数量、冲突检测情况以及运行时间。

在多次随机模拟中可以观察到：

当图较稀疏时（每门课程的冲突较少），贪心算法往往能够得到接近色数的解，有时甚至就是最优解；
当图较稠密时，所需的时间槽数量接近最大团的大小，而贪心算法在合理排序下仍然可以得到可接受的排课方案；
在课程数量不大时（如几十门课），回溯算法可以用来精确计算色数，以评估贪心算法的性能；当课程数进一步增大时，回溯的计算时间迅速增长，体现了问题的 NP 困难性。

这些模拟结果从数值上支持了前文的理论分析：排课问题可以通过图着色模型清晰地刻画，其可行解可以借助组合算法有效地构造，但想要在大规模实例中求得严格最优解在计算上往往是不现实的。

5 总结

本文从组合数学与图论的角度出发，将课程排课问题抽象为无向图的顶点着色问题。通过构造课程冲突图，我们将“课程–时间槽分配”的任务转化为对顶点进行合法着色，并借助色数来衡量在无冲突前提下所需的最少时间槽数量。

在算法层面，本文分析了两类典型方法：

基于“度数优先”的贪心着色算法，能够在多项式时间内快速给出一个可行排课方案；
基于递归回溯的精确搜索算法，可以在小规模实例中找到使用颜色最少的最优方案。

通过一个包含 6 门课程的小型排课实例，我们展示了模型的构建过程以及两种算法的应用效果。实验结果表明，图着色方法可以自然地刻画排课中的冲突关系，并在保证无冲突的前提下给出合理的课程时间安排。在示例中，贪心算法的着色数等于理论下界，说明在某些结构的冲突图上，简单的启发式算法也能够取得较理想的结果。

5.2 不足之处

需要指出的是，本文的模型与实验仍然存在一些局限性：

首先，模型只考虑了“不能同时上课”的硬约束，而实际排课中还存在大量软约束，例如教师的时间偏好、教室容量和设备需求、课程之间的先修关系等。这些约束往往不能简单用一条边来表示，需要更复杂的结构（如超图、多层图或带权图）才能较好地刻画。

其次，本文主要分析了两种基础算法。在课程数量较多、冲突关系复杂的实际场景中，贪心算法可能产生远离最优的解，而递归回溯算法的时间代价又难以接受。如何设计更高效的启发式或元启发式算法（如遗传算法、模拟退火、禁忌搜索等），以及如何结合整数规划、约束规划等工具，是进一步优化排课方案的方向。

再次，本文仅通过一个小规模的合成例子进行验证，尚未在真实学校的完整排课数据上进行实验。未来可以收集真实数据，对比不同算法在实践中的表现，从时间复杂度、冲突数量、资源均衡性等多个维度进行综合评价。

总的来说，组合数学和图论为课程排课问题提供了一种清晰、统一的描述框架。随着计算能力的提升和优化算法的发展，将图着色模型与更丰富的约束条件、智能算法相结合，有望构建出更为实用、智能的自动排课系统，从而减轻教务人员的工作负担，提高课程安排的合理性与公平性。

References 参考文献

[1] Even S., Itai A., Shamir A. On the Complexity of Timetable and Multicommodity Flow Problems[J]. SIAM Journal on Computing, 1976, 5(4): 691–703.

[2] Welsh D. J. A., Powell M. B. An Upper Bound for the Chromatic Number of a Graph and Its Application to Timetabling Problems[J]. The Computer Journal, 1967, 10(1): 85–86.

[3] Bondy J. A., Murty U. S. R. Graph Theory with Applications[M]. Macmillan, 1976.

[4] 刘树棠. 图论及其应用[M]. 北京: 高等教育出版社, 2002.

[5] Babaei H., Karimpour J., Hadidi A. A survey of approaches for university course timetabling problem[J]. Computers & Industrial Engineering, 2015, 86: 43–59.