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. 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.

Flow graph

Cederbaum's theorem applies to a particular type of directed graph:  G = (V, E). V is the set of nodes. [math]\displaystyle{ E }[/math] is the a set of directed edges: [math]\displaystyle{ E = (a, b) \in V \times V }[/math] . A positive weight is associated with each edge:  w_ab: E → R⁺ . Two of the nodes must be s and t: [math]\displaystyle{ s \in V }[/math] and [math]\displaystyle{ t \in V }[/math].

Flow

Flow,   f : E → R⁺, is a positive quantity associated with each edge in the graph. Flow is constrained by the weight of the associated edge and by the conservation of flow at each vertex as described here.

Current

Edge pair.

Current is defined as a map for each edge pair to the real numbers,  i_ab : E^p → R. Current maps from the voltage to a range that is determined by the weights of the respective forward and reverse edges. Each edge pair is the tuple consisting of the forward and reverse edges for a given pair of vertices. The current in the forward and reverse directions between a pair of nodes are the additive inverses of one another:  i_ab = −i_ba . Current is conserved at each interior node in the network. The net current at the [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] nodes is non-zero. The net current at the [math]\displaystyle{ s }[/math] node is defined as the input current. For the set of neighbors of the node [math]\displaystyle{ s }[/math], [math]\displaystyle{ N_s }[/math]:

[math]\displaystyle{ I_{in} = \sum_{b \in N_s}i_{sb} }[/math]

Voltage

Voltage is defined as a mapping from the set of edge pairs to real numbers,  v_ab : E^p → R. Voltage is directly analogous to electrical voltage in an electrical network. The voltage in the forward and reverse directions between a pair of nodes are the additive inverses of one another:  v_ab = −v_ba . The input voltage is the sum of the voltages over a set of edges, [math]\displaystyle{ P_{ab} }[/math], that form a path between the [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] nodes.

[math]\displaystyle{ V_{in} = \sum_{(a,b) \in P_{ab}}v_{ab} }[/math]

s–t cut

Minimum s–t cut for directed graph. All edges have equal weights.

An s–t cut is a partition of the graph into two parts each containing one of either [math]\displaystyle{ s }[/math] or [math]\displaystyle{ t }[/math]. Where [math]\displaystyle{ S \cup T = V }[/math], [math]\displaystyle{ \;\; s \in S }[/math], [math]\displaystyle{ \;\; t \in T }[/math], the s–t cut is [math]\displaystyle{ (S, T) }[/math]. The s–t cut set is the set of edges that start in [math]\displaystyle{ S }[/math] and end in [math]\displaystyle{ T }[/math]. The minimum s–t cut is the s–t cut whose cut set has the minimum weight. Formally, the cut set is defined as:

[math]\displaystyle{ X_C = \{ (a, b) \in E \mid a \in S, b \in T \} }[/math]

Electrical network

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 [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] terminals of the graph, respectively. The voltage state of the model becomes binary in the limit as the input voltage difference approaches [math]\displaystyle{ \infty }[/math]. The behavior of the electrical network is defined by Kirchhoff's voltage and current laws. Voltages add to zero around all closed loops and currents add to zero at all nodes.

Resistive element

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.

iv characteristic

[math]\displaystyle{ iv }[/math] characteristic.

The [math]\displaystyle{ iv }[/math] characteristic is the relationship between current and voltage. 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 current range may be inclusive or exclusive of the endpoints. The domain of the voltage is exclusive of the maximum and minimum currents:

 i_ab : R → [−w_ab,w_ba]   or   (−w_ab,w_ba]   or  [−w_ab,w_ba)   or  (−w_ab,w_ba)

 v_ab : (−w_ab,w_ba) → R

Statement of theorem

The limit of the current  I_in between the input terminals of the electrical network as the input voltage, V_in approaches [math]\displaystyle{ \infty }[/math], is equal to the weight of the minimum cut set X_C .

[math]\displaystyle{ \lim_{V_{in} \rightarrow \infty} (I_{in})= \min_{X_C}\sum_{(a,b) \in X_C}w_{ab} . }[/math]

Proof

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:

[math]\displaystyle{ \lim_{V_{in} \rightarrow \infty} (I_{in}) \leq \min_{X_C}\sum_{(a,b) \in X_C}w_{ab} . }[/math]

Claim 2 As the input voltage [math]\displaystyle{ V_{in} }[/math] approaches infinity, there exists at least one cut set [math]\displaystyle{ X'_C }[/math] such that the voltage across the cut set approaches infinity.

[math]\displaystyle{ \exists X'_C \;\; \forall \; (a,b) \in X'_C \;\; \lim_{V_{in} \rightarrow \infty}(v_{ab}) = \infty }[/math]

This implies that:

[math]\displaystyle{ \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}. }[/math]

Given claims 1 and 2 above:

[math]\displaystyle{ \lim_{V_{in} \rightarrow \infty} (I_{in}) = \min_{X_C}\sum_{(a,b) \in X_C}w_{ab} . }[/math]

Related Topics

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.