7.02r Graph modelling: model and solve problems using graphs

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]

6

1. The network shows a flow from \(S\) to \(T\) along a system of pipes, with the capacity in litres per second indicated on each edge. \includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-14_510_936_411_552}
   1. Show that the value of the cut shown on the diagram is 36 .
   2. The cut shown on the diagram can be represented as \(\{ S , B \} , \{ A , C , T \}\). Complete the table below to give the value of each of the 8 possible cuts.

      Cut		Value
      \(\{ S \}\)	\(\{ A , B , C , T \}\)	30
      \(\{ S , A \}\)	\(\{ B , C , T \}\)	29
      \(\{ S , B \}\)	\(\{ A , C , T \}\)	36
      \(\{ S , C \}\)	\(\{ A , B , T \}\)	33
      \(\{ S , A , B \}\)	\(\{ C , T \}\)
      \(\{ S , A , C \}\)	\(\{ B , T \}\)
      \(\{ S , B , C \}\)	\(\{ A , T \}\)
      \(\{ S , A , B , C \}\)	\(\{ T \}\)	30

   3. State the value of the maximum flow through the network, giving a reason for your answer. Maximum flow is \(\_\_\_\_\) because \(\_\_\_\_\)
   4. Indicate on the diagram below a possible flow along each edge corresponding to this maximum flow. \includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-15_469_933_406_550}
2. The capacities along \(S C\) and along \(A T\) are each increased by 4 litres per second.
   1. Using your values from part (a)(iv) as the initial flow, indicate potential increases and decreases on the diagram below and use the labelling procedure to find the new maximum flow through the network. You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the diagram. \includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-15_470_935_1315_260}

      Path	Additional Flow

   2. Use your results from part (b)(i) to illustrate the flow along each edge that gives this new maximum flow, and state the value of the new maximum flow. New maximum flow is \(\_\_\_\_\) \includegraphics[max width=\textwidth, alt={}, center]{d0902228-7041-4449-9ccb-770352ce6bef-15_474_933_2078_550}

3 The diagram below shows a network of pipes with source \(A\) and \(\operatorname { sink } J\). The capacity of each pipe is given by the number on each edge. \includegraphics[max width=\textwidth, alt={}, center]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-08_816_1280_443_386}

1. Find the values of the cuts \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\).
2. Find by inspection a flow of 60 units, with flows of 25,10 and 25 along \(H J , G J\) and \(I J\) respectively. Illustrate your answer on Figure 1.
3. 1. On a certain day the section \(E H\) is blocked, as shown on Figure 2. Find, by inspection or otherwise, the maximum flow on this day and illustrate your answer on Figure 2.
   2. Show that the flow obtained in part (c)(i) is maximal. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 1} \includegraphics[alt={},max width=\textwidth]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-09_595_1065_376_475}
      \end{figure} (c) \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 2} \includegraphics[alt={},max width=\textwidth]{c2b62fee-d320-4701-a5bb-b2e4b8cc0952-09_617_1061_1142_477}
      \end{figure} Maximum flow = \(\_\_\_\_\)

6 The network shows a system of pipes with lower and upper capacities for each pipe in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{34de3f03-a275-44fb-88b2-b88038bcec97-22_817_744_397_648}

1. 1. Find the value of the cut \(X\).
   2. Hence state what can be deduced about the maximum flow from \(A\) to \(H\).
2. Figure 3 shows a partially completed diagram for a feasible flow of 28 litres per second from \(A\) to \(H\). Indicate, on Figure 3, the flows along the edges \(B D , B E\) and \(C D\).
3. 1. Using your feasible flow from part (b) as an initial flow, indicate potential increases and decreases of the flow along each edge on Figure 4.
   2. Use flow augmentation on Figure 4 to find the maximum flow from \(A\) to \(H\). You should indicate any flow augmenting paths in the table and modify the potential increases and decreases of the flow on the network.
   3. State the maximum flow and indicate a maximum flow on Figure 5. \section*{Answer space for question 6} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 3} \includegraphics[alt={},max width=\textwidth]{34de3f03-a275-44fb-88b2-b88038bcec97-23_682_689_312_397}
      \end{figure} \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{34de3f03-a275-44fb-88b2-b88038bcec97-23_935_1477_1037_365}
      \end{figure} Figure 5
      \includegraphics[max width=\textwidth, alt={}]{34de3f03-a275-44fb-88b2-b88038bcec97-24_2032_1707_219_153}

1. \begin{figure}[h] \end{figure} Figure 1 shows a network of roads connecting six villages \(A , B , C , D , E\) and \(F\). The lengths of the roads are given in km .

1. Complete the table in the answer booklet, in which the entries are the shortest distances between pairs of villages. You should do this by inspection. The table can now be taken to represent a complete network.
2. Use the nearest-neighbour algorithm, starting at \(A\), on your completed table in part (a). Obtain an upper bound to the length of a tour in this complete network, which starts and finishes at \(A\) and visits every village exactly once.
   (3)
3. Interpret your answer in part (b) in terms of the original network of roads connecting the six villages.
   (1)
4. By choosing a different vertex as your starting point, use the nearest-neighbour algorithm to obtain a shorter tour than that found in part (b). State the tour and its length.
   (2)

\includegraphics{figure_3} \includegraphics{figure_4} Figure 3 shows the possible allocations of six people, Amelia, Charlie, Ellie, Gemma, Jimmy and Saskia, to six tasks, 1, 2, 3, 4, 5 and 6. Figure 4 shows an initial matching.

1. Use the maximum matching algorithm once to find an improved matching. You must state the alternating path used and your improved matching. [3]
2. Explain why a complete matching is not possible. [2] After training, Jimmy can be assigned to tasks 4 or 5 and Ellie to tasks 2, 3, 5 or 6.
3. Starting with your current maximal matching, use the maximum matching algorithm to obtain a complete matching. You must state the alternating path used and your final matching. [3]

(Total 8 marks)

Answer this question on the insert provided. Jenny needs to travel to London to arrive in time for a morning meeting. The graph below represents the various travel options that are available to her. \includegraphics{figure_3} It takes Jenny 120 minutes to drive from her home to the local airport and check in (arc \(JA\)). The journey from the local airport to Gatwick takes 80 minutes. From Gatwick to the underground station takes 60 minutes, and walking from the underground station to the meeting venue takes 15 minutes. Alternatively, Jenny could get a taxi from Gatwick to the meeting venue; this takes 80 minutes. It takes Jenny 15 minutes to drive from her house to the train station. Alternatively, she can walk to the bus stop, which takes 5 minutes, and then get a bus to the train station, taking another 20 minutes. From the train station to Paddington takes 300 minutes, and from Paddington to the underground station takes a further 20 minutes. Alternatively, Jenny could walk from Paddington to the meeting venue, taking 30 minutes. Jenny can catch a coach from her local bus stop to Victoria, taking 400 minutes. From Victoria she can either travel to the underground station, which takes 10 minutes, or she can walk to the meeting venue, which takes 15 minutes. The final option available to Jenny is to drive to a friend's house, taking 240 minutes, and then continue the journey into London by train. The journey from her friend's house to Waterloo takes Jenny 30 minutes. From here she can either go to the underground station, which takes 20 minutes, or walk to the meeting venue, which takes 40 minutes.

1. Weight the arcs on the graph in the insert to show these times. Apply Dijkstra's algorithm, starting from \(J\), to give a permanent label and order of becoming permanent at each vertex. Stop when you have assigned a permanent label to vertex \(M\). Write down the route of the shortest path from \(J\) to \(M\). [9]
2. What does the value of the permanent label at \(M\) represent? [1]
3. Give two reasons why Jenny might choose to use a different route from \(J\) to \(M\). [2]