Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 20:02, 2 December 2014

Revision as of 21:57, 2 December 2014

Line 16:

{{main|Flow network}}

Consider a flow network {{nowrap|''<math>G'' = (''V'', ''E'')}}</math> with a pair of distinct vertices ''<math>s''</math> and ''<math>t''</math> designated as the source and the sink, respectively. ForThe each edge {{nowrap|<math>c(''u'', ''v'') ∈\ge ''E''}},0</math> {{nowrap|''c''relation denotes the capacity of each edge <math>(''u'', ''v'') ≥\in 0}}E</math>. denotesIf its capacity; if {{nowrap|<math>(''u'', ''v'') ∉\notin ''E''}}</math>, then we assume that {{nowrap|''<math>c''(''u'', ''v'') {{=}} 0}}</math>. A flow on ''<math>G''</math> is a function {{nowrap[[real number|''real]] [[function (mathematics)|function]] <math>\ f'': ''V'' ×\times ''V'' →\rightarrow '''\mathbb{R'''}}</math> satisfying the following conditions:

:{|

:;Capacity constraints

| '''Capacity constraints''': || <math>\ f(u,v) \le c(u,v), \quad \forall u, v \in V</math>

::{{nowrap|''f''(''u'', ''v'') ≤ ''c''(''u'', ''v'')&emsp;∀''u'', ''v'' ∈ ''V''}}

|-

:;Skew symmetry

::{{nowrap| ''f'Skew symmetry'('': || <math>\ f(u'', ''v'') {{=}} −''- f''(''v'', ''u'')&emsp;∀'', \quad \forall u'', ''v'' ∈\in ''V''}}</math>

|-

:;Flow conservation

| '''Flow conservation''': || <math>\ \sum_{v \in V} f(u,v) = 0, \quad \forall u \in V - \{s,t\}</math>

::{{nowrap|∑_{''v''&#x200a;∈&#x200a;''V''} ''f''(''v'', ''u'') {{=}} 0&emsp;∀''u'' ∈ ''V'' \ {''s'', ''t''}}}

|}

The push–relabel algorithm introduces the concept of ''preflows''. A preflow is a function with a definition almost identical to that of a flow except that it relaxes the flow conservation condition. Instead of requiring strict flow balance at vertices other than ''s'' and ''t'', it allows them to carry positive excesses. This means that in a preflow the total flow into a vertex can exceed the flow out of the vertex. Put symbolically:

:{|

:;Nonnegative excesses:

| '''Non-Negative constraint''': || <math>\ \sum\limits_{u \in V} f(u, v) \geq 0, \quad \forall v \in V - \{s\} </math>

::{{nowrap|''e''(''u'') {{=}} ∑_{''v''&#x200a;∈&#x200a;''V''} ''f''(''v'', ''u'') ≥ 0&emsp;∀''u'' ∈ ''V'' \ {''s''}}}

|-

| '''Flow Excess''': || <math> e(v) =

\begin{cases}

\sum\limits_{u \in V} f(u, v), \quad \forall v \in V - \{s\} \\

\infty, \quad v = s

\end{cases} </math>

|}

{{nowrap|''e''(''s'')}} is assumed to be infinite. A vertex ''u''<math>v</math> is called ''active'' if {{nowrap|''<math>e''(''u''v) > 0</math> for <math>v \in V - \{s,t\}}</math>.

For each {{nowrap|<math>(''u'', ''v'') ∈\in ''V'' ×\times ''V''}}</math>, denote its ''residual capacity'' by {{nowrap|''c<submath>f</sub>''c_f(''u'', ''v'') {{=}} ''c''(''u'', ''v'') −- ''f''(''u'', ''v'')}}</math>. The residual network of ''<math>G''</math> with respect to a preflow ''<math>f''</math> is defined as {{nowrap|''G<submath>f</sub>''G_f(''V'', ''E_{fE_f)</submath>'')}} where {{nowrap|''Ethe residual edges are defined as <submath>f}''E_f {{=}} \{ (''u'', ''v'') {{!}}| ''u'', ''v'' ∈\in ''V'' ∧\and ''c_f''c_f(''u'', ''v'') > 0 \}}}</math>. If there is no path from any active vertex to ''t'' in {{nowrap|''G<submath>fG_f</submath>''}}, thethen preflow is called ''maximum''. In a maximum preflow, {{nowrap|''<math>e''(''t'')}}</math> is equal to the value of a maximum flow; if ''<math>T''</math> is the set of vertices from which ''t'' is reachable in {{nowrap|''G<submath>fG_f</submath>''}}, and {{nowrap|''<math>S'' {{=}} ''V'' \backslash ''T''}}</math>, then {{nowrap|<math>(''S'', ''T'')}}</math> is a [[Max-flow min-cut theorem|minimum ''s''-''t'' cut]].

The push–relabel algorithm uses a nonnegative integer ''valid labeling'' function which makes use of ''distance labels'', or ''heights'', ofon vertices to determine which vertex pair should be selected for the verticespush operation. This labeling function is denoted by {{nowrap|''<math>h''(''u''v)}}., Forv each\in vertexV</math>. {{nowrap|''u''This ∈function ''V''must \satisfy {''s'',the ''t''}}},following {{nowrap|''h''(''u'')}}conditions isin aorder nonnegativeto integerbe considered satisfyingvalid:

:{|

:;Valid labeling

::{{nowrap| ''h'Valid labeling'('': || <math>h(u'') ≤\le ''h''(''v'') + 1&emsp;∀, \quad \forall (''u'', ''v'') ∈\in ''E<sub>fE_f</submath>''}}

|-

| '''Source condition''': || <math>h(s) = |V|</math>

|-

| '''Sink conservation''': || <math>h(t) = 0</math>

|}

TheIn heightsthe algorithm, the height values of ''s'' and ''t'' are fixed at {{nowrap|{{!}}''V''{{!}}}} and 0, respectively. {{nowrap|''<math>h''(''u'')}}</math> is a lower bound of the unweighted distance from ''u'' to ''t'' in {{nowrap|''G<submath>fG_f</submath>''}} if ''t'' is reachable from ''u''. If ''u'' has been disconnected from ''t'', then {{nowrap|(''<math>h''(''u'') −- {{!}}''|V''{{!}})}}|</math> is a lower bound of the unweighted distance from ''u'' to ''s''. As a result, if a valid height function exists, there are no ''s''-''t'' paths in {{nowrap|''G<submath>fG_f</submath>''}} because no such paths can be longer than {{nowrap<math>|({{!}}''V''{{!}}| −- 1)}}</math>.

An edge {{nowrap|<math>(''u'', ''v'') ∈\in ''E_{fE_f</submath>''}} is called ''admissible'' if {{nowrap|''<math>h''(''u'') {{=}} ''h''(''v'') + 1}}</math>. The network {{nowrap|''G̃<submath>f}''\tilde{G}_f (''V'', ''Ẽ_{f\tilde{E}_f)</submath>'')}} wherewhen {{nowrap|''Ẽ<submath>f}'' \tilde{{=}E}_f = \{ (''u'', ''v'') {{!}}| (''u'', ''v'') ∈\in ''E_f''E_f ∧\and ''h''(''u'') {{=}} ''h''(''v'') + 1 \}}}</math> is called the ''admissible network''. The admissible network is acyclic.

===Operations===