Cederbaum's maximum flow theorem

Cederbaum's theorem defines hypothetical analog electrical networks which will automatically produce a solution to the minimum s–t cut problem.

Uses your system voice; voice and rate in settings.

≈ 3 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Cederbaum's theorem defines hypothetical analog electrical networks which will automatically produce a solution to the minimum s–t cut problem. Alternatively, simulation of such a network will also produce a solution to the minimum s–t cut problem. This article gives basic definitions, a statement of the theorem and a proof of the theorem. The presentation in this article closely follows the presentation of the theorem in the original publication.

Definitions

Definitions in this article are consistent in all respects with those given in a discussion of the maximum-flow minimum-cut theorem. Cederbaum's theorem applies to a particular type of directed graph: . V is the set of nodes.

E is the set of directed edges: E = (a, b) \in V \times V . A positive weight is associated with each edge: . Two of the nodes must be s and t: s \in V and t \in V . I_{in} = \sum_{b \in N_s}i_{sb} V_{in} = \sum_{(a,b) \in P_{ab}}v_{ab} An s–t cut is a partition of the graph into two parts each containing one of either s or t . Where S \cup T = V , \;\; s \in S , \;\; t \in T , the s–t cut is (S, T) . The s–t cut set is the set of edges that start in S and end in T . The minimum s–t cut is the s–t cut whose cut set has the minimum weight.

Formally, the cut set is defined as: X_C = \{ (a, b) \in E \mid a \in S, b \in T \}

Statement of theorem

The limit of the current between the input terminals of the electrical network as the input voltage, approaches \infty , is equal to the weight of the minimum cut set . \lim_{V_{in} \rightarrow \infty} (I_{in})= \min_{X_C}\sum_{(a,b) \in X_C}w_{ab} . \exists X'_C \;\; \forall \; (a,b) \in X'_C \;\; \lim_{V_{in} \rightarrow \infty}(v_{ab}) = \infty This implies that: \lim_{V_{in} \rightarrow \infty} (I_{in}) = \sum_{(a,b) \in X'_C}w_{ab} \; \geq \; \min_{X_C}\sum_{(a,b) \in X_C}w_{ab}. Given claims 1 and 2 above: \lim_{V_{in} \rightarrow \infty} (I_{in}) = \min_{X_C}\sum_{(a,b) \in X_C}w_{ab} .

See also

The existence and uniqueness of a solution to the equations of an electrical network composed of monotone resistive elements was established by Duffin.

Application

Cederbaum's maximum flow theorem is the basis for the Simcut algorithm.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1336826237 under CC BY-SA 4.0; modifications have been made.

Words in each sectionDefinitionsDefinitionsDefinitions: 189 words189Statement of theoremStatement of theoremStatement of theorem: 121 words121ApplicationApplicationApplication: 34 words34See alsoSee alsoSee also: 23 words23
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001336826237 · captured 2026-02-05 · ledger · version history

Cite this page as: encyclopegia.org, “Cederbaum's maximum flow theorem”, snapshot enwiki-001336826237. https://encyclopegia.org/a/cederbaum-s-maximum-flow-theorem

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.