4 The diagram represents a system of roads through which traffic flows from a source, \(S\), to a sink, \(T\). The weights on the arcs show the capacities of the roads in cars per minute.
\includegraphics[max width=\textwidth, alt={}, center]{3a47bac8-0067-4acb-a3c7-7d8512403cca-5_414_1080_349_488}

1. (a) The cut \(\alpha\) partitions the vertices into the sets \(\{ S , A , B , C \} , \{ D , E , F , T \}\). Calculate the capacity of cut \(\alpha\).
   (b) The cut \(\beta\) partitions the vertices into the sets \(\{ S , A , B , D \} , \{ C , E , F , T \}\). Calculate the capacity of cut \(\beta\).
   (c) Using only the capacities of cuts \(\alpha\) and \(\beta\), what can you deduce about the maximum possible flow through the system?
2. Explain why partitioning the vertices into sets \(\{ S , A , D , T \} , \{ B , C , E , F \}\) does not give a cut.
3. What do the double arcs between \(D\) and \(E\) and between \(E\) and \(F\) represent?
4. Explain why the maximum possible flow along \(C F\) must be less than 45 cars per minute.
5. (a) Show how a flow of 60 cars per minute along \(F T\) can be achieved.
   (b) Show that 60 cars per minute is the maximum possible flow through the system. An extra road is opened linking \(S\) to \(C\). Let the capacity of this road be \(x\) cars per minute.
6. Find the maximum possible flow through the new system, in terms of \(x\) where necessary, for the different possible values of \(x\).