7.02f Bipartite test: colouring argument

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}

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 A connected graph is shown below. \includegraphics[max width=\textwidth, alt={}, center]{50697293-6cdc-475f-981f-71a351b0ff5a-4_442_954_296_246}

1. Write down a path through exactly 7 of the vertices.
2. Write down a cycle through exactly 6 of the vertices.
3. Explain why Ore's theorem cannot be used to decide whether or not this graph is Hamiltonian.
4. Prove that the graph is not Hamiltonian. 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, (1) and (2). STEP 1 Choose a vertex and assign it colour (1).
   STEP 2 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour (2) to each vertex that is adjacent to a vertex with colour (1).
   STEP 3 If any vertex is adjacent to another vertex of the same colour, stop. Otherwise assign colour (1) to each vertex that is adjacent to a vertex with colour (2).
   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, output the word "bipartite".
   Otherwise the graph is not bipartite, output the words "not bipartite".
5. Use this algorithm, starting at vertex A, to determine whether the graph is bipartite, or not. [2
6. Explain what Kuratowski's theorem tells you about the graph.
7. Show that the graph has thickness 2 .

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.

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six people, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, \(1,2,3\), 4, 5 and 6

1. Write down the technical name given to the type of diagram shown in Figure 1. Figure 2 shows an initial matching.
2. Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating paths you use and state your improved matching after each iteration.
   (6)

4. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Six airline pilots, Alice, Dan, Miya, Phil, Sophie and Tom, are to be assigned to six flights, 1, 2, 3, 4, 5 and 6. A bipartite graph showing the possible allocations is shown in Figure 2, and an initial matching is given in Figure 3. The maximum matching algorithm will be used to obtain a complete matching.

1. Starting from A, find an alternating path that leads to an improved matching and list the improved matching that it gives.
   (3)
2. Using the improved matching found in part (a) as the new initial matching, find a complete matching. You must state any alternating paths you use and list your final complete matching.

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.

At Tesafe supermarket there are 5 trainee staff, Homan \((H)\), Jenna \((J)\), Mary \((M)\), Tim \((T)\) and Yoshie \((Y)\). They each must spend one week in each of 5 departments, Delicatessen \((D)\), Frozen foods \((F)\), Groceries \((G)\), Pet foods \((P)\), Soft drinks \((S)\). Next week every department requires exactly one trainee. The table below shows the departments in which the trainees have yet to spend time. Initially \(H\), \(J\), \(M\) and \(T\) are allocated to the first department in their list.

1. Draw a bipartite graph to model this situation and indicate the initial matching in a distinctive way. [2] Starting from this matching,
2. use the maximum matching algorithm to find a complete matching. You must make clear your alternating path and your complete matching. [4]

Define the terms

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

\includegraphics{figure_1} The bipartite graph in Figure 1 shows a mapping between six people, Andy (\(A\)), David (\(D\)), Joan (\(J\)), Preety (\(P\)), Sally (\(S\)) and Trevor (\(T\)), and six tasks 1, 2, 3, 4, 5 and 6. The initial matching is \(A\) to 2, \(D\) to 1, \(J\) to 3 and \(P\) to 4.

1. Indicate this initial matching in a distinctive way on the bipartite graph drawn in the answer book. [1]
2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. List clearly the alternating paths you use. [5]