-
n * n 그리드 형태의 무방향 그래프가 존재한다. 행렬을 (i, j)로 표현했을 때, 그리드의 i =1, i = n, j =1, or j = n(테두리에 위치한 정점들)을 제외한 모든 정점들은 정확히 4개의 이웃을 갖는다.
-
시작점은 검은색, 다른 정점들은 흰색이다. (a) 그래프의 탈출 경로는 그림자로 표현된 경로이며, (b) 그래프는 탈출 불가능하다.
-
탈출 문제는 그리드에서 시작점 (x1, y1), (x2, y2), …, (xm, ym)이 주어졌을 때 각 시작점에서 경계로 가는 m개의 경로가 존재하는지 여부를 결정한다.
An n x n grid is an undirected graph consisting of n rows and n columns of vertices, as shown in Figure 27.12. We denote the vertex in the ith row and the jth 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.*
Figure 27.12 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 escape.
Given m 
a. Consider a flow network in which vertices, as well as edges, have capacities. That is, the positive net 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.
| 동작 | 시각화 | |
|---|---|---|
| 1 | • 모든 간선에 1의 가중치를 부여한다 |  |
| 2 | • 정점 s를 만든다. • 모든 시작점에 방향 연결한다. • 새로 만든 간선에 1의 가중치를 부여한다. |  |
| 3 | • 정점 t를 만든다. • 그리드의 경계에 있는 정점들을 t에 방향 연결한다. • 간선에 1의 가중치를 부여한다. |  |
| 4 | • 정점에는 Cost가 없기 때문에 정점을 통한 경로가 중복되는 경우가 발생할 수 있는데, 그리드를 2중으로 만들어 Vin과 Vout을 만든 후, 간선의 가중치를 1로 부여해 해결한다. |  |
| 5 | • Network Flow의 입력 인스턴스로 변형하였으므로 Edmonds-Karp 알고리즘으로 이를 풀 수 있다. • Network Flow 문제를 알려진 방법대로 푼다. • 결과로 나온 max flow는 robbers의 수와 동일하다. • flow들의 0또는 1의 값은 모든 정점들에 대한 탈출 경로를 나타낸다. | - |
| 입력 데이터 | 콘솔 결과 |
|---|---|
  |
 |