26-1 Escape problem

A\(n \times 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 \le n^2\) starting points \((x_1, y_1), (x_2, y_2), \ldots, (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.

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

a. This problem is identical to exercise 26.1-7.

b. Construct a vertex constrained flow network from the instance of the escape problem by letting our flow network have a vertex (each with unit capacity) for each intersection of grid lines, and have a bidirectional edge with unit capacity for each pair of vertices that are adjacent in the grid. Then, we will put a unit capacity edge going from \(s\) to each of the distinguished vertices, and a unit capacity edge going from each vertex on the sides of the grid to \(t\). Then, we know that a solution to this problem will correspond to a solution to the escape problem because all of the augmenting paths will be a unit flow, because every edge has unit capacity. This means that the flows through the grid will be the paths taken. This gets us the escaping paths if the total flow is equal to \(m\) (we know it cannot be greater than \(m\) by looking at the cut which has \(s\) by itself). And, if the max flow is less than \(m\), we know that the escape problem is not solvable, because otherwise we could construct a flow with value \(m\) from the list of disjoint paths that the people escaped along.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用