7.02b Graph terminology: tree, simple, connected, simply connected

3 The diagram shows three sets, A, B and C. Each region of the diagram contains at least one element. The diagram shows that B is a subset of \(\mathrm { A } , \mathrm { C }\) is a subset of A , and that B shares at least one element with C . \includegraphics[max width=\textwidth, alt={}, center]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_410_615_342_726} The two graphs below give information about the three sets \(\mathrm { A } , \mathrm { B }\) and C . The first graph shows the relation 'is a subset of' and the second graph shows the relation 'shares at least one element with'. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. Draw two graphs to represent the sets \(\mathrm { X } , \mathrm { Y }\) and Z shown in the following diagram. \includegraphics[max width=\textwidth, alt={}, center]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_415_613_1388_731}
2. Draw a diagram to represent the sets \(\mathrm { P } , \mathrm { Q }\) and R for which both of the following graphs apply. \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_202_264_1980_621} \captionsetup{labelformat=empty} \caption{'is a subset of'}
   \end{figure} \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_200_260_1982_1155} \captionsetup{labelformat=empty} \caption{'shares at least one element with'}
   \end{figure}

3 The adjacency graph of a cube \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_106_108_214_735}
is shown. Vertices on the graph represent faces of the cube. Two vertices are connected by an arc if the corresponding faces of the cube share an edge. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_401_464_246_1334} The second graph is the complement of the adjacency graph, i.e. the graph that consists of the same vertices together with the arcs that are not in the adjacency graph. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_403_464_737_1334} Throughout this question we wish to colour solids so that two faces that share an edge have different colours. The second graph shows that the minimum number of colours required for a cube is three, one colour for the top and base, one for the front and back, and one for the left and right.

1. Draw the adjacency graph for a square-based pyramid, and draw its complement. Hence find the minimum number of colours needed to colour a square-based pyramid. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_161_202_1434_1548}
2. (A) Draw the adjacency graph for an octahedron, and draw its complement.
   (B) An octahedron can be coloured using just two colours. Explain how this relates to the complement of the adjacency graph. \includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_227_205_1731_1548}

4. The following matrix gives the capacities of the pipes in a system.

1. Represent this information as a digraph.
2. Find the minimum cut, expressing it in the form \(\{ \} \mid \{ \}\), and state its value.
3. Starting from having no flow in the system, use the labelling procedure to find a maximal flow through the system. You should list each flow-augmenting route you use, together with its flow.
4. Explain how you know that this flow is maximal.

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.

1 Six students are choosing their tokens for a board game. The bipartite graph in Fig. 1 shows which token each student is prepared to have. \begin{figure}[h] \end{figure} Initially Ezra takes the flat iron, Jonah the old boot, Lily the racing car and Molly the scottie dog. This leaves Adele and Noah with tokens that they do not want. This incomplete matching is shown in Fig. 2 below. \begin{table}[h] \end{table}

1. Write down the shortest possible alternating path that starts at A and finishes at either B or T . Hence write down a matching that only excludes Noah and one of the tokens.
2. Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at N and finishes at whichever of B and T has still not been taken. Hence write down a complete matching between the students and the tokens.
3. By starting at B on Fig. 1, show that there are exactly two complete matchings between the students and the tokens.

1 The infamous fictional detective Agatha Parrot is working on a case and decides to invite each of the four suspects to visit her for tea. She will invite one suspect to tea on Sunday (S), another on Monday (M), another on Tuesday (T) and the final suspect on Wednesday (W).

• Beryl Batty (B) could come to tea on Sunday or Monday but she is away for a few days after that.
• Colonel Chapman (C) could come to tea on Sunday or Tuesday, but is busy on the other days.
• Dimitri Delacruz (D) could only come to tea on Monday or Wednesday.
• Erina El-Sayed (E) could come to tea on Sunday, Monday or Tuesday, but will be away on Wednesday.
  1. Draw a bipartite graph to show which suspects could come to tea on which day.

Agatha initially intended to invite Beryl to tea on Sunday, Dimitri on Monday and Colonel Chapman on Tuesday. However this would mean that Erina would not be able to come to tea, as she will be away on Wednesday.

Draw a second bipartite graph to show this incomplete matching.

Working from this incomplete matching, find the shortest possible alternating path, starting at Erina, to achieve a breakthrough. Write down which suspect is invited on which day with this matching. Before issuing invitations, Agatha overhears Erina making arrangements to go to tea with the vicar one day. She knows that Erina will not want to accept two invitations to tea on the same day. Unfortunately, Agatha does not know which day Erina has arranged to go to tea with the vicar, other than that it was not Sunday. Agatha invites Erina to tea on Sunday and the others when she can. After having tea with all four suspects she considers what they have said and invites them all back on Friday. She then accuses the person who came to tea on Monday of being guilty.

Who does Agatha accuse of being guilty?

1 Josh is making a calendar. He has chosen six pictures, each of which will represent two months in the calendar. He needs to choose which picture to use for each two-month period. The bipartite graph in Fig. 1 shows for which months each picture is suitable. \begin{figure}[h] \end{figure} Initially Josh chooses the sailing ships for March/April, the sunset for July/August, the snow scene for November/December and the swans for May/June. This incomplete matching is shown in Fig. 2 below. \begin{table}[h] \end{table}

1. Write down the shortest possible alternating path that starts at (JF) and finishes at either (2) or (4). Hence write down a matching that only excludes (SO) and one of the pictures.
2. Working from the incomplete matching found in part (i), write down the shortest possible alternating path that starts at (SO) and finishes at whichever of (2) and (4) has still not been matched. Hence write down a complete matching between the pictures and the months.
3. Explain why three of the arcs in Fig. 1 must appear in the graph of any complete matching. Hence find a second complete matching.

1 [Answer this question on the insert provided.]
Six neighbours have decided to paint their houses in bright colours. They will each use a different colour.

• Arthur wants to use lavender, orange or tangerine.
• Bridget wants to use lavender, mauve or pink.
• Carlos wants to use pink or scarlet.
• Davinder wants to use mauve or pink.
• Eric wants to use lavender or orange.
• Ffion wants to use mauve.

Arthur chooses lavender, Bridget chooses mauve, Carlos chooses pink and Eric chooses orange. This leaves Davinder and Ffion with colours that they do not want.

1. Draw a bipartite graph on the insert, showing which neighbours ( \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) ) want which colours (L, M, O, P, S, T). On a separate diagram on the insert, show the incomplete matching described above.
2. By constructing alternating paths obtain the complete matching between the neighbours and the colours. Give your paths and show your matching on the insert.
3. Fill in the table on the insert to show how the Hungarian algorithm could have been used to find the complete matching. (You do not need to carry out the Hungarian algorithm.)

5 There are three non-isomorphic trees on five vertices.

1. Draw an example of each of these trees.
2. State three properties that must be satisfied by the vertex orders of a tree on six vertices.
3. List the five different sets of possible vertex orders for trees on six vertices.
4. Draw an example of each type listed in part (iii).

2. Kruskal's algorithm finds a minimum spanning tree for a connected graph with \(n\) vertices.

1. Explain the terms
   1. connected graph,
   2. tree,
   3. spanning tree.
2. Write down, in terms of \(n\), the number of arcs in the minimum spanning tree. The table below shows the lengths, in km, of a network of roads between seven villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F }\) and G .

   	A	B	C	D	E	F	G
   A	-	17	-	19	30	-	-
   B	17	-	21	23	-	-	-
   C	-	21	-	27	29	31	22
   D	19	23	27	-	-	40	-
   E	30	-	29	-	-	33	25
   F	-	-	31	40	33	-	39
   G	-	-	22	-	25	39	-

3. Complete the drawing of the network on Diagram 1 in the answer book by adding the necessary arcs from vertex C together with their weights.
4. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree.
5. State the weight of the minimum spanning tree.

6. \begin{figure}[h] \end{figure} [The weight of the network is \(20 x + 17\) ]

1. Explain why it is not possible to draw a network with an odd number of vertices of odd valency. Figure 3 represents a network of 12 roads in a city. The expression on each arc gives the time, in minutes, to travel along the corresponding road.
2. During rush hour one day \(x = 9\)
   1. Starting at A, use Prim's algorithm to find a minimum spanning tree. You must state the order in which you select the arcs of your tree.
   2. Calculate the weight of the minimum spanning tree. You are now given that \(x > 3\) A route that minimises the total time taken to traverse each road at least once needs to be found. The route must start and finish at the same vertex. The route inspection algorithm is applied to the network in Figure 3 and the time taken for the route is 162 minutes.
3. Determine the value of \(x\), showing your working clearly.

3. \begin{figure}[h] \end{figure} Figure 3 shows a graph G that contains \(17 \operatorname { arcs }\) and 8 vertices.

1. State how many arcs there are in a spanning tree for G .
   (1)
2. Explain why a path on G cannot contain 10 vertices.
   (2)
3. Determine the number of arcs that would need to be added to G to make G a complete graph with 8 vertices.
   (1) \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-04_684_1326_1420_370} \captionsetup{labelformat=empty} \caption{Figure 4}
   \end{figure} Figure 4 shows a weighted graph.
4. Use Prim's algorithm, starting at C , to find the minimum spanning tree for the weighted graph. You must clearly state the order in which you select the arcs of the tree.
   (3)
5. State the weight of the minimum spanning tree.
   (1)

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of five workers, Charles (C), David (D), Ellie (E), Freya (F) and Georgi (G), to five tasks, 1, 2, 3, 4 and 5. Figure 2 shows an initial matching.

1. Starting from this initial matching, use the maximum matching algorithm to find a complete matching. State clearly the alternating path that you use and list your final matching.
   (4)
2. Find another solution starting from the given initial matching. You should state the alternating path and list the complete matching it gives.
   (3)

4. \begin{figure}[h] \end{figure} \section*{[The total weight of the network is 1436 m ]}

1. Explain the term valency. Figure 3 models a system of underground pipes. The number on each arc represents the length, in metres, of that pipe. Pressure readings indicate that there is a leak in the system and an electronic device is to be used to inspect the system to locate the leak. The device will start and finish at A and travel along each pipe at least once. The length of this inspection route needs to be minimised.
2. Use the route inspection algorithm to find the pipes that will need to be traversed twice. You should make your method and working clear.
3. Find the length of the inspection route. Pipe HI is now found to be blocked; it is sealed and will not be replaced. An inspection route is now required that excludes pipe HI . The length of the inspection route must be minimised.
4. Find the length of the minimum inspection route excluding HI. Justify your answer.
5. Given that the device may now start at any vertex and finish at any vertex, find a minimum inspection route, excluding HI.

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. Figure 2 shows an initial matching.

1. Starting from the given initial matching, use the maximum matching algorithm to find an improved matching. You should list the alternating path you used, and your improved matching.
2. Explain why it is not possible to find a complete matching. After training, task 4 is added to F's possible allocation and task 6 is added to E's possible allocation.
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 used and your complete matching.

1. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of six people, Alex (A), Ben (B), Harriet (H), Izzy (I), Leo (L) and Rowan (R), 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)

2. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure} Figure 1 shows the possible allocations of five employees, Ali (A), Campbell (C), Hugo (H), Janelle (J) and Polly (P), to five tasks 1, 2, 3, 4 and 5.

1. Explain why it is not possible to find a complete matching. It is decided that one of the employees should be trained so that a complete matching becomes possible. There are only enough funds for one employee to be trained. Two employees volunteer to undergo training. Janelle can be trained to do task 1 or Hugo can be trained to do task 5.
2. Decide which employee, Janelle or Hugo, should undergo training. Give a reason for your answer. You may now assume that the employee you identified in (b) has successfully undergone training. Figure 2 shows an initial matching.
3. Starting from the given initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use, and state the complete matching.

2. A simply connected graph is a connected graph in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself.

1. Given that a simply connected graph has exactly four vertices,
   1. write down the minimum number of arcs it can have,
   2. write down the maximum number of arcs it can have.
2. 1. Draw a simply connected graph that has exactly four vertices and exactly five arcs.
   2. State, with justification, whether your graph is Eulerian, semi-Eulerian or neither.
3. By considering the orders of the vertices, explain why there is only one simply connected graph with exactly four vertices and exactly five arcs.

3. \begin{figure}[h] \end{figure} [The total weight of the network is \(139 + x + y\) ]

1. Explain what is meant by the term "tree". Figure 3 represents a network of walkways in a warehouse.
   The arcs represent the walkways and the nodes represent junctions between them.
   The number on each arc represents the length, in metres, of the corresponding walkway.
   The values \(x\) and \(y\) are unknown, however it is known that \(x\) and \(y\) are integers and that $$9 < x < y < 14$$
2. 1. Use Dijkstra's algorithm to find the shortest route from A to M.
   2. State an expression for the length of the shortest route from A to M . The warehouse manager wants to check that all of the walkways are in good condition.
      Their inspection route starts at B and finishes at C .
      The inspection route must traverse each walkway at least once and be as short as possible.
3. State the arcs that are traversed twice.
4. State the number of times that H appears in the inspection route. The warehouse manager finds that the total length of the inspection route is 172 metres.
5. Determine the value of \(x\) and the value of \(y\)

4.

1. Explain why it is not possible to draw a graph with exactly 5 nodes with orders \(1,3,4,4\) and 5 A connected graph has exactly 5 nodes and contains 18 arcs. The orders of the 5 nodes are \(2 ^ { 2 x } - 1,2 ^ { x } , x + 1,2 ^ { x + 1 } - 3\) and \(11 - x\).
2. 1. Calculate X .
   2. State whether the graph is Eulerian, semi-Eulerian or neither. You must justify your answer.
3. Draw a graph which satisfies all of the following conditions: