7.02a Graphs: vertices (nodes) and arcs (edges)

3 Consider the following graph in which the arcs are straight lines. \includegraphics[max width=\textwidth, alt={}, center]{71ca9c4e-573b-43b7-910d-4bd610af6b27-3_928_938_317_566}

1. Explain how you know that the graph is simple.
2. Explain how you know that the graph is not connected.
3. On the copy of the graph in your answer book, add as many arcs as you can whilst keeping it both simple and not connected. Give the number of arcs which you have added.
4. Imagine that a new graph is produced in which two vertices are connected if there is no connection between them, direct or indirect, on the original graph. How many arcs would this new graph have?

1 The diagram shows an electrical circuit with wires and switches and with five components, labelled A, B, C, D and E. \includegraphics[max width=\textwidth, alt={}, center]{11c2d98f-1f72-4f1b-b971-5521bee09358-2_328_730_609_319} \includegraphics[max width=\textwidth, alt={}, center]{11c2d98f-1f72-4f1b-b971-5521bee09358-2_261_519_621_1224}

1. Draw a graph showing which vertices are connected together, either directly or indirectly, when the two switches remain open.
2. How many arcs need to be added to your graph when both switches are closed? The graph below shows which components are connected to each other, either directly or indirectly, for a second electrical circuit. \includegraphics[max width=\textwidth, alt={}, center]{11c2d98f-1f72-4f1b-b971-5521bee09358-2_410_494_1356_788}
3. Find the minimum number of arcs which need to be deleted to create two disconnected sets of vertices, and write down your two separate sets.
4. Explain why, in the second electrical circuit, it might be possible to split the components into two disconnected sets by cutting fewer wires than the number of arcs which were deleted in part (iii).

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}

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?

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.

1 Bus routes connect towns A and B and towns A and C .
Train lines connect towns B and D, towns C and D, and towns A and C.
John represents this information in a graph with four nodes, one for each town, in which an arc is drawn for each connection, giving five arcs in all.

1. Draw John's graph.
2. Is John's graph simple? Justify your answer. Jamil represents the information in a graph with five nodes. He uses one node for each of towns A, B and D. Because in town C the bus station and train station are some distance apart, he uses a node labelled C (bus) and a node labelled C (train). Again there are 5 arcs, each representing a connection.
3. Draw Jamil's graph.
4. Is Jamil's graph a tree? Justify your answer.

3 The graph represents four towns together with (two-way) roads connecting them. \includegraphics[max width=\textwidth, alt={}, center]{8eba759f-38bc-4d14-ac65-9a0ee6c79741-4_191_286_319_886} A path is a set of connected arcs linking one vertex to another. A path contains no repeated vertex. \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 2 }\) are paths.

1. There are six paths from \(\mathrm { T } _ { 1 }\). List them.
2. List the paths from \(\mathrm { T } _ { 4 }\).
3. How many paths are there altogether? For this question a route is defined to be a path in which the direction of the arcs is not relevant. Thus \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 2 } \rightarrow \mathrm {~T} _ { 1 }\) are the same route. Similarly \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 2 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 1 }\) are the same route (but note that \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 } \rightarrow \mathrm {~T} _ { 3 }\) is different).
4. How many routes are there altogether?

1 The numbers on opposite faces of the die shown (a standard die) add up to 7. The adjacency graph for the die is a graph which has vertices representing faces. In the adjacency graph two vertices are joined with an arc if they share an edge of the die. For example, vertices 2 and 6 are joined by an arc because they share an edge of the die. \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-2_246_213_488_1608}

1. List the pairs of numbers which are opposite each other.
2. Draw the adjacency graph.
3. Identify and sketch a solid which has the following adjacency graph. \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-2_287_307_1027_879}

5 The diagram represents canals connecting five cities. Canal lengths (shown on the arcs) are in km. \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-5_410_990_306_539}

1. Draw a network in your answer book with nodes representing the five cities and arcs representing direct canal connections, i.e. canal connections which do not involve passing through another city. The company operating the canal system wishes to close some canals to save money, whilst preserving the connectivity.
2. Starting at A, use Prim's algorithm on your answer to part (i) to find a minimum connector for the network. Give the order in which you include arcs. Draw your minimum connector and give its total length. Consider the original network together with an extra vertex, X , at the junction of four arcs. \includegraphics[max width=\textwidth, alt={}, center]{dab87ac5-eda4-433f-b07a-0a609aca2f65-5_405_987_1361_539}
3. Draw the minimum connector which results from applying Prim's algorithm, starting at A , to this network. Give the length of that minimum connector. Hence advise the company on which canals to close.
4. Give a reason why the company might face objections to such closures.

3 Traffic flows in and out of a junction of three roads as shown in the diagram. \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_296_337_333_863} Assuming that no traffic leaves the junction by the same road as it entered, then the digraph shows traffic flows across the junction. \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_362_511_852_776}

1. Redraw the digraph to show that it is planar.
2. Draw a digraph to show the traffic flow across the junction of 4 roads, assuming that no traffic leaves the junction by the same road as it entered. \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_366_366_1512_854}
   (Note that the resulting digraph is also planar, but you are not required to show this.)
3. The digraphs showing flows across the junctions omit an important aspect in their modelling of the road junctions. What is it that they omit?

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 table defines a network in which the numbers represent lengths.

1. Draw the network.
2. Use Dijkstra's algorithm to find the shortest route from A to G . Give the route and its length.

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}

1 The diagram shows the layout of a Mediterranean garden. Thick lines represent paths. \includegraphics[max width=\textwidth, alt={}, center]{aac29742-fee8-48a9-896c-e96696742251-2_961_1093_440_468}

1. Draw a graph to represent this information using the vertices listed below, and with arcs representing the 18 paths. Vertices: patio (pa); pool (po); top steps (ts); orange tree (or); fig tree (fi); pool door (pd); back door (bd); front door (fd); front steps (fs); gate (gat); olive tree (ol); garage (gar). [2] Joanna, the householder, wants to walk along all of the paths.
2. Explain why she cannot do this without repeating at least one path.
3. Write down a route for Joanna to walk along all of the paths, repeating exactly one path. Write down the path which must be repeated. Joanna has a new path constructed which links the pool directly to the top steps.
4. Describe how this affects Joanna's walk, and where she can start and finish. (You are not required to give a new route.)

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}

3. (a) Draw a graph with 6 vertices, each of degree 1 .
(b) Draw two graphs with 6 vertices, each of degree 2 such that:

1. the graph is connected,
2. the graph is not connected. A simple connected graph has 5 vertices each of degree \(x\).
   (c) Find the possible values of \(x\) and explain your answer.
   (d) For each value of \(x\) you found in part (c) draw a possible graph.

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.

6. \begin{figure}[h] \end{figure} A maximin route is to be found through the network shown in Figure 3.
Complete the table in the answer book, and hence find a maximin route.

3 The network represents a system of pipes along which fluid can flow from \(S\) to \(T\). The values on the arcs are the capacities in litres per second. \includegraphics[max width=\textwidth, alt={}, center]{9c9b1a42-8d16-446a-85a1-4c08e5e368be-3_634_1112_404_484}

1. Calculate the capacity of the cut with \(\mathrm { X } = \{ S , A , B , C \} , \mathrm { Y } = \{ D , E , F , G , H , I , T \}\).
2. Explain why the capacity of the cut \(\alpha\), shown on the diagram, is only 21 litres per second.
3. Explain why neither of the arcs \(S C\) and \(A D\) can be full to capacity. Give the maximum flow in \(\operatorname { arc } S B\).
4. Find the maximum flow through the system and draw a diagram to show a way in which this can be achieved. Show that your flow is maximal by using the maximum flow-minimum cut theorem.

5

1. Capacity = \(\_\_\_\_\)
2. \includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_671_997_456_614}
3. Route: \(\_\_\_\_\) Flow \(=\) \(\_\_\_\_\)
4. Maximum flow = \(\_\_\_\_\) Cut: \(\mathrm { X } = \{\) \} \(\quad \mathrm { Y } = \{\)
5. \includegraphics[max width=\textwidth, alt={}, center]{3d8f3593-7923-40f7-b5c0-ac5c3bc21292-10_659_995_1774_616}

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.