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.
≈ 3 min read
Cederbaum's maximum flow theorem. encyclopegia.org, snapshot enwiki-001336826237. /a/cederbaum-s-maximum-flow-theorem
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.