2.0p Grid outerconnect 1 An n x n grid is an undirected graph consisting of 72 rows and 72 columns of vertices, as shown below. It has n vertices in total. We denote the vertex in the ith row and 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. (a) (b) In this exercise we consider a routing problem on grids that occurs when designing electronic circuit boards. Given a placement of transistors at given distinct vertices of a grid, we wish to determine if these transistors can be connected to the boundary of the grid, from where they connect to other components of the circuit board. To avoid short-circuits, each transistor should get its own connection to the boundary of the grid and the vertices and edges on this path should not be used by any other connections. We say that a grid with a given placement of transistors has an outerconnect if all transistors can be simultaneously connected to the boundary by a path that is vertex-disjoint from all the other paths. For example, the grid in (a) has an outerconnect, but the grid in (b) does not. Given a grid and a placement of m < n transistors at distinct vertices (, ), (2, Y),..., (Tm, Ym). the goal is to determine whether there is an outerconnect for the grid. Describe how the existence of an outerconnect (yes or no) can be determined by a single maximum flow computation. That is, describe how to construct a flow network G=(V, E) (with a sources, sinkt, and capacity function e for each edge) and how to define a value k from the given placement of m transistors, so that an outerconnect exists if and only there is a flow of value k in G. Describe the construction clearly. You do not have to prove its correctness. Hint: Find a way to prevent more than one unit of flow from going through any node of the grid, by representing such a node with two vertices joined by an edge of capacity 1.