Proposition 3.3 — flow across a cut
ProvedCombOpt.Circulation.proposition_3_3graph-theorynetwork-flowsp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be an -flow in a digraph and let be an -cut, so and . Then
where . The net flow across any cut therefore equals the value of the flow.
Differences from the source: none.
Preamble
import Mathlib import Definitions.Def_CombOpt_Circulation_MultiDigraph import Definitions.Def_CombOpt_Circulation_delta import Definitions.Def_CombOpt_Circulation_excess import Definitions.Def_CombOpt_Circulation_IsFlow
Formal statement
namespace CombOpt.Circulation
variable {V E : Type*} [Fintype V] [Fintype E] [DecidableEq V]
/-- **Proposition 3.3**, Cook, Cunningham, Pulleyblank & Schrijver, *Combinatorial Optimization* (Wiley, 1998), p. 40 (PDF p. 49): for any `(r, s)`-cut `δ(R)` and any
`(r, s)`-flow `x`, `x(δ(R)) − x(δ(R̄)) = f_x(s)`.
**Formalization Note** `δ(R)` is an `(r, s)`-cut when `r ∈ R`, `s ∉ R`; `x(A)` is `∑ e ∈ A, x e`. -/
theorem proposition_3_3 (G : MultiDigraph V E) {r s : V} {R : Finset V} (hr : r ∈ R) (hs : s ∉ R)
{x : E → ℝ} (hx : IsFlow G r s x) :
∑ e ∈ delta G R, x e - ∑ e ∈ delta G Rᶜ, x e = excess G x s := by sorry
end CombOpt.Circulation
Source
Cook, Cunningham, Pulleyblank & Schrijver, Combinatorial Optimization (Wiley, 1998), Proposition 3.3, p. 40
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.