An n ? n grid is an undirected graph consisting of n rows and n columns of vertices, as shown in Figure 26.11. We denote the vertex in the i th row and the j th column by (I, j). All vertices in a grid have exactly four neighbors, except for the boundary vertices, which are the points (I, j) for which i = 1, i = n, j = 1, or j = n. Given m ? n² starting points?(x₁, y₁), (x₂, y₂), . . . , (x_m, y_m)?in the grid, the?escape problem?is to determine whether or not there are?m?vertex-disjoint paths from the starting points to any?m?different points on the boundary. For example the grid in Figure 26(11(a) has an escape, but the grid in Figure 26(11(b) does not.

a.?Consider a flow network in which vertices, as well as edges, have capacities. That is, the total positive flow entering any given vertex is subject to a capacity constraint. Show that determining the maximum flow in a network with edge and vertex capacities can be reduced to an ordinary maximum-flow problem on a flow network of comparable size.

Figure 26.11?Grids for the escape problem( Starting points are black, and other grid vertices are white.?(a)?A grid with an escape, shown by shaded paths.?(b)?A grid with no escap.

b. Describe an efficient algorithm to solve the escape problem, and analyze its running time.

Transcribed Image Text:

(а) (b)