1 Josh is making a calendar. He has chosen six pictures, each of which will represent two months in the calendar. He needs to choose which picture to use for each two-month period. The bipartite graph in Fig. 1 shows for which months each picture is suitable.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{490ff276-6639-40a1-bffb-dc6967f3ab21-2_497_1246_488_415}
\captionsetup{labelformat=empty}
\caption{Fig. 1}
\end{figure}
Initially Josh chooses the sailing ships for March/April, the sunset for July/August, the snow scene for November/December and the swans for May/June. This incomplete matching is shown in Fig. 2 below.
\begin{table}[h]
| Sailing ships | (1) | | | January/February |
| Seascape | (2) | • ◯ | (MA) | March/April |
| Snow scene | (3) | \includegraphics[max width=\textwidth, alt={}]{490ff276-6639-40a1-bffb-dc6967f3ab21-2_54_381_1451_716} | (MJ) | May/June |
| Street scene | | \includegraphics[max width=\textwidth, alt={}]{490ff276-6639-40a1-bffb-dc6967f3ab21-2_59_38_1536_712} | (JA) | July/August |
| Sunset | (5) | | (SO) | September/October |
| Swans | (6) | | (ND) | November/December |
\captionsetup{labelformat=empty}
\caption{Fig. 2}
\end{table}
- Write down the shortest possible alternating path that starts at (JF) and finishes at either (2) or (4). Hence write down a matching that only excludes (SO) and one of the pictures.
- Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at (SO) and finishes at whichever of (2) and (4) has still not been matched. Hence write down a complete matching between the pictures and the months.
- Explain why three of the arcs in Fig. 1 must appear in the graph of any complete matching. Hence find a second complete matching.