Ford-Fulkerson: Difference between revisions
| (7 intermediate revisions by 2 users not shown) | |||
| Line 9: | Line 9: | ||
'''Invariant:''' | '''Invariant:''' | ||
After <math>i \ge 0</math> iterations: | After <math>i \ge 0</math> iterations: | ||
# The flow <math>f</math> is a feasible flow. | # The flow <math>f</math> is a [[basic flow definitions#Feasible flow|feasible flow]]. | ||
# If all upper bounds are integral, <math>f</math> is integral as well. | # If all upper bounds are integral, <math>f</math> is integral as well. | ||
'''Variant:''' The value of <math>f</math> increases. | '''Variant:''' The [[Basic flow definitions#Flow value|flow value]] of <math>f</math> increases. | ||
'''Break condition:''' There is no flow- | '''Break condition:''' There is no [[Basic flow definitions#Flow-augmenting paths and saturated arcs|flow-augmenting path]]. | ||
== Induction basis == | == Induction basis == | ||
| Line 26: | Line 26: | ||
'''Abstract view:''' Find a [[Basic flow definitions#Flow-augmenting path|flow-augmenting path]] and increase <math>f</math> along this path up to saturation. If no path is found, the break condition applies, and the loop is terminated. | '''Abstract view:''' Find a [[Basic flow definitions#Flow-augmenting path|flow-augmenting path]] and increase <math>f</math> along this path up to saturation. If no path is found, the break condition applies, and the loop is terminated. | ||
'''Proof:''' If the graph traversal does not hit <math>t</math>, the break condition is fulfilled, and nothing is to show. So consider the case that the graph traversal does hit <math>t</math>. Then an <math>(s,t)</math>-path is found. Augmenting along this path up to saturation preserves feasibility of the flow | '''Proof:''' If the graph traversal does not hit <math>t</math>, the break condition is fulfilled, and nothing is to show. So consider the case that the graph traversal does hit <math>t</math>. Then an <math>(s,t)</math>-path is found. [[Basic flow definitions#Augmenting along a path|Augmenting along this path up to saturation]] preserves feasibility of the flow. | ||
== Correctness == | == Correctness == | ||
| Line 39: | Line 39: | ||
It is also evident that, before and after each iteration, the flow values on all arcs are integral. In particular, the total flow value is integral. The variant implies that, in case of integral capacity values, the total flow value increases by at least one unit in every iteration. Since the total flow value is always in the interval <math>[0...F]</math>, this may happen at most <math>F</math> times. | It is also evident that, before and after each iteration, the flow values on all arcs are integral. In particular, the total flow value is integral. The variant implies that, in case of integral capacity values, the total flow value increases by at least one unit in every iteration. Since the total flow value is always in the interval <math>[0...F]</math>, this may happen at most <math>F</math> times. | ||
'''Remark:''' | |||
The number of nodes is irrelevant because at most <math>m</math> nodes are reachable from <math>s</math> (not including <math>s</math> itself). | |||
Latest revision as of 11:49, 23 June 2015
General information
Algorithmic problem: Max-flow problems (standard version)
Type of algorithm: loop
Abstract view
Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:
- The flow [math]\displaystyle{ f }[/math] is a feasible flow.
- If all upper bounds are integral, [math]\displaystyle{ f }[/math] is integral as well.
Variant: The flow value of [math]\displaystyle{ f }[/math] increases.
Break condition: There is no flow-augmenting path.
Induction basis
Abstract view: We start with some feasible flow, for example, the zero flow.
Implementation: Obvious.
Proof: Obvious.
Induction step
Abstract view: Find a flow-augmenting path and increase [math]\displaystyle{ f }[/math] along this path up to saturation. If no path is found, the break condition applies, and the loop is terminated.
Proof: If the graph traversal does not hit [math]\displaystyle{ t }[/math], the break condition is fulfilled, and nothing is to show. So consider the case that the graph traversal does hit [math]\displaystyle{ t }[/math]. Then an [math]\displaystyle{ (s,t) }[/math]-path is found. Augmenting along this path up to saturation preserves feasibility of the flow.
Correctness
Due to the invariant, the flow is feasible before and after each iteration. Termination results from the complexity considerations below. Due to the max-flow min-cut theorem, the break condition implies that the final flow is maximum.
Complexity
Statement: If all capacity values are integral, the asymptotic worst-case complexity is [math]\displaystyle{ \mathcal{O} (m\cdot F) }[/math], where [math]\displaystyle{ m = |A| }[/math] and [math]\displaystyle{ F }[/math] is the maximum total flow value.
Proof: A graph search from [math]\displaystyle{ s }[/math] requires [math]\displaystyle{ \Omicron (m) }[/math] . Obviously, determining [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] and changing the flow values along [math]\displaystyle{ p }[/math] requires [math]\displaystyle{ \mathcal{O}(m) }[/math] as well. It is also evident that, before and after each iteration, the flow values on all arcs are integral. In particular, the total flow value is integral. The variant implies that, in case of integral capacity values, the total flow value increases by at least one unit in every iteration. Since the total flow value is always in the interval [math]\displaystyle{ [0...F] }[/math], this may happen at most [math]\displaystyle{ F }[/math] times.
Remark: The number of nodes is irrelevant because at most [math]\displaystyle{ m }[/math] nodes are reachable from [math]\displaystyle{ s }[/math] (not including [math]\displaystyle{ s }[/math] itself).