§1, Step 2, first bracket, p. 34 — the alternating sequence Z_0, …, Z_2k exists, is unique, and has distinct elements
ProvedMunkresAlg.Assignment.step2_sequencealternating-sequenceassignment-probleminvariantp2o-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 2 with the primed zero . Call a list a Step 2 sequence if it starts at , each is a starred zero in the column of , each is a primed zero in the row of , and has no starred zero in its column. Then:
- a Step 2 sequence exists (the construction never fails and the sequence stops);
- any two Step 2 sequences are equal (the sequence is uniquely specified);
- the elements of a Step 2 sequence are distinct;
- is a primed zero, it is non-covered, and it is the only non-covered primed zero.
These facts make Step 2 well defined; part 1 is what rules out the algorithm getting stuck at Step 2.
Preamble
import Mathlib import Definitions.Def_MunkresAlg_Assignment_Basic import Definitions.Def_MunkresAlg_Assignment_Algorithm
Formal statement
namespace MunkresAlg.Assignment
/-- §1, Step 2, p. 34: at Step 2 the alternating sequence `Z₀, Z₁, …, Z₂ₖ` exists (it stops),
it is uniquely specified, its elements are distinct, and `Z₀` is the only non-covered primed
zero. -/
theorem step2_sequence {n : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (s : State n)
(z₀ : Fin n × Fin n) (hs : Reachable A s) (hph : s.phase = Phase.step2 z₀) :
(∃ zs, IsStep2Seq s z₀ zs) ∧
(∀ zs zs', IsStep2Seq s z₀ zs → IsStep2Seq s z₀ zs' → zs = zs') ∧
(∀ zs, IsStep2Seq s z₀ zs → zs.Nodup) ∧
(z₀ ∈ s.primed ∧ NonCovered s z₀ ∧ ∀ p ∈ s.primed, NonCovered s p → p = z₀) := by sorry
end MunkresAlg.Assignment
Source
Munkres, Algorithms for the assignment and transportation problems, J. SIAM 5 (1957), p. 34, §1, Step 2, first bracket (and '[There is only one.]')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.