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

4 The Head Teacher of a school is allocating five teachers, Amy ( \(A\) ), Ben ( \(B\) ), Celia ( \(C\) ), Duncan ( \(D\) ), and Erica ( \(E\) ), to the five posts of Head of Year 7, 8, 9, 10 and 11. The five teachers are asked which year(s) they would be willing to take. This information is shown below. Amy is willing to take Year 7 or Year 8 . Ben is willing to take Year 7, Year 8 or Year 10. Celia is willing to take Year 8, Year 9 or Year 11. Duncan will take only Year 9.
Erica will take only Year 11.

1. Show this information on a bipartite graph.
2. Initially the Head Teacher assigns Amy to Year 8, Ben to Year 10, Celia to Year 9 and Erica to Year 11. Demonstrate, by using an alternating path from this initial matching, how each teacher can be matched to a year that they are willing to take.

2

1. Draw a bipartite graph representing the following adjacency matrix.

   \cline { 2 - 7 } \multicolumn{1}{c|}{}	\(\mathbf { 1 }\)	\(\mathbf { 2 }\)	\(\mathbf { 3 }\)	\(\mathbf { 4 }\)	\(\mathbf { 5 }\)	\(\mathbf { 6 }\)
   \(\boldsymbol { A }\)	1	1	0	0	1	1
   \(\boldsymbol { B }\)	0	1	0	0	1	1
   \(\boldsymbol { C }\)	1	0	0	0	1	1
   \(\boldsymbol { D }\)	0	1	1	1	0	1
   \(\boldsymbol { E }\)	0	0	0	0	1	1
   \(\boldsymbol { F }\)	0	0	0	0	0	1

2. Given that \(A , B , C , D , E\) and \(F\) represent six people and that 1, 2, 3, 4, 5 and 6 represent six tasks to which they may be assigned, explain why a complete matching is impossible. \begin{verbatim} QUESTION PART REFERENCE \end{verbatim}

1

1. Draw a bipartite graph to represent the following adjacency matrix.

   	1	2	3	4	5
   A	0	0	0	0	1
   \(\boldsymbol { B }\)	0	0	0	1	1
   \(\boldsymbol { C }\)	0	1	0	1	1
   \(\boldsymbol { D }\)	0	0	0	1	1
   \(\boldsymbol { E }\)	1	1	1	0	1

2. If \(A , B , C , D\) and \(E\) represent five people and 1, 2, 3, 4 and 5 represent five tasks to which they are to be assigned, explain why a complete matching is impossible.
   (2 marks)

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. Initially, \(A\) is matched to task 3, \(B\) to task 4, \(C\) to task 2 and \(E\) to task 5. From this initial matching, use the maximum matching algorithm to obtain a complete matching. List your complete matching.

1

1. Draw a bipartite graph representing the following adjacency matrix.

   	1	2	3	4	5	6
   \(\boldsymbol { A }\)	1	0	1	0	1	0
   B	0	1	0	1	0	0
   \(\boldsymbol { C }\)	0	1	0	0	0	1
   \(\boldsymbol { D }\)	0	0	0	1	0	0
   E	0	0	1	0	1	1
   \(\boldsymbol { F }\)	0	0	0	1	1	0

2. Initially, \(A\) is matched to \(3 , B\) is matched to \(4 , C\) is matched to 2 , and \(E\) is matched to 5 . Use the maximum matching algorithm, from this initial matching, to find a complete matching. List your complete matching.
   

1 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 adjacency matrix shows the tasks that each of the people is able to undertake.

1. Represent this information in a bipartite graph.
2. Initially, \(A\) is assigned to task 3, \(B\) to task 2, \(C\) to task 4 and \(D\) to task 5 . Use an algorithm from this initial matching to find a maximum matching, listing your alternating paths.

2 A small party is held in a country house. There are 10 men and 10 women, and there are 10 dances. For each dance a number of pairings, each of one man and one woman, are formed. The same pairing can appear in more than one dance. A graph is to be drawn showing who danced with whom during the evening, ignoring repetitions.

1. Name the type of graph which is appropriate.
2. What is the maximum possible number of arcs in the graph? Dashing Mr Darcy dances with every woman except Elizabeth, who will have nothing to do with him. She dances with eight different men. Prince Charming only dances with Cinderella. Cinderella only dances with Prince Charming and with Mr Darcy. The three ugly sisters only have one dance each.
3. Add arcs to the graph in your answer book to show this information.
4. What is the maximum possible number of arcs in the graph?

1 Two students draw graphs to represent the numbers of pairs of shoes owned by members of their class. Andrew produces a bipartite graph, but gets it wrong. Barbara produces a completely correct frequency graph. Their graphs are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Draw a correct bipartite graph.
2. How many people are in the class?
3. How many pairs of shoes in total are owned by members of the class?
4. Which points on Barbara's graph may be deleted without losing any information? Charles produces the same frequency graph as Barbara, but joins consecutive points with straight lines.
5. Criticise Charles's graph.

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. The manager of an outdoor centre must staff each activity offered by the centre with an appropriately qualified instructor. The table below shows the sports for which each member of staff is qualified to supervise.

1. Draw a bipartite graph to model this situation. Initially the manager allocates Fatima, Gavin, Iain and Jane to supervise the first sport listed against their names in the table.
2. Starting from this matching, use the maximum matching algorithm to find a complete matching. Indicate clearly how you have applied the algorithm.
   (6 marks)

4. This question should be answered on the sheet provided. The Prime Minister is planning a reshuffle and the table indicates which posts each of the six ministers involved would be willing to accept.

1. Draw a bipartite graph to model this situation. Initially the Prime Minister matches Minister \(P\) to the post of Chancellor, \(Q\) to Foreign Secretary, \(R\) to Defence and \(T\) to Home Secretary.
2. Draw this initial matching.
3. Starting from this initial matching use the maximum matching algorithm to find a complete matching. Indicate clearly how the algorithm has been applied, listing any alternating paths used. Minister \(U\), on reflection, now expresses no interest in becoming Foreign Secretary.
4. Explain why no complete matching is now possible.
   (2 marks)

3. This question should be answered on the sheet provided. A firm of auditors is to place one trainee accountant at each of its five offices. These are situated in Dundee, Edinburgh, Glasgow and London. There are two offices in London, one of which is the company's Head Office. The table summarises the trainees' preferences.

1. Draw a bipartite graph to model this situation.
2. Explain why no complete matching is possible. Trainee \(T\) is persuaded that either office in London would be just as good for her personal development as the Edinburgh office.
3. Draw a second bipartite graph to model the changed situation. In an initial matching, trainee \(P\) is placed in the Dundee office, trainee \(R\) in the Glasgow office, and trainee \(S\) in the Edinburgh office.
4. Draw this initial matching.
5. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You must indicate how the algorithm has been applied, stating clearly the alternating paths you use and the final matching.
   (7 marks)

1 Arnie (A), Brigitte (B), Charles (C), Diana (D), Edward (E) and Faye (F) are moving into a home for retired Hollywood stars. They all still expect to be treated as stars and each has particular requirements. Arnie wants a room that can be seen from the road, but does not want a ground floor room; Brigitte wants a room that looks out onto the garden; Charles wants a ground floor room; Diana wants a room with a balcony; Edward wants a second floor room; Faye wants a room, with a balcony, that can be seen from the road. The table below shows the features of each of the six rooms available.

1. Draw a bipartite graph to show the possible pairings between the stars ( \(A , B , C , D , E\) and \(F\) ) and the rooms ( \(1,2,3,4,5\) and 6 ). Originally Arnie was given room 4, Brigitte was given room 3, Charles was given room 2, Diana was given room 5, Edward was given room 6 and Faye was given room 1.
2. Identify the star that has not been given a room that satisfies their requirements. Draw a second bipartite graph to show the incomplete matching that results when this star is not given a room.
3. Construct the shortest possible alternating path, starting from the star without a room and ending at the room that was not used, and hence find a complete matching between the stars and the rooms. Write a list showing which star should be given which room. When the stars view the rooms they decide that some are much nicer than others. Each star gives each room a value from 1 to 6 , where 1 is the room they would most like and 6 is the room they would least like. The results are shown below.

   \multirow{2}{*}{}	Room
   	1	2	3	4	5	6
   Arnie (A)	3	6	4	1	5	2
   Brigitte ( \(B\) )	5	3	2	4	1	6
   Charles (C)	2	1	3	4	5	6
   Diana (D)	5	4	1	3	2	6
   Edward ( \(E\) )	5	6	4	3	2	1
   Faye (F)	5	6	4	1	3	2

4. Apply the Hungarian algorithm to this table, reducing rows first, to find a minimum 'cost' allocation between the stars and the rooms. Write a list showing which star should be given which room according to this allocation. Write down the name of any star whose original requirements are not satisfied.

4 Anya \(( A )\), Ben \(( B )\), Connie \(( C )\), Derek \(( D )\) and Emma \(( E )\) work for a local newspaper. The editor wants them each to write a regular weekly article for the paper. The items needed are: problem page \(( P )\), restaurant review \(( R )\), sports news \(( S )\), theatre review \(( T )\) and weather report \(( W )\). Anya wants to write either the problem page or the restaurant review. She is given the problem page. Ben wants the restaurant review, the sports news or the theatre review. The editor gives him the restaurant review. Connie wants either the theatre review or the weather report. The editor gives her the theatre review. Derek wants the problem page, the sports news or the weather report. He is given the weather report. Emma is only interested in writing the problem page but this has already been given to Anya.

1. Draw a bipartite graph to show the possible pairings between the writers ( \(A , B , C , D\) and \(E\) ) and the articles ( \(P , R , S , T\) and \(W\) ). On your bipartite graph, show who has been given which article by the editor.
2. Construct the shortest possible alternating path, starting from Emma, to find a complete matching between the writers and the articles. Write a list showing which article each writer is given with this complete matching. When the writers send in their articles the editor assigns a sub-editor to each one to check it. The sub-editors can check at most one article each. The table shows how long, in minutes, each sub-editor would typically take to check each article.

   \multirow{8}{*}{Sub-editor}	\multirow{2}{*}{}	Article
   		\(P\)	\(R\)	\(S\)	\(T\)	\(W\)
   	Jeremy ( \(J\) )	56	56	51	57	58
   	Kath ( \(K\) )	53	52	53	54	54
   	Laura ( \(L\) )	57	55	52	58	60
   	Mohammed ( \(M\) )	59	55	53	59	57
   	Natalie ( \(N\) )	57	57	53	59	60
   	Ollie ( \(O\) )	58	56	51	56	57

   The editor wants to find the allocation for which the total time spent checking the articles is as short as possible.
3. Apply the Hungarian algorithm to the table, reducing rows first, to find an optimal allocation between the sub-editors and the articles. Explain how each table is formed and write a list showing which sub-editor should be assigned to which article. If each minute of sub-editor time costs \(\pounds 0.25\), calculate the total cost of checking the articles each week.

1 Andy ( \(A\) ), Beth ( \(B\) ), Chelsey ( \(C\) ), Dean ( \(D\) ) and Elly ( \(E\) ) have formed a quiz team. They have entered a quiz in which, as well as team questions, each of them must answer individual questions on a specialist topic. The specialist topics could be any of: food \(( F )\), geography \(( G )\), history \(( H )\), politics ( \(P\) ), science ( \(S\) ) and television ( \(T\) ). The team members do not know which five specialist topics will arise in the quiz. Andy wants to answer questions on either food or television; Beth wants to answer questions on geography, history or science; Chelsey wants to answer questions on geography or television; Dean wants to answer questions on politics or television; and Elly wants to answer questions on history or television.

1. Draw a bipartite graph to show the possible pairings between the team members and the specialist topics. In the quiz, the first specialist topic is food, and Andy is chosen to answer the questions. The second specialist topic is geography, and Beth is chosen. The next specialist topic is history, and Elly is chosen. The fourth specialist topic is science. Beth has already answered questions so Dean offers to try this round. The final specialist topic is television, and Chelsey answers these questions.
2. Draw a second bipartite graph to show these pairings, apart from Dean answering the science questions. Write down an alternating path starting from Dean to show that there would have been a better way to choose who answered the questions had the topics been known in advance. Write down which team member would have been chosen for each specialist topic in this case.
3. In a practice, although the other team members were able to choose topics that they wanted, Beth had to answer the questions on television. Write down which topic each team member answered questions on, and which topic did not arise.

1 Four friends, Amir (A), Bex (B), Cerys (C) and Duncan (D), are visiting a bird sanctuary. They have decided that they each will sponsor a different bird. The sanctuary is looking for sponsors for a kite \(( K )\), a lark \(( L )\), a moorhen \(( M )\), a nightjar \(( N )\), and an owl \(( O )\). Amir wants to sponsor the kite, the nightjar or the owl; Bex wants to sponsor the lark, the moorhen or the owl; Cerys wants to sponsor the kite, the lark or the owl; and Duncan wants to sponsor either the lark or the owl.

1. Draw a bipartite graph to show which friend wants to sponsor which birds. Amir chooses to sponsor the kite and Bex chooses the lark. Cerys then chooses the owl and Duncan is left with no bird that he wants.
2. Write down the shortest possible alternating path starting from the nightjar, and hence write down one way in which all four friends could have chosen birds that they wanted to sponsor.
3. List a way in which all four friends could have chosen birds they wanted to sponsor, with the owl not being chosen.

1 Five film studies students need to review five different films for an assignment, but only have one evening left before the assignment is due in. They decide that they will share the work out so that each of them reviews just one film. Jack \(( J )\) wants to review a horror movie; Karen \(( K )\) wants to review an animated film; Lee \(( L )\) wants to review a film that is suitable for family viewing; Mark ( \(M\) ) wants to review an action adventure film and Nikki ( \(N\) ) wants to review anything that is in 3D. The film "Somewhere" ( \(S\) ) has been classified as a horror movie and is being shown in 3D; "Tornado Terror" ( \(T\) ) has been classified as an action adventure film that is suitable for family viewing; "Underwater" \(( U )\) is an animated action adventure film; "Vampires" ( \(V\) ) is an animated horror movie that is suitable for family viewing and "World" ( \(W\) ) is an animated film.

1. Draw a bipartite graph to show which student ( \(J , K , L , M , N\) ) wants to review which films ( \(S , T , U\), \(V , W\) ). Initially Jack says that he will review "Somewhere", Karen then chooses "Underwater" and Lee chooses "Tornado Terror", but this would leave both Mark and Nikki with films that they do not want.
2. Write down the shortest possible alternating path starting from Nikki, and hence write down an improved, but still incomplete, matching.
3. From this incomplete matching, write down the shortest possible alternating path starting from "World", and hence write down a complete matching between the students and the films.
4. Show that this is the only possible complete matching between the students and the films.

1 A TV soap opera has five main characters, Alice ( \(A\) ), Bob ( \(B\) ), Charlie ( \(C\) ), Dylan ( \(D\) ) and Etty ( \(E\) ). A different character is scheduled to play the lead in each of the next five episodes. Alice, Dylan and Etty are all in the episode about the fire ( \(F\) ), but Bob and Charlie are not. Alice and Bob are the only main characters in the episode about the gas leak ( \(G\) ). Alice, Charlie and Etty are the only main characters in the episode about the house break-in (H). The episode about the icy path (I) stars Alice and Charlie only. The episode about the jail break ( \(J\) ) does not star any of the main characters who were in the episodes about the fire or the house break-in.

1. Draw a bipartite graph to show which main characters ( \(A , B , C , D , E\) ) are in which of the next five episodes \(( F , G , H , I , J )\). The writer initially decides to make Alice play the lead in the episode about the fire, Bob in the episode about the gas leak and Charlie in the episode about the house break-in.
2. Write down the shortest possible alternating path starting from Dylan. Hence draw the improved, but still incomplete, matching that results.
3. From this incomplete matching, write down the shortest possible alternating path starting from the character who still has no leading part allocated. Hence draw the complete matching that results.
4. By starting with the episode about the jail break, explain how you know that this is the only possible complete matching between the characters and the episodes.

4 The complete bipartite graph \(K _ { 3,4 }\) connects the vertices \(\{ 2,4,6 \}\) to the vertices \(\{ 1,3,5,7 \}\).

1. How many arcs does the graph \(K _ { 3,4 }\) have?
2. Deduce how many different paths are there that pass through each of the vertices once and once only. The direction of travel of the path does not matter. The arcs are weighted with the product of the numbers at the vertices that they join.
3. (a) Use an appropriate algorithm to find a minimum spanning tree for this network.
   (b) Give the weight of the minimum spanning tree.

4 Graph G is a simply connected Eulerian graph with 4 vertices.

1. 1. Explain why graph G cannot be a complete graph.
   2. Determine the number of arcs in graph G, explaining your reasoning.
   3. Show that graph G is a bipartite graph. Graph H is a digraph with 4 vertices and no undirected arcs. The adjacency matrix below shows the number of arcs that directly connect each pair of vertices in digraph H . From \begin{table}[h]
      \captionsetup{labelformat=empty} \caption{To}

      	A	B	C	D
      A	0	1	0	1
      B	0	0	2	0
      C	2	1	0	1
      D	0	1	1	0

      \end{table}
2. 1. Write down a feature of the adjacency matrix that shows that H has no loops.
   2. Find the number of \(\operatorname { arcs }\) in H .
   3. Draw a possible digraph H .
   4. Show that digraph H is semi-Eulerian by writing down a suitable trail.

4 One of these graphs is isomorphic to \(\mathrm { K } _ { 2,3 }\). \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Explain how you know that each of the other graphs is not isomorphic to \(\mathrm { K } _ { 2,3 }\). The arcs of the complete graph \(\mathrm { K } _ { 5 }\) can be partitioned as the complete bipartite graph \(\mathrm { K } _ { 2,3 }\) and a graph G.
2. Draw the graph G.
3. Explain carefully how you know that the graph \(\mathrm { K } _ { 5 }\) has thickness 2 . The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, \(\alpha\) and \(\beta\). STEP 1 Choose a vertex and assign it colour \(\alpha\).
   STEP 2 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour \(\beta\) to each vertex that is adjacent to a vertex with colour \(\alpha\). STEP 3 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour \(\alpha\) to each vertex that is adjacent to a vertex with colour \(\beta\). STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured.
   STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite. Otherwise the graph is not bipartite. STEP 6 Stop.
4. Apply this algorithm to graph A, starting with the vertex in the top left corner, to determine whether graph A is bipartite or not. A measure of the efficiency of the colouring algorithm is given by the number of passes through STEP 4.
5. Write down how many passes through STEP 4 are needed for the bipartite graph \(\mathrm { K } _ { 2,3 }\). The worst case is when the graph is a path that starts at one vertex and ends at another, having passed through each of the other vertices once.
6. What can you deduce about the efficiency of the colouring algorithm in this worst case? The colouring algorithm is used on two graphs, X and Y . It takes 10 seconds to run for graph X and 60 seconds to run for graph Y. Graph X has 1000 vertices.
7. Estimate the number of vertices in graph Y . A different algorithm has efficiency \(\mathrm { O } \left( 2 ^ { n } \right)\). This algorithm takes 10 seconds to run for graph X .
8. Explain why you would expect this algorithm to take longer than 60 seconds to run for graph Y .

1. (a) Define the term 'bipartite graph'.

Six workers, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , are to be matched to six tasks, 1, 2, 3, 4, 5 and 6 The table below shows the tasks that each worker is able to do. (b) Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocation of workers to tasks.
(1) Initially, workers \(\mathrm { A } , \mathrm { C } , \mathrm { E }\) and F are allocated to tasks 2, 4, 5 and 6 respectively.
(c) Starting from the given initial matching, apply the maximum matching algorithm to obtain a complete matching. You must state the alternating paths that you use, and state your improved matching after each iteration.

2. Six film critics, Bronwen (B), Greg (G), Jean (J), Mick (M), Renee (R) and Susan (S), must see six films, \(1,2,3,4,5\) and 6 . Each critic must attend a different film and each critic needs to be allocated to exactly one film. The critics are asked which films they would prefer and their preferences are given in the table below.

1. Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocations of critics to their preferred films. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{049de386-42a9-4f16-8be3-9324382e4988-03_616_524_1114_767} \captionsetup{labelformat=empty} \caption{Figure 2}
   \end{figure} Figure 2 shows an initial matching.
2. Starting from the given initial matching, apply the maximum matching algorithm to find an alternating path from G to 3 . Hence find an improved matching. You should list the alternating path that you use, and state your improved matching.
   (3)
3. Starting with the improved matching found in (b), apply the maximum matching algorithm to obtain a complete matching. You should list the alternating path that you use, and state your complete matching.

3. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six workers, Andrea (A), Baasim (B), Charlie (C), Deirdre (D), Ean (E) and Fen-Fang (F), to six tasks, 1, 2, 3, 4, 5 and 6.

1. Write down the technical name given to the type of graph shown in Figure 1.
   (1) Figure 2 shows an initial matching.
2. Starting from the initial matching, use the maximum matching algorithm to find a complete matching. You must list the alternating path you used and state your complete matching.
3. State a different complete matching from the one found in (b).
4. By considering the workers who must be allocated to particular tasks, explain why there are exactly two different complete matchings.

3. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Define the terms

1. bipartite graph,
2. matching. Figure 3 shows the possible allocations of six people, Charles (C), Emily (E), George (G), Harriet (H), Jack (J) and Shen (S), to six tasks, 1, 2, 3, 4, 5 and 6. Figure 4 shows an initial matching.
3. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path you use and state your improved matching. Emily has task 5 added to her possible allocations and Harriet has task 3 added to her possible allocations.
4. Starting from the improved matching found in part (c), use the maximum matching algorithm to find a complete matching. You should list the alternating path you use and state your improved matching.
   (3)
   (Total 10 marks)