7.02e Bipartite graphs: K_{m,n} notation

3. At a water sports centre there are five new instructors. Ali (A), George ( \(G\) ), Jo ( \(J\) ), Lydia ( \(L\) ) and Nadia \(( N )\). They are to be matched to five sports, canoeing \(( C )\), scuba diving \(( D )\), surfing \(( F )\), sailing ( \(S\) ) and water skiing ( \(W\) ). The table indicates the sports each new instructor is qualified to teach. Initially, \(A , G , J\) and \(L\) are each matched to the first sport in their individual list.

1. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way.
2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You must clearly list any alternating paths used. Given that on a particular day \(J\) must be matched to \(D\),
3. explain why it is no longer possible to find a complete matching. \includegraphics[max width=\textwidth, alt={}, center]{438a62e6-113c-428e-85bf-4b1cbecee0de-4_720_1305_391_236} Figure 2 models an underground network of pipes that must be inspected for leaks. The nodes \(A\), \(B , C , D , E , F , G\) and \(H\) represent entry points to the network. The number on each arc gives the length, in metres, of the corresponding pipe. Each pipe must be traversed at least once and the length of the inspection route must be minimised.

3. \begin{figure}[h] \end{figure} The bipartite graph in Fig. 2 shows the possible allocations of people \(A , B , C , D , E\) and \(F\) to tasks \(1,2,3,4,5\) and 6. An initial matching is obtained by matching the following pairs \(A\) to \(3 , \quad B\) to \(4 , \quad C\) to \(1 , \quad F\) to 5 .

1. Show this matching in a distinctive way on the diagram in the answer book.
2. Use an appropriate algorithm to find a maximal matching. You should state any alternating paths you have used.
   (5)

3. Six newspaper reporters Asif (A), Becky (B), Chris (C), David (D), Emma (E) and Fred (F), are to be assigned to six news stories Business (1), Crime (2), Financial (3), Foreign (4), Local (5) and Sport (6). The table shows possible allocations of reporters to news stories. For example, Chris can be assigned to any one of stories 1, 2 or 4.

1. Show these possible allocations on the bipartite graph on the diagram in the answer book. A possible matching is
   A to 5,
   C to 1 ,
   E to 6,
   F to 4
2. Show this information, in a distinctive way, on the diagram in the answer book.
   (1)
3. Use an appropriate algorithm to find a maximal matching. You should list any alternating paths you have used.
4. Explain why it is not possible to find a complete matching.

1 Answer this question on the insert provided. Mrs Price has bought six T shirts for her children. Each child is to have two shirts.
Amanda would like the green shirt, the pink shirt or the red shirt.
Ben would like the green shirt, the turquoise shirt, the white shirt or the yellow shirt.
Carrie would like the pink shirt, the white shirt or the yellow shirt.

1. On the first diagram in the insert, draw a bipartite graph to show which child would like which shirt. The children are represented as \(A 1 , A 2 , B 1 , B 2 , C 1\) and \(C 2\) and the shirts as \(G , P , R , T , W\) and \(Y\). Initially, Mrs Price puts aside the green shirt and the pink shirt for Amanda, the turquoise shirt and the white shirt for Ben and the yellow shirt for Carrie.
2. Show this incomplete matching on the second diagram in the insert.
3. Write down an alternating path consisting of three arcs to enable the matching to be improved. Use your alternating path to match the children to the shirts.
4. Amanda decides that she does not like the green shirt after all. Which shirts should each child have now?

5

1. How many arcs does the complete bipartite graph \(K _ { 5,5 }\) have? A subgraph of \(K _ { 5,5 }\) contains 5 arcs joining each of the elements of the set \(\{ 1,2,3,4,5 \}\) to an element in a permutation of the set \(\{ 1,2,3,4,5 \}\). Suppose that \(r\) is connected to \(p ( r )\) for \(r = 1,2,3,4,5\).
2. How many permutations would have \(p ( 1 ) \neq 1\) ?
3. Using the pigeonhole principle, show that for every permutation of \(\{ 1,2,3,4,5 \}\), the product \(\Pi _ { r = 1 } ^ { 5 } ( r - p ( r ) )\) is even (i.e. an integer multiple of 2, including 0 ).
4. Is the result in part (iii) true when the permutation is of the set \(\{ 1,2,3,4,5,6 \}\) ? Give a reason for your answer.

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. 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: $$\begin{aligned} & \text { Mr. Ahmed } ( A ) \text { - Monday and Wednesday; } \\ & \text { Miss Brown } ( B ) \text { - Monday, Wednesday and Friday; } \\ & \text { Ms. Clough } ( C ) \text { - Monday; } \\ & \text { Mr. Dingle } ( D ) \text { - Tuesday, Wednesday and Thursday; } \\ & \text { Mrs. Evans } ( E ) \text { - Wednesday and Thursday. } \end{aligned}$$ 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. Find another alternating path and hence obtain a complete matching.
   (3 marks)

1

1. Draw a bipartite graph representing the following adjacency matrix.
   (2 marks)

   	\(\boldsymbol { U }\)	\(V\)	\(\boldsymbol { W }\)	\(\boldsymbol { X }\)	\(\boldsymbol { Y }\)	\(\boldsymbol { Z }\)
   \(\boldsymbol { A }\)	1	0	1	0	1	0
   \(\boldsymbol { B }\)	0	1	0	1	0	0
   \(\boldsymbol { C }\)	0	1	0	0	0	1
   \(\boldsymbol { D }\)	0	0	0	1	0	0
   \(\boldsymbol { E }\)	0	0	1	0	1	1
   \(\boldsymbol { F }\)	0	0	0	1	1	0

2. Given that initially \(A\) is matched to \(W , B\) is matched to \(X , C\) is matched to \(V\), and \(E\) is matched to \(Y\), use the alternating path algorithm, from this initial matching, to find a complete matching. List your complete matching.

2 Five people \(A , B , C , D\) and \(E\) are to be matched to five tasks \(R , S , T , U\) and \(V\).
The table shows the tasks that each person is able to undertake.

1. Show this information on a bipartite graph.
2. Initially, \(A\) is matched to task \(V , B\) to task \(R , C\) to task \(T\), and \(E\) to task \(U\). Demonstrate, by using an alternating path from this initial matching, how each person can be matched to a task.

1 Five people, \(A , B , C , D\) and \(E\), are to be matched to five tasks, \(J , K , L , M\) and \(N\). The table shows the tasks that each person is able to undertake.

1. Show this information on a bipartite graph.
2. Initially, \(A\) is matched to task \(N , B\) to task \(J , C\) to task \(L\), and \(E\) to task \(M\). Complete the alternating path \(D - M \ldots\), from this initial matching, to demonstrate how each person can be matched to a task.
   (3 marks)

2 Six people, \(A , B , C , D , E\) and \(F\), are to be allocated to six tasks, 1, 2, 3, 4, 5 and 6. The following bipartite graph shows the tasks that each of the people is able to undertake. \includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-3_401_517_429_751} \includegraphics[max width=\textwidth, alt={}, center]{6360ed01-76da-4265-8bc8-53ffe391704e-3_408_520_943_751}

1. Represent this information in an adjacency matrix.
2. Initially, \(B\) is assigned to task \(1 , C\) to task \(2 , D\) to task 4, and \(E\) to task 5 . Demonstrate, by using an algorithm from this initial matching, how each person can be allocated to a task.

1 Six girls, Alfonsa (A), Bianca (B), Claudia (C), Desiree (D), Erika (E) and Flavia (F), are going to a pizza restaurant. The restaurant provides a special menu of six different pizzas: Margherita (M), Neapolitana (N), Pepperoni (P), Romana (R), Stagioni (S) and Viennese (V). The table shows the pizzas that each girl likes.

1. Show this information on a bipartite graph.
2. Each girl is to eat a different pizza. Initially, the waiter brings six different pizzas and gives Alfonsa the Pepperoni, Bianca the Romana, Claudia the Neapolitana and Erika the Stagioni. The other two pizzas are put in the middle of the table. From this initial matching, use the maximum matching algorithm to obtain a complete matching so that every girl gets a pizza that she likes. List your complete matching.

2 A father is going to give each of his five daughters: Grainne ( \(G\) ), Kath ( \(K\) ), Mary ( \(M\) ), Nicola ( \(N\) ) and Stella ( \(S\) ), one of the five new cars that he has bought: an Audi ( \(A\) ), a Ford Focus ( \(F\) ), a Jaguar ( \(J\) ), a Peugeot ( \(P\) ) and a Range Rover ( \(R\) ). The daughters express preferences for the car that they would like to be given, as shown in the table.

1. Show all these preferences on a bipartite graph.
2. Initially the father allocates the Peugeot to Kath, the Jaguar to Mary, and the Audi to Nicola. Demonstrate, by using alternating paths from this initial matching, how each daughter can be matched to a car which is one of her preferences.
   (6 marks)

1 Five people, \(A , B , C , D\) and \(E\), are to be matched to five tasks, 1, 2, 3, 4 and 5. The table shows which tasks each person can do.

1. Show this information on a bipartite graph.
2. Initially \(A\) is matched to task 3, \(B\) to task 4, \(C\) to task 2 and \(E\) to task 5 . Use an alternating path from this initial matching to find a complete matching.

1 Six people, \(A , B , C , D , E\) and \(F\), are to be matched to six tasks, \(1,2,3,4,5\) and 6 . The following adjacency matrix shows the possible matching of people to tasks.

1. Show this information on a bipartite graph.
2. At first \(F\) insists on being matched to task 4. Explain why, in this case, a complete matching is impossible.
3. To find a complete matching \(F\) agrees to be assigned to either task 4 or task 5. Initially \(B\) is matched to task 3, \(C\) to task 6, \(E\) to task 2 and \(F\) to task 4.
   From this initial matching, use the maximum matching algorithm to obtain a complete matching. List your complete matching.

1 Five people, \(A , B , C , D\) and \(E\), are to be allocated to five tasks, 1, 2, 3, 4 and 5 . The following bipartite graph shows the tasks that each person is able to undertake. \includegraphics[max width=\textwidth, alt={}, center]{5ee6bc88-6343-4ee6-8ecd-c13868d77049-02_441_437_699_797}

1. Represent this information in an adjacency matrix.
2. Initially, \(A\) is allocated to task 3, \(B\) to task 2 and \(C\) to task 4.
   1. Demonstrate, by using an alternating-path algorithm from this initial matching, how each person can be allocated to a different task.
   2. Find a different allocation of people to tasks.

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]

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]

This question should be answered on the sheet provided. There are 5 computers in an office, each of which must be dedicated to a single application. The computers have different specifications and the following table shows which applications each computer is capable of running.

1. Draw a bipartite graph to model this situation. [1 mark]

Initially it is decided to run the Office application on computer \(F\), Animation on computer \(H\), and Data on computer \(I\).

1. Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied. [9 marks]
2. Computer \(H\) is upgraded to allow it to run CAD. Find an alternative matching to that found in part (b). [3 marks]

Find an expression for the number of edges in the complete bipartite graph, \(K_{m,n}\) Circle your answer. [1 mark] \(\frac{m}{n}\) \quad\quad \(m - n\) \quad\quad \(m + n\) \quad\quad \(mn\)

A planar graph \(G\) is described by the adjacency matrix below. $$\begin{pmatrix} 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}$$

1. Draw the graph \(G\). [1]
2. Use Euler's formula to verify that there are four regions. Identify each region by listing the vertices that define it. [3]
3. Explain why graph \(G\) cannot have a Hamiltonian cycle that includes the edge \(AB\). Deduce how many Hamiltonian cycles graph \(G\) has. [4]

A colouring algorithm is given below. STEP 1: Choose a vertex, colour this vertex using colour 1. STEP 2: If all vertices are coloured, STOP. Otherwise use colour 2 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 1. STEP 3: If all vertices are coloured, STOP. Otherwise use colour 1 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 2. STEP 4: Go back to STEP 2.

1. Apply this algorithm to graph \(G\), starting at \(E\). Explain how the colouring shows you that graph \(G\) is not bipartite. [2]

By removing just one edge from graph \(G\) it is possible to make a bipartite graph.

1. Identify which edge needs to be removed and write down the two sets of vertices that form the bipartite graph. [2]

Graph \(G\) is augmented by the addition of a vertex \(X\) joined to each of \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\).

1. Apply Kuratowski's theorem to a contraction of the augmented graph to explain how you know that the augmented graph has thickness 2. [4]