考试时间编排问题 ·问题：排考试时间，一方面要总时间尽可能短（假设教室没问题）， 一方面一个同学所选的任意两门课不能同时间。 ·图模型：每门课程对应一个顶点。任意两点相邻当且仅当对应的两门 课程有相同的选课人。 ·解：用不同颜色给顶点着色。相邻的点不能同颜色。则最少着色数即 至少需要的考试时间段数（可以将颜色相同的点所对应的课程安排在 同一时间)。考试时间编排问题 • 问题：排考试时间，一方面要总时间尽可能短(假设教室没问题)，另 一方面一个同学所选的任意两门课不能同时间。 • 图模型：每门课程对应一个顶点。任意两点相邻当且仅当对应的两门 课程有相同的选课人。 • 解：用不同颜色给顶点着色。相邻的点不能同颜色。则最少着色数即 至少需要的考试时间段数(可以将颜色相同的点所对应的课程安排在 同一时间)