4. The precedence table shows the activities involved in a project.
| Activity | Immediately preceding activities |
| A | - |
| B | - |
| C | - |
| D | A |
| E | A |
| \(F\) | B |
| G | B |
| H | C, D |
| I | E |
| J | \(F , H\) |
| K | \(G , J\) |
| L | G |
| M | L |
| \(N\) | L |
- Draw the activity network for this project, using activity on arc and using two dummies.
- Explain why each of the two dummies is necessary.
(3)
(Total 7 marks)
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{19cfdf0b-6be6-4f44-bfae-2b6bf592cfd8-5_635_446_296_485}
\end{figure}
\begin{figure}[h]
\captionsetup{labelformat=empty}
\caption{Figure 4}
\includegraphics[alt={},max width=\textwidth]{19cfdf0b-6be6-4f44-bfae-2b6bf592cfd8-5_639_450_296_1233}
\end{figure}
A film critic, Verity, must see five films A, B, C, D and E over two days.
The films are being shown at five special critics' preview times:
\(\begin{array} { l l } 1 & ( \text { Monday } 4 \mathrm { pm } ) ,
2 & ( \text { Monday } 7 \mathrm { pm } ) ,
3 & ( \text { Tuesday } 1 \mathrm { pm } ) ,
4 & ( \text { Tuesday } 4 \mathrm { pm } ) ,
5 & ( \text { Tuesday } 7 \mathrm { pm } ) . \end{array}\)
The bipartite graph in Figure 3 shows the times at which each film is showing.
Initially Verity intends to see
\begin{displayquote}
Film A on Monday at 4 pm , Film B on Tuesday at 4 pm , Film C on Tuesday at 1 pm , Film D on Monday at 7 pm .
\end{displayquote}
This initial matching is shown in Figure 4.
Using the maximum matching algorithm and the given initial matching, - find two distinct alternating paths and complete the matchings they give.
Verity's son is very keen to see film D, but he can only go with his mother to the showing on Monday at 7 pm .
- Explain why it will not be possible for Verity to take her son to this showing and still see all five films herself.