. Consider a directed graph with edge capacities, representing a rail network. There are three types of vertex: supplies, demands, and ordinary interconnection points. There is a single type of cargo we wish to carry. Each demand vertex v requires dv>0 units. Each supply vertex v has a maximum amount it can produce sv>0 units. We wish to determine if we can route exactly dv units to each demand vertex v from the supply vertices. (i) Explain how to express this problem as a max flow problem. Justify correctness of your construction. [10 marks] We now add a further constraint: each interconnection point v has a capacity iv0, and no more than iv units of flow can pass through v. More formally if an interconnection point v has edges e1,,ek then the flow though these edges can be at most iv. (ii) Adapt your model for the original problem above to take account of this new constraint. Justify correctness of your construction. [10 marks] We now allow each demand vertex to receive any number of units. The question is now: can we route all available units from supply vertices to some demand vertices? (iii) Design a polynomial time algorithm to solve this problem. Justify correctness of your algorithm. [10 marks]