Existence and uniqueness of the tree solution
ProvedLinearOptimization.network_tree_solution_uniquebasic-solutionsnetwork-flowstrees
(Bertsimas & Tsitsiklis, Theorem 7.3, p. 281) Let be a set of arcs that form a tree when their direction is ignored. Then, the system of linear equations , and for all , has a unique solution.
(The book's proof: the matrix of the -columns of can be reordered to lower-triangular form with nonzero diagonal, hence is nonsingular — so the columns of associated with the tree arcs form a basis.)
Preamble
import Definitions.Def_LinearOptimization_TreeSolution open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 7.3 (p. 281).** For a set `T` of arcs forming a tree when direction is ignored (on `n + 1` nodes, so `T` has `n` arcs), the system `Ãf = b̃` together with `f_k = 0` for all `k ∉ T` has a unique solution. -/
Formal statement
theorem LinearOptimization.network_tree_solution_unique {n m : ℕ}
(arcs : Fin m → Fin (n + 1) × Fin (n + 1)) (bsupply : Fin (n + 1) → ℝ)
(hloop : HasNoSelfLoops arcs)
(T : Finset (Fin m)) (hT : IsTreeArcSet arcs T) :
∃! f : Fin m → ℝ,
(truncatedIncidence arcs).mulVec f = truncatedSupply bsupply ∧
∀ k, k ∉ T → f k = 0 := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 7.3, p. 281