Content deleted Content added
Line 51:
====Relabel====
The relabel operation applies on an active vertex ''u'' without any admissible out-edges in {{nowrap|''G<sub>f</sub>''}}. It modifies {{nowrap|''h''(''u'')}} to the minimum value such that an admissible out-edge is created. Note that this always increases {{nowrap|''h''(''u'')}} and never creates a steep edge (an edge {{nowrap|(''u'', ''v'')}} such that {{nowrap|''c<sub>f</sub>''(''u'', ''v'') > 0}}, and {{nowrap|''h''(''u'') > ''h''(''v'') + 1}}).
relabel(u):
assert e[u] > 0 and h[u] <= h[v] ∀v such that f[u][v] < c[u][v]
h[u] = min(h[v] ∀v such that f[u][v] < c[u][v]) + 1
===Effects of push and relabel===
After a push or relabel operation, ''h'' remains a valid height function with respect to ''f''.
For a push operation on an admissible edge {{nowrap|(''u'', ''v'')}}, it may add an edge {{nowrap|(''v'', ''u'')}} to {{nowrap|''E<sub>f</sub>''}}, where {{nowrap|''h''(''v'') {{=}} ''h''(''u'') − 1 ≤ ''h''(''u'') + 1}}; it may also remove the edge {{nowrap|(''u'', ''v'')}} from {{nowrap|''E<sub>f</sub>''}}, where it effectively removes the constraint {{nowrap|''h''(''u'') ≤ ''h''(''v'') + 1}}.
To see that a relabel operation on vertex ''u'' preserves the validity of {{nowrap|''h''(''u'')}}, notice that this is trivially guaranteed by definition for the out-edges of ''u'' in {{nowrap|''G<sub>f</sub>''}}. For the in-edges of ''u'' in the {{nowrap|''G<sub>f</sub>''}}, the increased {{nowrap|''h''(''u'')}} can only satisfy the constraints less tightly but not violate them.
==Push-relabel Algorithm==
| |||