3. (a) (all students). The figure shows the map of an island, divided into nine squares. The people in the yellow city in the northwest want to build a wall separating them from the red city on the southeast, and they can choose to route it along any of the black line segments between two squares (only the line segments that are inland, not the line segments along the beaches). The cost for building a wall on each segment is not yet known (but can be assumed to be positive) and different line segments might have different costs. (Some go through swamps, some over mountains, etc.) The wall should go all the way across the island, so thatt separates the island into two countries, one for each city. Draw a directed graph with a vertex for each square (with two vertices labeled s and t, but with no edge capacities) such that, once we find out the cost for building each segment of wall, we can use those costs as edge capacities and solve a minimum cut problem on the resulting flow network to find the cheapest wall 3. (a) (all students). The figure shows the map of an island, divided into nine squares. The people in the yellow city in the northwest want to build a wall separating them from the red city on the southeast, and they can choose to route it along any of the black line segments between two squares (only the line segments that are inland, not the line segments along the beaches). The cost for building a wall on each segment is not yet known (but can be assumed to be positive) and different line segments might have different costs. (Some go through swamps, some over mountains, etc.) The wall should go all the way across the island, so thatt separates the island into two countries, one for each city. Draw a directed graph with a vertex for each square (with two vertices labeled s and t, but with no edge capacities) such that, once we find out the cost for building each segment of wall, we can use those costs as edge capacities and solve a minimum cut problem on the resulting flow network to find the cheapest wall