Cederbaum's maximum flow theorem
Cederbaum's theorem[1] 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.
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: G = (V, E).
Flow, f : E → R+, is a positive quantity associated with each edge in the graph.
Current is defined as a map for each edge pair to the real numbers, iab : Ep → R. Current maps from the voltage to a range that is determined by the weights of the respective forward and reverse edges.
The current in the forward and reverse directions between a pair of nodes are the additive inverses of one another: iab = −iba .
The voltage in the forward and reverse directions between a pair of nodes are the additive inverses of one another: vab = −vba .
Formally, the cut set is defined as: An electrical network is a model that is derived from a flow graph.
Each resistive element in the electrical network corresponds to an edge pair in the flow graph.
The positive and negative terminals of the electrical network are the nodes corresponding to the
and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.")
The behavior of the electrical network is defined by Kirchhoff's voltage and current laws.
A resistive element in the context of this theorem is a component of the electrical network that corresponds to an edge pair in the flow graph.
The requirements are: (i) Current and voltage are continuous function with respect to one another.
(ii) Current and voltage are non-decreasing functions with respect to one another.
(iii) The range of the current is limited by the weights of the forward and reverse edges corresponding to the resistive element.
The domain of the voltage is exclusive of the maximum and minimum currents: The limit of the current Iin between the input terminals of the electrical network as the input voltage, Vin approaches
, is equal to the weight of the minimum cut set XC .
Claim 1 Current at any resistive element in the electrical network in either direction is always less than or equal to the maximum flow at the corresponding edge in the graph.
Therefore, the maximum current through the electrical network is less than the weight of the minimum cut of the flow graph: Claim 2 As the input voltage
approaches infinity, there exists at least one cut set
This implies that: Given claims 1 and 2 above: The existence and uniqueness of a solution to the equations of an electrical network composed of monotone resistive elements was established by Duffin.
[2] Cederbaum's maximum flow theorem is the basis for the Simcut algorithm.
