§3.1, p. 157 — a feasible course schedule in p periods is exactly a node coloring of the lecture graph with p colors
ProvedTimetabling85.CourseColoring.schedule_iff_coloringLet a course scheduling instance be given: courses with their lectures , and students each taking a set of courses. Let be its lecture graph: one node per lecture, two lecture-nodes of the same course adjacent, and two lecture-nodes of distinct courses , adjacent whenever some student takes both courses. Let .
Then an assignment of periods to lectures is a feasible course schedule (no two lectures of a course at one period, and no student required to take two lectures at one period) if and only if is a node colouring of with colours:
In particular
This is the basic graph model of course scheduling, on which the treatment of unavailabilities and preassignments (Proposition 3.1) builds.
Formalization Note The schedule and the colouring are the same function Lecture → Fin p; the first conjunct says that the feasible schedules are exactly the underlying functions of the proper colourings of lectureGraph, the second is the existence form with SimpleGraph.Colorable.
import Mathlib import Definitions.Def_Timetabling85_CourseColoring_CSUP
namespace Timetabling85.CourseColoring
theorem schedule_iff_coloring {q r : ℕ} (I : CourseInstance q r) (p : ℕ) :
(∀ s : I.Lecture → Fin p,
I.IsFeasibleSchedule p s ↔ ∃ c : I.lectureGraph.Coloring (Fin p), ⇑c = s) ∧
((∃ s : I.Lecture → Fin p, I.IsFeasibleSchedule p s) ↔ I.lectureGraph.Colorable p) := by sorry
end Timetabling85.CourseColoring
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.