Reference no: EM131258865

Pathological example for the labeling algorithm. In the residual network G(x) corresponding to a flow x, we define an augmenting walk as a directed walk from node s to node t that visits any arc at most once (it might visit nodes multiple times-in particular, an augmenting walk might visit nodes s and t multiple times.)

(a) Consider the network shown in Figure 6.26(a) with the arcs labeled a, b, c and d; note that one arc capacity is irrational. Show that this network contains an infinite sequence of augmenting walks whose residual capacities sum to the maximum flow value. (Hint: Each augmenting walk of the sequence contains exactly two arcs from node s to node t with finite residual capacities.)

(b) Now consider the network shown in Figure 6.26(b). Show that this network contains an infinite sequence of augmenting walks whose residual capacities sum to a value different than the maximum flow value.

(c) Next consider the network shown in Figure 6.26(c); in addition to the arcs shown, the network contain an infinite capacity arc connecting each node pair in the set