Content deleted Content added
→Definitions: {{main}} |
|||
Line 14:
To ''push'' preflow is to move it down a residual edge from a vertex ''u'' to a vertex ''v'', where <math>h(u) = h(v)+1 </math>. It is called a ''saturating push'' if all of the capacity of the residual edge was used (and thus the edge ''(u,v)'' is removed from the residual graph). It is called a ''non-saturating push'' if after the push there is still available capacity on edge ''(u,v)''. Note that a non-saturating push will deplete all the excess flow from vertex ''u''. A saturating push may deplete ''u'', but not necessarily.
==
{{main|Flow network}}
The push-relabel algorithm finds maximum flow on a [[flow network]]. There are three conditions for a flow network:
| |||