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.

Example 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 az ow problem for a unit-capacity network is equivalent to nding the maximum number of edge-disjoint 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