2 (***) A cohort of spies A cohort of k spies resident in a certain country needs escape routes in case of emergency. They will be travelling using the railway system which we can think of as a directed graph G-(V, E) with V being the cities. Each spy i has a starting point si V and needs to reach the consulate of a friendly nation; these consulates are in a known set of cities T CV. In order to move undeteced, the spies agree that at most c of them should ever pass through any one city. Our goal is to find a set of paths for each of the spies (or detect that the requirements cannot be met). Model this problem as a flow network. Specify the vertices, edges and capacities, and show that a maximum flow in your network can be transformed into an optimal solution for the original problem. You do not need to explain how to solve the max-flow instance itself. 2 (***) A cohort of spies A cohort of k spies resident in a certain country needs escape routes in case of emergency. They will be travelling using the railway system which we can think of as a directed graph G-(V, E) with V being the cities. Each spy i has a starting point si V and needs to reach the consulate of a friendly nation; these consulates are in a known set of cities T CV. In order to move undeteced, the spies agree that at most c of them should ever pass through any one city. Our goal is to find a set of paths for each of the spies (or detect that the requirements cannot be met). Model this problem as a flow network. Specify the vertices, edges and capacities, and show that a maximum flow in your network can be transformed into an optimal solution for the original problem. You do not need to explain how to solve the max-flow instance itself