\end{figure}
Figure 1 shows a network of roads represented by arcs. The capacity of the road represented by that arc is shown on each arc. The numbers in circles represent a possible flow of 26 from \(B\) to \(L\).
Three cuts \(\mathrm { C } _ { 1 } , \mathrm { C } _ { 2 }\) and \(\mathrm { C } _ { 3 }\) are shown on Fig. 1.
Find the capacity of each of the three cuts.
Verify that the flow of 26 is maximal.
The government aims to maximise the possible flow from \(B\) to \(L\) by using one of two options.
Option 1: Build a new road from \(E\) to \(J\) with capacity 5 .
or
Option 2: Build a new road from \(F\) to \(H\) with capacity 3.
By considering both options, explain which one meets the government's aim
(3)
\begin{figure}[h]
\end{figure}
An engineer needs to check the state of a number of roads to see whether they need resurfacing. The roads that need to be checked are represented by the arcs in Fig. 2. The number on each arc represents the length of that road in km. To check all the roads, he needs to travel along each road at least once. He wishes to minimise the total distance travelled.
The engineer's office is at \(G\), so he starts and ends his journey at \(G\).
Use an appropriate algorithm to find a route for the engineer to follow. State your route and its length.
(6)
The engineer lives at \(D\). He believes he can reduce the distance travelled by starting from home and inspecting all the roads on the way to his office at \(G\).
State whether the engineer is correct in his belief. If so, calculate how much shorter his new route is. If not, explain why not.
(3)
\includegraphics[max width=\textwidth, alt={}, center]{a21a4565-800c-45c0-a513-bb813ef1086f-5_1561_1568_347_178}
Figure 3 describes an algorithm in the form of a flow chart, where \(a\) is a positive integer.
List \(P\), which is referred to in the flow chart, comprises the prime numbers \(2,3,5,7,11,13\), 17, ...
Starting with \(a = 90\), implement this algorithm. Show your working in the table in the answer book.
Explain the significance of the output list.
Write down the final value of \(c\) for any initial value of \(a\).