Moderate -0.8 This is a standard textbook application of the alternating path algorithm with an initial matching already provided. Students simply need to execute the mechanical procedure to find an augmenting path and improve the matching—no problem-solving insight or novel thinking required, just routine algorithm application.
1 A quiz team must answer questions from six different topics, numbered 1 to 6. The team has six players, \(A , B , C , D , E\) and \(F\). Each player can only answer questions on one of the topics. The players list their preferred topics. The bipartite graph shows their choices.
\includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-02_711_499_781_760}
Initially, \(A\) is allocated topic 2, \(B\) is allocated topic \(3 , C\) is allocated topic 1 and \(F\) is allocated topic 4. By using an alternating path algorithm from this initial matching, find a complete matching. [0pt]
[5 marks]
1 A quiz team must answer questions from six different topics, numbered 1 to 6. The team has six players, $A , B , C , D , E$ and $F$. Each player can only answer questions on one of the topics. The players list their preferred topics. The bipartite graph shows their choices.\\
\includegraphics[max width=\textwidth, alt={}, center]{f5890e58-38c3-413c-8762-6f80ce6dcec7-02_711_499_781_760}
Initially, $A$ is allocated topic 2, $B$ is allocated topic $3 , C$ is allocated topic 1 and $F$ is allocated topic 4. By using an alternating path algorithm from this initial matching, find a complete matching.\\[0pt]
[5 marks]
\hfill \mbox{\textit{AQA D1 2015 Q1 [5]}}