A simple-cycle traversal vector is a circulation
ProvedLinearOptimization.traversalVector_isCirculation_of_isCyclecirculationscyclesnetwork-flows
Let be a finite directed network with node--arc incidence matrix . For a simple cycle , let be its signed traversal vector: a forward traversal contributes on its arc, a backward traversal contributes , and unused arcs contribute . Then
Thus every simple-cycle traversal vector is a circulation. This is the structural fact that makes cycle vectors reusable as the elementary summands in the flow-decomposition theorem.
Formalization Note A cycle is represented by a nonempty list of directed arc steps with no repeated internal vertex or arc index; the conclusion uses the platform definitions traversalVector and IsCirculation.
Preamble
import Definitions.Def_LinearOptimization_NetworkFlowProblem open Matrix
Formal statement
theorem LinearOptimization.traversalVector_isCirculation_of_isCycle
{n m : ℕ} (arcs : Fin m → Fin n × Fin n) {v : Fin n}
{steps : List (Fin m × Bool)} (hcyc : IsCycle arcs v steps) :
IsCirculation arcs (traversalVector steps) := by
sorrySource
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, §7.2, p. 278 (definition of the simple circulation h^C); used in the proof of Lemma 7.1, p. 298