Content deleted Content added
Line 15:
==Definition==
:{|▼
| '''Capacity constraints''': || <math>\ f(u,v) \le c(u,v)</math>. The flow along an edge cannot exceed its capacity.▼
|-▼
| '''Skew symmetry''': || <math>\ f(u,v) = - f(v,u)</math>. The net flow from <math>\ u</math> to <math>\ v</math> must be the opposite of the net flow from <math>\ v</math> to <math>\ u</math> (see example).▼
|-▼
| '''Flow conservation''': || <math>\ \sum_{w \in V} f(u,w) = 0</math>, unless <math>\ u=s</math> or <math>\ u=t</math>. The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow.▼
|}▼
The '''preflow''' algorithm observes the first two of the conditions of flow networks, plus a relaxed third condition for the duration of the algorithm (the algorithm finishes once all the excess is gone from the graph, at which point we have a legal flow, and the '''Flow conservation''' constraint is again observed):▼
:{|▼
| '''Non-negativity constraint: ''' <math>\ \sum_v f(v,u) = \mathrm{excess}(u) \geq 0</math> for all nodes <math>u \neq s</math>. More flow enters a node than exits.▼
|}▼
Given a flow network <math>G(V,E)</math> with capacity from node ''u'' to node ''v'' given as <math>c(u,v)</math>, and the flow across ''u'' and ''v'' given as <math> f(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. Some key concepts used in the algorithm are:
Line 29 ⟶ 45:
|}
▲Given that we are operating on a flow network, we will give a brief description. There are three conditions for [[flow network|flow networks]]:
▲:{|
▲| '''Capacity constraints''': || <math>\ f(u,v) \le c(u,v)</math>. The flow along an edge cannot exceed its capacity.
▲|-
▲| '''Skew symmetry''': || <math>\ f(u,v) = - f(v,u)</math>. The net flow from <math>\ u</math> to <math>\ v</math> must be the opposite of the net flow from <math>\ v</math> to <math>\ u</math> (see example).
▲|-
▲| '''Flow conservation''': || <math>\ \sum_{w \in V} f(u,w) = 0</math>, unless <math>\ u=s</math> or <math>\ u=t</math>. The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow.
▲|}
▲The '''preflow''' algorithm observes the first two of the conditions of flow networks, plus a relaxed third condition for the duration of the algorithm (the algorithm finishes once all the excess is gone from the graph, at which point we have a legal flow, and the '''Flow conservation''' constraint is again observed):
▲:{|
▲| '''Non-negativity constraint: ''' <math>\ \sum_v f(v,u) = \mathrm{excess}(u) \geq 0</math> for all nodes <math>u \neq s</math>. More flow enters a node than exits.
▲|}
We observe that the longest possible path from ''s'' to ''t'' is <math>|V|</math> nodes long. Therefore it must be possible to assign ''height'' to the nodes such that for any legal flow, <math>\mathrm{height}(s) = |V|</math> and <math>\mathrm{height}(t) = 0</math>, and if there is a positive flow from ''u'' to ''v'', <math>\mathrm{height}(u) > \mathrm{height}(v)</math>. As we adjust the height of the nodes, the flow goes through the network as water through a landscape. Differing from algorithms such as [[Ford–Fulkerson algorithm|Ford–Fulkerson]], the flow through the network is not necessarily a legal flow throughout the execution of the algorithm.
| |||