NOIP 提高组初赛 · NOIP 2016 提高组初赛试题 第 22 题

某中学在安排期末考试时发现，有 $7$ 个学生要参加 $7$ 门课程的考试，下表列 出了哪些学生参加哪些考试（用√表示要参加相应的考试）。 最少要安排_________个不同的考试时间段才能避免冲突？ 

这题表面是填表，本质是图论里的色数问题。拿到表先别急着数，把每门课当顶点，有共同学生的课连边，然后看能不能用 2 种颜色把相邻顶点染开——发现不行，必须 3 种，答案就是 3。

很多学生会直接看表里打勾最多的那门课，以为它最难排，就填 4 或 5；或者只盯着某几门课看，忽略了跨行的冲突，误以为 2 个时段够。还有人会误把‘同一学生参加的多门课’当成独立时间段，忘了只要两门课没有共同学生就能挤进同一个时段。最容易错的是没意识到图中存在三角形结构，导致低估色数。

考点概念：图着色（排课问题）

这道题考查的是图论中的色数概念。把每门考试看作图的一个顶点，如果两门考试有同一个学生参加（即表中同一行出现两个√），就在它们之间连一条边。这样，所有考试就构成了一个图。

题目问“最少要安排多少个不同的考试时间段”，其实就是问：能不能把图中的顶点分成最少的几组，使得每一组里的顶点之间都没有边相连？这在图论里叫图的色数，也就是给图着最少数量的颜色，让相邻顶点颜色不同。

命题视角：为什么考这个？

命题人喜欢用这种“排课表”的生活化场景来考抽象的图论概念，因为表格里√的位置天然就是边的存在与否。学生如果只会看表，很容易陷入局部观察，比如只关注某门课冲突多，或者只盯着某几门课看，而忽略全局结构。真正的难点在于识别出图中是否存在三角形（三个顶点两两相连）——一旦有三角形，色数至少是 3；如果还能找到更大的团（比如 K4），色数就会更高。