Proposition 2.1, p. 152 — CT1 has a solution iff every row and column sum of R is at most p (König)
ProvedTimetabling85.ClassTeacher.prop_2_1edge-coloringkonig-theoremp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1timetabling
Let be an requirement matrix of nonnegative integers and a number of periods. Problem CT1 — find with for all , for all and for all — has a solution if and only if
This is König's edge-colouring theorem for bipartite multigraphs: a bipartite multigraph of maximum degree can be properly edge-coloured with colours iff . In timetabling terms, there is a timetable in periods iff no teacher and no class is involved in more than lectures.
Formalization Note The statement holds for every , including , where both sides say .
Preamble
import Mathlib import Definitions.Def_Timetabling85_ClassTeacher_Problems
Formal statement
namespace Timetabling85.ClassTeacher
/-- Proposition 2.1 (König; de Werra 1985, p. 152): CT1 has a solution iff every column sum and
every row sum of `R` is at most `p`. -/
theorem prop_2_1 {m n : ℕ} (R : Fin m → Fin n → ℕ) (p : ℕ) :
(∃ x : Fin m → Fin n → Fin p → ℕ, IsCT1 R p x) ↔
(∀ j, colSum R j ≤ p) ∧ (∀ i, rowSum R i ≤ p) := by sorry
end Timetabling85.ClassTeacher
Source
de Werra, An introduction to timetabling, Eur. J. Oper. Res. 19 (1985), p. 152, Proposition 2.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.