3. \begin{figure}[h] \end{figure} Figure 5 represents a network of corridors in a school. The number on each arc represents the maximum number of students, per minute, that may pass along each corridor at any one time. At 11 am on Friday morning, all students leave the hall (S) after assembly and travel to the cybercafé ( T ). The numbers in circles represent the initial flow of students recorded at 11 am one Friday.

1. State an assumption that has been made about the corridors in order for this situation to be modelled by a directed network.
2. Find the value of x and the value of y , explaining your reasoning. Five new students also attend the assembly in the hall the following Friday. They too need to travel to the cybercafé at 11 am . They wish to travel together so that they do not get lost. You may assume that the initial flow of students through the network is the same as that shown in Figure 5 above.
3. 1. List all the flow augmenting routes from S to T that increase the flow by at least 5
   2. State which route the new students should take, giving a reason for your answer.
4. Use the answer to part (c) to find a maximum flow pattern for this network and draw it on Diagram 1 in the answer book.
5. Prove that the answer to part (d) is optimal. The school is intending to increase the number of students it takes but has been informed it cannot do so until it improves the flow of students at peak times. The school can widen corridors to increase their capacity, but can only afford to widen one corridor in the coming term.
6. State, explaining your reasoning,
   1. which corridor they should widen,
   2. the resulting increase of flow through the network.