Revision as of 17:59, 10 April 2014 edit Kxx (talk \| contribs) Extended confirmed users 3,386 edits →Concepts: reduce verbosity ← Previous edit		Revision as of 18:42, 10 April 2014 edit undo Kxx (talk \| contribs) Extended confirmed users 3,386 edits →Definitions and notations Next edit →
Line 32: ::{{nowrap\|''h''(''u'') ≤ ''h''(''v'') + 1&emsp;∀(''u'', ''v'') ∈ ''E<sub>f</sub>''}} The heights of ''s'' and ''t'' are fixed at {{nowrap\|{{!}}''V''{{!}}}} and 0, respectively. {{nowrap\|''h''(''u'')}} is a lower bound of the unweighted distance from ''u'' to ''t'' in {{nowrap\|''G<sub>f</sub>''}} if ''t'' is reachable from ''u''. If ''u'' has been disconnected from ''t'', then {{nowrap\|''h''(''u'') − {{!}}''V''{{!}}}} 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<sub>f</sub>''}} because no such paths can be longer than {{nowrap\|({{!}}''V''{{!}} − 1)}}. ~~The heights of ''s'' and ''t'' are fixed at {{nowrap\|{{!}}''V''{{!}}}} and 0, respectively.~~ ~~The height of a vertex is a lower bound of its unweighted distance in the residual network to ''t'' or to ''s'' if it has been separated from ''t''.~~ An edge {{nowrap\|(''u'', ''v'') ∈ ''E<sub>f</sub>''}} is called ''admissible'' if {{nowrap\|''h''(''u'') {{=}} ''h''(''v'') + 1}}. The network {{nowrap\|''G̃<sub>f</sub>''(''V'', ''Ẽ<sub>f</sub>'')}} where {{nowrap\|''Ẽ<sub>f</sub>'' {{=}} {(''u'', ''v'') {{!}} (''u'', ''v'') ∈ ''E<sub>f</sub>'' ∧ ''h''(''u'') {{=}} ''h''(''v'') + 1}}} is called the ''admissible network''. The admissible network is acyclic. ===Operations===

Push–relabel maximum flow algorithm: Difference between revisions