minimum cut,
as applied to a directed network flow.
(2)
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{fd0401c4-bf18-4c3b-af1d-cd1b633c6853-5_845_1610_713_294}
\end{figure}
Figure 4 shows a capacitated directed network and two cuts \(C _ { 1 }\) and \(C _ { 2 }\). The number on each arc is its capacity.
(b) State the values of the cuts \(C _ { 1 }\) and \(C _ { 2 }\).
(3)
Given that one of these two cuts is a minimum cut,
(c) find a maximum flow pattern by inspection, and show it on the diagram in the answer book.
(d) Find a second minimum cut for this network.
(1)
In order to increase the flow through the network it is decided to add an arc of capacity 100 joining \(D\) either to \(E\) or to \(G\).
(e) State, with a reason, which of these arcs should be added, and the value of the increased flow.
(2)
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 5}
\includegraphics[alt={},max width=\textwidth]{fd0401c4-bf18-4c3b-af1d-cd1b633c6853-6_649_1496_320_294}
\end{figure}
The network in Figure 5 shows the activities involved in a process. The activities are represented by the arcs. The number in brackets on each arc gives the time, in days, taken to complete the activity.
(a) Calculate the early time and late time for each event, showing them on the diagram in the answer book.
(b) Determine the critical activities and the length of the critical path.
(c) On the grid in the answer book, draw a cascade (Gantt) chart for the process.
Each activity requires only one worker, and workers may not share an activity.
(d) Use your cascade chart to determine the minimum numbers of workers required to complete the process in the minimum time. Explain your reasoning clearly.
(e) Schedule the activities, using the number of workers you found in part (d), so that the process is completed in the shortest time.