A nonzero nonnegative circulation contains a positive directed cycle
ProvedLinearOptimization.positive_directed_cycle_of_circulationcirculationscyclesflow-decompositionnetwork-flows
Let be a finite directed network with no self-loops, and let be a nonzero nonnegative circulation, so for the node--arc incidence matrix . Then there is a simple directed cycle entirely contained in the positive support of :
This cycle-extraction lemma is the combinatorial step used when decomposing a nonnegative circulation into positive multiples of simple circulations.
Formalization Note The cycle is returned as a nonempty list of forward arc traversals; its internal vertices and arc indices are both duplicate-free.
Preamble
import Definitions.Def_LinearOptimization_NetworkFlowProblem open Matrix
Formal statement
theorem LinearOptimization.positive_directed_cycle_of_circulation
{n m : ℕ} (arcs : Fin m → Fin n × Fin n)
(hloop : HasNoSelfLoops arcs) (f : Fin m → ℝ)
(hnn : 0 ≤ f) (hcirc : IsCirculation arcs f) (hne : f ≠ 0) :
∃ (v : Fin n) (steps : List (Fin m × Bool)),
IsCycle arcs v steps ∧
(∀ st ∈ steps, st.2 = true) ∧
∀ st ∈ steps, 0 < f st.1 := by
sorrySource
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, proof of Lemma 7.1, p. 298