7.02r Graph modelling: model and solve problems using graphs

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 bipartite graph shows the tasks that each of the people is able to undertake. \includegraphics[max width=\textwidth, alt={}, center]{1258a6d3-558a-46dc-a916-d71f71b175ff-02_1003_547_740_737}

1. Represent this information in an adjacency matrix.
2. Initially, \(B\) is assigned to task 4, \(C\) to task 3, \(D\) to task 1, \(E\) to task 5 and \(F\) to task 6. By using an algorithm from this initial matching, find a complete matching.
   (3 marks)

1 Six people, Andy, Bob, Colin, Dev, Eric and Faisal, are to be allocated to six tasks, \(1,2,3,4,5\) and 6 . The following table shows the tasks that each person is able to undertake.

1. Represent this information on a bipartite graph.
2. Initially, Bob is allocated to task 1, Colin to task 3, Dev to task 5 and Eric to task 2. Demonstrate, by using an alternating path algorithm from this initial matching, how each person can be allocated to a different task.

1 A graph is obtained from a solid by producing a vertex for each exterior face. Vertices in the graph are connected if their corresponding faces in the original solid share an edge. The diagram shows a solid followed by its graph. The solid is made up of two cubes stacked one on top of the other. This solid has 10 exterior faces, which correspond to the 10 vertices in the graph. (Note that in this question it is the exterior faces of the cubes that are being counted.) \includegraphics[max width=\textwidth, alt={}, center]{3239d012-5699-4789-ba64-f1295f4b4642-2_455_309_571_653} \includegraphics[max width=\textwidth, alt={}, center]{3239d012-5699-4789-ba64-f1295f4b4642-2_444_286_573_1135}

1. Draw the graph for a cube.
2. Obtain the number of vertices and the number of edges for the graph of three cubes stacked on top of each other. \includegraphics[max width=\textwidth, alt={}, center]{3239d012-5699-4789-ba64-f1295f4b4642-2_643_305_1302_881}

4 The table defines a network in which the numbers represent lengths.

1. Draw the network.
2. Use Dijkstra's algorithm to find the shortest paths from A to each of the other vertices. Give the paths and their lengths.
3. Draw a new network containing all of the edges in your shortest paths, and find the total length of the edges in this network.
4. Find a minimum connector for the original network, draw it, and give the total length of its edges.
5. Explain why the method defined by parts (i), (ii) and (iii) does not always give a minimum connector.

2 Fig. 2.1 represents the two floors of a house. There are 5 rooms shown, plus a hall and a landing, which are to be regarded as separate rooms. Each " × " represents an internal doorway connecting two rooms. The " ⊗ " represents the staircase, connecting the hall and the landing. \begin{figure}[h] \end{figure}

1. Draw a graph representing this information, with vertices representing rooms, and arcs representing internal connections (doorways and the stairs). What is the name of the type of graph of which this is an example?
2. A larger house has 12 rooms on two floors, plus a hall and a landing. Each ground floor room has a single door, which leads to the hall. Each first floor room has a single door, which leads to the landing. There is a single staircase connecting the hall and the landing. How many arcs are there in the graph of this house?
3. Another house has 12 rooms on three floors, plus a hall, a first floor landing and a second floor landing. Again, each room has a single door on to the hall or a landing. There is one staircase from the hall to the first floor landing, and another staircase joining the two landings. How many arcs are there in the graph of this house?
4. Fig. 2.2 shows the graph of another two-floor house. It has 8 rooms plus a hall and a landing. There is a single staircase. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{c429bfed-9241-409a-9cd5-9553bf16c9df-3_208_666_1896_694} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
   \end{figure} Draw a possible floor plan, showing internal connections.

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)

6. This question should be answered on the sheet provided. \begin{figure}[h] \end{figure} Figure 4 above shows a capacitated, directed network. The number on each arc indicates the capacity of that arc.

1. Calculate the values of cut \(C _ { 1 }\) and \(C _ { 2 }\).
2. Find the minimum cut and state its value.
   (2 marks) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-06_647_1303_1430_347} \captionsetup{labelformat=empty} \caption{Fig. 5}
   \end{figure} Figure 5 shows a feasible flow through the same network.
3. State the values of \(x , y\) and \(z\).
4. Using this as your initial flow pattern, use the labelling procedure to find a maximal flow. You should list each flow-augmenting route you use together with its flow. State how you know that you have found a maximal flow.
   (8 marks)

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six workers, Amrit (A), Bernard (B), Cameron (C), David (D), Emily (E) and Francis (F), to six tasks, 1, 2, 3, 4, 5 and 6

1. Explain why it is not possible to find a complete matching. Figure 2 shows an initial matching. Starting from this initial matching,
2. find the two alternating paths that start at C .
3. List the two improved matchings generated by using the two alternating paths found in (b). After training, task 5 is added to Bernard's possible allocation.
   Starting from either of the two improved matchings found in (c),
4. use the maximum matching algorithm to obtain a complete matching. You must list the additional alternating path that you use, and state the complete matching.
   (3)

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

1. Starting from this initial matching, use the maximum matching algorithm to find an improved matching. You must list the alternating path used and state your improved matching.
2. Explain why it is not possible to find a complete matching. Now, exactly one worker may be trained so that a complete matching becomes possible.
   Either worker A can be trained to do task 1 or worker E can be trained to do task 4.
3. Decide which worker, A or E , should be trained. Give a reason for your answer. You may now assume that the worker you identified in (c) has been trained.
4. Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You must list the alternating path used 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, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , to six tasks, \(1,2,3\), 4, 5 and 6. Each task must be assigned to only one worker and each worker must be assigned to exactly one task. Figure 2 shows an initial matching.

1. Starting from the given initial matching, use the maximum matching algorithm to find an alternating path from A to 4 . Hence find an improved matching. You should list the alternating path you use, and state your improved matching.
2. Explain why it is not possible to find a complete matching. After training, task 1 is added to worker A's possible allocations.
3. Starting from the improved matching found in (a), use the maximum matching algorithm to find a complete matching. You should list the alternating path you use, and state your complete matching.
   (3)

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Define the term 'bipartite graph'. Figure 1 shows the possible allocations of six people, A , B , C , D , E and F , to six activities, \(1,2,3\), 4, 5 and 6 Figure 2 shows an initial matching.
2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state your complete matching.

4. Six pupils, Ashley (A), Fran (F), Jas (J), Ned (N), Peter (P) and Richard (R), each wish to learn a musical instrument. The school they attend has six spare instruments; a clarinet (C), a trumpet (T), a violin (V), a keyboard (K), a set of drums (D) and a guitar (G). The pupils are asked which instruments they would prefer and their preferences are given in the table above. It is decided that each pupil must learn a different instrument and each pupil needs to be allocated to exactly one of their preferred instruments.

1. Using Diagram 1 in the answer book, draw a bipartite graph to show the possible allocations of pupils to instruments. Initially Ashley, Fran, Jas and Richard are each allocated to their first preference.
2. Show this initial matching on Diagram 2 in the answer book.
3. Starting with the initial matching from (b), apply the maximum matching algorithm once to find an improved matching. You must state the alternating path you use and give your improved matching.
4. Explain why a complete matching is not possible. Fran decides that as a third preference she would like to learn to play the guitar. Peter decides that as a second preference he would like to learn to play the drums.
5. Starting with the improved matching found in (c), use the maximum matching algorithm to obtain a complete matching. You must state the alternating path you use and your complete matching.

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} A delivery firm has six vans, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E }\) and F , available for six deliveries, \(1,2,3,4,5\) and 6 . Each van must be assigned to just one delivery. The bipartite graph shown in Figure 1 shows the possible matchings and Figure 2 shows an initial matching. A complete matching is required, starting from the given initial matching.

1. Explain why it is necessary to use the maximum matching algorithm twice. There are three possible alternating paths that start at either D or B . One of these is $$D - 2 = A - 3 = F - 6 = E - 5$$
2. Find the other two alternating paths.
3. List the improved matching generated by using the alternating path $$D - 2 = A - 3 = F - 6 = E - 5$$
4. Starting from the improved matching found in (c), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use and your complete matching.

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Define the term 'bipartite graph'. Figure 1 shows the possible allocations of five people, Larry (L), Monisha (M), Nina (N), Phil (P) and Theo (T), to five activities, A, B, C, D and E. Figure 2 shows an initial matching.
2. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path you use and state your complete matching.

5. \begin{figure}[h] \end{figure} Figure 3 shows the possible allocations of five workers, Cole (C), Dorothy (D), Harold (H), Richard (R) and Stephen (S), to five tasks, 1, 2, 3, 4 and 5. In an initial matching, each of three workers is allocated to a different task. For this initial matching, there are three possible alternating paths that start at C . One alternating path is $$C - 3 = S - 4 = D - 5$$ A second alternating path is $$\mathrm { C } - 1 = \mathrm { H } - 2$$

1. Use this information to deduce the initial matching.
2. Find the third alternating path that starts at C .
3. List the improved matching generated by using the alternating path \(\mathrm { C } - 3 = \mathrm { S } - 4 = \mathrm { D } - 5\)
4. Starting from the improved matching found in (c), use the maximum matching algorithm to obtain a complete matching. You must list the alternating path you use and the final matching.
   (3)

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.

2 Answer this question on the insert provided. A maze is constructed by building east/west and north/south walls so that there is a route from the entrance to the exit. The maze is shown in Fig. 2.1. \begin{figure}[h] \end{figure} On entering the maze Janet says "I'm always going to keep a hand in contact with the wall on the right." John says "I'm always going to keep a hand in contact with the wall on the left."

1. On the insert for this question show Janet's route through the maze. On the insert show John's route.
2. Will these strategies always find a way through such mazes? Justify your answer. In some mazes the objective is to get to a marked point before exiting. An example is shown in Fig. 2.2, where \(\mathbf { X }\) is the marked point. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-3_497_716_1672_669} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
   \end{figure} In the maze shown in Fig. 2.2 Janet's algorithm takes her to \(\mathbf { X }\). John's algorithm does not take him to \(\mathbf { X }\). John modifies his algorithm by saying that he will turn his back on the exit if he arrives there without visiting \(\mathbf { X }\). He will then move onwards, continuing to keep a hand in contact with the wall on the left.
3. Will this modified algorithm take John to the point \(\mathbf { X }\) in the maze in Fig. 2.2?
4. Will this modified algorithm take John to any marked point in the maze in Fig. 2.2? Justify your answer.

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.