Necessary cut conditions for feasible network demands
ProvedCombOpt.Circulation.solution38_implies_Gale_conditionscombinatorial-optimizationgraph-algorithmsnetwork-flows
Let be a finite directed multigraph, with nonnegative finite capacity on each arc and node demand . Write for the net inflow at . If an arc assignment realizes all demands and respects the capacities, so that for every and , then
\sum_{v\in V} b_v=0,\qquad b(A):=\sum_{v\in A}b_v\le u(\delta(ar A)):=\sum_{e\in\delta(ar A)}u_e\quad ext{for every }A\subseteq V.Here \delta(ar A) is the set of arcs entering . These balance and cut-capacity inequalities are the necessary half of Gale’s criterion for feasible network demands.
Preamble
import Mathlib import Definitions.Def_CombOpt_Circulation_MultiDigraph import Definitions.Def_CombOpt_Circulation_delta import Definitions.Def_CombOpt_Circulation_IsSolution38 import Definitions.Def_CombOpt_Circulation_excess
Formal statement
namespace CombOpt.Circulation
variable {V E : Type*} [Fintype V] [Fintype E] [DecidableEq V]
theorem solution38_implies_Gale_conditions (G : MultiDigraph V E) (u : E → ℝ)
(b : V → ℝ) (x : E → ℝ) (hx : IsSolution38 G u b x) :
(∑ v, b v = 0) ∧
∀ A : Finset V, ∑ v ∈ A, b v ≤ ∑ e ∈ delta G Aᶜ, u e := by sorry
end CombOpt.Circulation
Source
W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver, Combinatorial Optimization (Wiley, 1998), §3.3, Theorem 3.15 and flow system (3.8), pp. 54–55; this is the necessity direction.