Lemma 7 — if ψ is a tour, G_ψ* is connected
ProvedGilmoreGomoryTSP.Bottleneck.lemma_7_Gstar_connectedgraph-connectivityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1traveling-salesman
Let be a permutation of the jobs and let be a tour. Then the graph — all arcs of together with every arc for which (22a) holds for some or (22b) holds for some — is connected.
Consequently the added arcs of contain a spanning tree of ; this is how a tour is compared with spanning trees of .
Formalization Note The ranking property of is not used and not assumed; the statement is for an arbitrary permutation . A tour is a permutation with for every nonempty proper subset .
Preamble
import Mathlib import Definitions.Def_GilmoreGomoryTSP_Bottleneck_Model
Formal statement
namespace GilmoreGomoryTSP.Bottleneck
theorem lemma_7_Gstar_connected {n : ℕ} (φ ψ : Equiv.Perm (Fin (n + 1)))
(hψ : GilmoreGomoryTSP.MinCost.IsTour ψ) : (Gstar φ ψ).Connected := by sorry
end GilmoreGomoryTSP.Bottleneck
Source
Gilmore and Gomory, Sequencing a one state-variable machine, Oper. Res. 12 (1964), p. 668, Lemma 7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.