**Property 6.2** For any flow *x* of value *v* in a network, the additional flow that can be sent from* s *to* t *is less than or equal to the residual capacity of any
*s *-* t *cut.
**Generic Path Augmenting Algorithm**
Definition: __Augmenting Path__: directed path from* s *to* t *in the residual network
__Residual capacity of an augmenting path:__ minimum residual capacity of any arc in the augmenting path.
1 2
s t
3 4
1 2
s t
3 4
If the minimum residual capacity along an augmenting path is > 0 then we can push more flow along that path.
We can build an algorithm that works by finding paths and pushing the maximum flow on them.
**algorithm** augmenting path;
**begin**
x : = 0;
** while** G(x) contains a directed path from node* s *to node* t ***do**
** begin**
identify an augmenting path P from node* s *to node *t*;
augment units of flow along P and update G(x);
**end;**
**end;**
** Figure 6.12** Generic augmenting path algorithm.
1 2
s t
3 4
1 2
s t
3 4
1 2
s t
3 4
1 2
s t
3 4
**Relationship between the original and residual networks**
We can keep track of x_{ij} or r_{ij}, because they have an equivalence.
Augmenting path in original:
Path P (need not be directed) from* s *to *t *such that x_{ij }< u_{ij} for forward arcs and x_{ji }> 0 for backward arcs.
Can show equivalence to directed path in residual network.
When we updated the flows we increased the x_{ij} values on the forward arcs and decreased the x_{ji} values on the backward arcs.
If we use r_{ij}'s how do we get x_{ij}'s?
Recall r_{ij }= u_{ij }- x_{ij }+ x_{ji} or u_{ij }- r_{ij }= x_{ij }- x_{ji}
if u_{ij }> r_{ij} let x_{ij }= u_{ij }- r_{ij }and x_{ji }= 0
if u_{ij }< r_{ij} let x_{ij }= 0 and x_{ji = }r_{ij} - u_{ij}
**Explanation of path augmenting when there are backward arcs. **
**Labeling algorithm & maximum flow minimum cut theorem**
Discuss augmenting path algorithm in more detail.
Specifically
1. How do we know if there are any more augmenting paths?
2. Will the algorithm terminate in an infinite number of steps?
3. Will the algorithm terminate at opt.?
In general the algorithm fans out from* s *labeling nodes - we can label a node if we can reach that node in the residual network (that is there is a path with r_{ij} > 0 for all arcs in the path). When we label the sink, stop and augment flow. If we can't label the sink stop.
**algorithm** labeling;
**begin**
label node *t*;
** while*** t *is labeled **do**
** begin**
unlabel all nodes;
set pred (j) : = 0 for each jN;
label node* s *and set LIST : = {*s*};
**while** LIST and* t *is unlabeled **do**
** begin**
remove a node i from LIST;
**for** each arc (i, j) in the residual network emanating from
node i **do**
**if** r_{ij} > 0 and node j is unlabeled **then** set
pred (j) : = i , label node j, and add j to LIST;
**end;**
** if**** t **is labeled **then** augment
**end;**
**end;**
**procedure **augment;
**begin**
use the predecessor labels to trace back from the sink to the source to obtain an augmenting path P from node* s *to node t;
augment units of flow along P and update the residual capacities;
**Share with your friends:** |