Questions 6, 8 and 9.

6.Is there a flow meeting the demands in Figure 4.4?

8.Vertices b, c, d have supplies 30, 20, 10, respectively, and vertices j, k have demands of 30 and 25 in this network.

9.Solve the messenger problem in Example 6.

6. Is there a ow meeting the demands in Figure 4.4? 7. Suppose vertices b, c, d in Figure 4.4 have unlimited supplies. How much ow can be sent to the set {h, i, j}? Explain your model. 8. Vertices b, c, d have supplies 30, 20, 10, respectively, and vertices j, k have demands of 30 and 25 in this network. (3) Find a ow satisfying the demands, if possible. (b) Reverse the direction of edge (h, g) and repeat part (a). 9. Solve the messenger problem in Example 6. \fExample 6: Edge-Disjoint Paths in a Graph We are going to send messengers from a to z in the graph shown in Figure 4.10. Because certain edges (roads) may be blocked, we require each messenger to use different edges. How many messengers can be sent? That is, we want to know the number of edge-disjoint paths. We convert this path problem into a network ow problem by assigning unit capacities to each edge. One could think of the ow as \"ow messengers,\" and the unit capacities mean that at most one messenger can use any edge. The number of edgedisjoint paths (number of messengers) is thus equal to the value of a maximum ow in this undirected network. (See Example 5 for ows in undirected networks.) Observe that we have implicitly shown that a maximum amz ow problem for a unitcapacity network is equivalent to nding the maximum number of ed gedisjoint az paths in the associated graph (where edge capacities are ignored). This equiva lence can be extended using multigraphs to all networks by replacing each kcapacity Figure 4.10 4.3 NetworkFlows 147 (b) (edges directed downward and to right) Figure 4.11 edge (x, y) with k multiple unit-capacity edges and now proceeding with the above conversion