NOIP 提高 2016 第一轮 第 22 题：某中学在安排期末考试时发现，有7个学生要参加7门课程的考试，下表列

题目

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

答案

3

题解

考点定位

本题考「图着色最小色数」,对应大纲 4.3.4 图着色（难度【5】）。

解题过程

7 学生 7 考试的二部冲突表：考试时间安排 = 冲突图着色，最少时段 = 图的色数。按原卷表建立考试冲突图（学生连其参加的考试——考试为点、共同学生连边），求色数 = 3。

答案：3。

易错提醒

① 建模：考试为点、有公共学生的考试连边，色数即最少时段；② 小图手工着色验证下界（找 K₃）与上界（给出 3 色方案）。