§1, Step 3, first bracket, p. 34 — at Step 3 the starred zeros are a maximal independent set and the covered lines a minimal cover
ProvedMunkresAlg.Assignment.step3_maximal_minimalassignment-problemindependent-zerosinvariantline-coverp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix and let be a state reachable by Munkres' algorithm from that is at Step 3, with current matrix , covered rows , covered columns and starred zeros . Then:
- all the zeros of are covered: every has or ;
- each starred zero is covered by precisely one line: for , exactly one of , holds;
- there are exactly as many covered lines as starred zeros: ;
- the starred zeros form a maximal set of independent zeros: is a set of independent zeros of and ;
- the covered lines form a minimal set of lines containing all the zeros: for every containing all the zeros of , .
Here is the maximal number of independent zeros. Steps 1 and 2 thus carry out Step B of Flood's outline, finding a minimal cover and a maximal independent set.
Preamble
import Mathlib import Definitions.Def_MunkresAlg_Assignment_Basic import Definitions.Def_MunkresAlg_Assignment_Algorithm
Formal statement
namespace MunkresAlg.Assignment
/-- §1, Step 3, first bracket, p. 34: at Step 3 all zeros are covered, each starred zero is
covered by exactly one line, there are as many covered lines as starred zeros, the starred zeros
form a maximum set of independent zeros, and the covered lines form a minimum set of lines
containing all the zeros. -/
theorem step3_maximal_minimal {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (s : State n)
(hs : Reachable A s) (hph : s.phase = Phase.step3) :
CoversZeros s.A s.rowCov s.colCov ∧
(∀ p ∈ s.starred, (p.1 ∈ s.rowCov ∧ p.2 ∉ s.colCov) ∨ (p.1 ∉ s.rowCov ∧ p.2 ∈ s.colCov)) ∧
s.rowCov.card + s.colCov.card = s.starred.card ∧
(IsIndepZeros s.A s.starred ∧ s.starred.card = maxIndepZeros s.A) ∧
(∀ R C : Finset (Fin n), CoversZeros s.A R C →
s.rowCov.card + s.colCov.card ≤ R.card + C.card) := by sorry
end MunkresAlg.Assignment
Source
Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957), p. 34, §1, Step 3, first bracket
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.