§3.1, Figure 4, p. 157 — the printed schedule of the Figure 4 example is feasible in 4 periods
ProvedTimetabling85.CourseColoring.figure4_feasiblecourse-schedulingexamplep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1timetabling
Consider the instance of Figure 4: courses with lectures; student 1 takes ; student 2 takes . The schedule printed on the page,
is a feasible course schedule in periods: no two lectures of one course share a period, and no student has two lectures at one period.
This checks the example the paper uses to illustrate the graph model of §3.1.
Formalization Note The instance and the schedule are the definitions figure4 and figure4Schedule, with all indices starting at .
Preamble
import Mathlib import Definitions.Def_Timetabling85_CourseColoring_Figure4
Formal statement
namespace Timetabling85.CourseColoring theorem figure4_feasible : figure4.IsFeasibleSchedule 4 figure4Schedule := by sorry end Timetabling85.CourseColoring
Source
de Werra, An introduction to timetabling, Eur. J. Oper. Res. 19 (1985), p. 157, §3.1, Figure 4 and "The schedule corresponding to the coloring in Figure 4 is: …"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.