Bipartite graph definition or properties

1 The directed bipartite graph represents links between chairlifts and ski runs in one part of a ski resort. Chairlifts are represented by capital letters, and ski runs are represented by numbers. For example, chairlift A takes skiers to the tops of ski runs 1 and 2, whereas ski run 2 takes skiers to the bottom of chairlift B . \includegraphics[max width=\textwidth, alt={}, center]{a27c868b-4fc4-4e82-b27f-d367b15b42c2-2_551_333_493_849}

1. The incomplete map in your answer book represents the three chairlifts and ski run 2 . Complete the map by drawing in the other 4 ski runs. Angus wants to ski all 5 ski runs, starting and finishing at the bottom of chairlift A .
2. Which chairlifts does Angus have to repeat, and why?
3. Which ski runs does Angus have to repeat, and why? The chairlifts and ski runs shown above form only part of the resort. In fact, chairlift C also takes skiers to the bottom of chairlift \(D\).
4. Why can this information not be represented in a bipartite graph?

4. This question should be answered on the sheet provided in the answer booklet. A manager has five workers, Mr. Ahmed, Miss Brown, Ms. Clough, Mr. Dingle and Mrs. Evans. To finish an urgent order he needs each of them to work overtime, one on each evening, in the next week. The workers are only available on the following evenings: Mr. Ahmed \(( A )\) - Monday and Wednesday;
Miss Brown ( \(B\) ) - Monday, Wednesday and Friday;
Ms. Clough ( \(C\) ) - Monday;
Mr. Dingle ( \(D\) ) - Tuesday, Wednesday and Thursday;
Mrs. Evans \(( E )\) - Wednesday and Thursday.
The manager initially suggests that \(A\) might work on Monday, \(B\) on Wednesday and \(D\) on Thursday.

1. Using the nodes printed on the answer sheet, draw a bipartite graph to model the availability of the five workers. Indicate, in a distinctive way, the manager's initial suggestion.
   (2 marks)
2. Obtain an alternating path, starting at \(C\), and use this to improve the initial matching.
   (3 marks)
3. Find another alternating path and hence obtain a complete matching.
   (3 marks)

4

1. State the definition of a bipartite graph. 4
2. A jazz quintet has five musical instruments: bassoon, clarinet, flute, oboe and violin. Jay, Kay, Lee, Mel and Nish are musicians and each plays a musical instrument in the jazz quintet. Jay knows how to play the bassoon and the clarinet.
   Kay knows how to play the bassoon, the oboe and the violin.
   Lee knows how to play the clarinet and the flute.
   Mel knows how to play the clarinet, the oboe and the violin.
   Nish knows how to play the flute, the oboe and the violin. 4 (b) (i) Draw a graph to show which musicians know how to play which instruments. 4 (b) (ii) Nish arrives late to a jazz quintet rehearsal. Each of the other four musicians is already playing an instrument: \begin{displayquote} Jay is playing the clarinet
   Kay is playing the oboe
   Lee is playing the flute
   Mel is playing the violin. \end{displayquote} Explain how the graph in part (b)(i) shows that there is no instrument available that Nish knows how to play. 4 (b) (iii) When Nish arrives the rehearsal stops. When they restart the rehearsal, Nish is playing the flute. Draw all possible subgraphs of the graph in part (b)(i) that show how Jay, Kay, Lee and Mel can each be assigned a unique musical instrument they know how to play.
   [0pt] [2 marks]

Define the terms

1. bipartite graph, [2]
2. alternating path, [2]
3. matching, [1]
4. complete matching. [1]

A political party is holding an election to choose a new leader. A statistician within the party decides to sample 70 party members to find their opinions of the leadership candidates. There are 4735 members under 30 years old and 8565 members 30 years old and over. The statistician wants to use a sample of 70 party members in the survey. He decides to use a random stratified sample.

1. Calculate how many of each age group should be included in his sample. [2 marks]
2. Explain how he could collect the random sample of members under 30 years old. [3 marks]