Reference no: EM1352863

Suppose that we allow a flow network to have negative (as well as positive) edge capacities. In such a network, a feasible flow need not exist.

(a)Consider an edge (u, v) in a flow network G = (V, E) with c(u, v) < 0. Briefly explain what such a negative capacity means in terms of the flow between u and v.

Let G = (V, E) be a flow network with negative edge capacities, and let s and t be the source and sink of G. Construct the ordinary flow network G' = (V', E') with capacity function c', source s', and sink t', where

V' = V ∪ {s', t'} and

E' = E ∪ {(u, v) : (v, u) ∈ E}
∪ {(s', v) : v ∈ V}
∪ {(u, t') : u ∈ V}
∪ {(s, t), (t, s)}

We assign capacities to edges as follows. For each edge (u, v) ∈ E, we set
c'(u, v) = c'(v, u) = (c(u, v) + c(v, u))/2 .

For each vertex u ∈ V, we set
c' (s', u) = max(0, (c(V, u) - c(u, V))/2)and

c'(u, t') = max(0, (c(u, V) - c(V, u))/2) .
We also set c'(s, t) = c'(t, s) = ∞.

( b )Prove that if a feasible flow exists in G, then all capacities in G' are nonnegative and a maximum flow exists in G' such that all edges into the sink t' are saturated.

( c ) Prove the converse of part ( b ). Your proof should be constructive, that is, given a flow in G' that saturates all the edges into t', your proof should show how to obtain a feasible flow in G.

( d ) Describe an algorithm that finds a maximum feasible flow in G. Denote by MF(|V|, |E|) the worst-case running time of an ordinary maximum flow algorithm on a graph with |V| vertices and |E| edges. Analyze your algorithm for computing the maximum flow of a flow network with negative capacities in terms of MF.