cutCapacity
def
The total capacity of the edges of the network leaving a vertex set S: the sum over u ∈ S and all v of cap({u,v}), with the terms where v ∈ S set to zero.
Statement
def cutCapacity {V : Type} [Fintype V] [DecidableEq V] (net : CapacitatedNetwork V) (S : Finset V) : ℝ
- Source
- step towards undirected_binary_linear_unicast_advantage
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Built on 1
- CapacitatedNetworkAn undirected capacitated network on a finite vertex set V given by a simple graph G where each edge in G has strictly positive capacity…
- Used by 5
- linear_code_rate_le_cut_cone_boundIf a linear network code over a field F supports the common rate r, then for any finite family of vertex sets cuts and any nonnegative…
- code_transmissions_cross_cut_leIn a causal linear network code on net, the number of transmissions whose endpoints are separated by a vertex set S is at most T *…
- flow_rate_mul_sep_le_cut_capacityIf a fractional multicommodity flow supports the common rate r, then for every vertex set S, r times the number of sessions crossing S is…
- linear_code_supports_rate_cut_boundIf a linear network code over a field F supports the common rate r on net with sessions sess, then for every vertex set S, r times the…
- one_slot_code_rate_le_cut_ratioA one-slot (T = 1) causal linear code over any field satisfies L * (number of sessions separated by S) ≤ (capacity leaving S) for every…
Lean source view module on GitHub
/-- Total capacity leaving the cut S. -/ def cutCapacity {V : Type} [Fintype V] [DecidableEq V] (net : CapacitatedNetwork V) (S : Finset V) : ℝ := ∑ u ∈ S, ∑ v, if v ∈ S then 0 else net.cap s(u, v)