Content deleted Content added
Line 17:
Given a flow network <math>G(V,E)</math> with capacity from node ''u'' to node ''v'' given as <math>c(u,v)</math>, source ''s'' and sink ''t'', we want to find the maximum amount of flow you can send from ''s'' to ''t'' through the network. Two types of operations are performed on nodes, ''push'' and ''relabel''. Throughout we maintain:
:{|
| ''f(u,v)'': ||Flow from ''u'' to ''v''.
* <math>\mathrm{height}(u)</math>. We only ''push'' from ''u'' to ''v'' if <math>\mathrm{height}(u) = \mathrm{height}(v)+1</math>. For each residual edge ''(u,v)'', <math>\mathrm{height}(u) \leq \mathrm{height}(v) +1 </math>.▼
|-
* <math>\mathrm{excess}(u)</math>. Sum of flow to and from ''u''.▼
| ''residual edge'': ||If available capacity <math>c(u,v) - f(u,v)>0</math> we have a residual edge <math>r(u,v)</math>.
|-
| ''residual edge (Alternate)'': ||<math>r(v,u) = - f (u,v)</math>. We can push flow back along an edge.
|-
| ''residual graph'': ||The set of all residual edges forms the residual graph.
|-
▲
|-
|}
There are three conditions for [[flow network|flow networks]]:
| |||