Consider the following network.

Treat the rst number assigned to each edge as a capacity and let the edges be directed by alphabetical order of their endpoints with L preceding a and W following n [e.g., the edge between f and i goesfrom f to i].

(a) If we say that the second number is the ow through the edge, is this a feasible L W ow?

(b) Find the maximum L W ow and a minimum L W cut in this network.

(c) By inspection, nd a dierent maximum L W ow.

(d) In addition, let the second number of each edge be a lower bound on the ow in that edge. Try to nd an L W ow satisfying both constraints.

8, 4 8, 5 3, 1 /5, 1 7, 2 4, 1 7, 2 5, 1 5, 2 4, 1 8, 3 4, 2 6, 3 7, 2 8, 4 12, 4. 6, 3 4, 2 4, 2 5, 3 8, 3 5, l 5, 5 m 6, 2