Graph theory: exam review Exam review Worked solutions

A museum has five galleries, A, B, C, D and E. The graph shows the corridors between them. [7]

1. (a) Write down the adjacency matrix of the graph, taking the vertices in the order A, B, C, D, E. [2]

   • M1 for a symmetric 5 × 5 matrix with zeros on the diagonal
   • A1 for all entries correct

2. (b) Use your matrix to find the degree of vertex B. [1]

   • A1 for 3 (the sum of row B)

3. (c) Two walks in the graph are W₁: A-E-B-C-D-E and W₂: B-C-D-E-B. For each walk, write down the word from trail, path, circuit and cycle that describes it best. [2]

   • A1 for W₁: trail (no edge is repeated, but vertex E is, so it is not a path)
   • A1 for W₂: cycle (it is closed and no vertex is repeated)

4. (d) Explain why the graph is not a tree. [2]

   • A1 for naming a cycle, for example B-C-D-E-B
   • R1 for a tree has no cycles (or: a tree on 5 vertices has 4 edges, this graph has 6)

Five villages, P, Q, R, S and T, are joined by footpaths, as the graph shows. The footpath at T is a loop that starts and ends at T. The adjacency matrix of the graph is \(A=\begin{pmatrix}0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1\end{pmatrix}\), with the vertices in the order P, Q, R, S, T. A loop is entered as 1. [6]

1. (a) Use \(A^3\) to find the number of walks of length 3 from Q to S. [2]

   • M1 for calculating \(A^3\) (or the relevant entry)
   • A1 for 6 (row Q, column S of \(A^3\))

2. (b) Find the number of walks of length at most 3 from R to T. [2]

   • M1 for using \(A + A^2 + A^3\)
   • A1 for 0 + 1 + 2 = 3

3. (c) List all the paths of length 3 from P to S. [2]

   • M1 for at least one correct path, with no vertex repeated
   • A1 for all 2: P-R-Q-S; P-Q-R-S

A cycle club has a map of the roads between six villages, A to F. The graph shows the roads. [6]

1. (a) Is it possible to make a journey that uses every road exactly once and finishes at a different place from where it started? Give a reason. [2]

   • A1 for yes
   • R1 for exactly two vertices of odd degree: B (degree 3) and F (degree 3)

2. (b) Write down a journey that uses every road exactly once. [2]

   • M1 for a trail that starts at B (or F) and ends at the other
   • A1 for all 8 roads used exactly once, for example B-C-F-E-C-A-B-D-F

3. (c) Write down a Hamiltonian cycle. [2]

   • M1 for a closed route that visits each vertex once
   • A1 for a valid cycle, for example A-B-D-F-E-C-A

Five islands, A, B, C, D and E, are joined by ferry routes. The adjacency matrix of the ferry network is \(A=\begin{pmatrix}0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0\end{pmatrix}\), with the vertices in the order A, B, C, D and E. [6]

1. (a) Write down the vertices adjacent to E. [1]

   • A1 for B and D (the 1s in row E)

2. (b) Use the row sums of the matrix to show that the graph has an Euler trail but no Euler circuit. State the two vertices at which an Euler trail must start and finish. [3]

   • M1 for row sums (degrees) 2, 3, 3, 2, 2 for A, B, C, D, E
   • A1 for exactly two odd degrees, at B and C, so an Euler trail but no Euler circuit
   • A1 for start and finish at B and C

3. (c) Use \(A^5\) to find the number of walks of length 5 from A to D. [2]

   • M1 for calculating \(A^5\) (or the relevant entry)
   • A1 for 14 (row A, column D of \(A^5\))

A robot vacuum visits six rooms, A to F, joined by the doorways in the graph. [7]

1. (a) Explain why the graph has no Hamiltonian cycle. [2]

   • M1 for a Hamiltonian cycle needing two different edges at every vertex it visits
   • R1 for vertex A having degree 1 (only one edge), so it cannot be on a cycle

2. (b) Write down a Hamiltonian path. [1]

   • A1 for a path visiting every vertex once, for example A-B-C-D-E-F

3. (c) A complete graph has 8 vertices. Find the number of different Hamiltonian cycles in it. [2]

   • M1 for \(\frac{(8-1)!}{2}\)
   • A1 for 2,520

4. (d) A computer checks 1,000,000 Hamiltonian cycles every second. Find the time it takes to check every Hamiltonian cycle of a complete graph with 15 vertices, in hours to 3 significant figures, and comment on whether checking all the cycles is practical for larger graphs. [2]

   • M1 for \(\frac{(15-1)!}{2} \div 1,000,000\) seconds, then dividing by 3600, giving 43,589,145,600 cycles and about 43,589 s
   • A1 for 12.107421875 hours, with a comment that the number of cycles grows too fast to check every cycle for larger graphs

The graph shows the roads between six villages, A to F. The weight of each edge is the length of the road in km. [7]

1. (a) The weighted adjacency table of the graph is shown, with two entries missing: \(\begin{array}{c|cccccc} & A & B & C & D & E & F \\ \hline A & - & 9 & p & - & - & - \\ B & 9 & - & 12 & 8 & 2 & - \\ C & p & 12 & - & - & 14 & - \\ D & - & 8 & - & - & q & 3 \\ E & - & 2 & 14 & q & - & 9 \\ F & - & - & - & 3 & 9 & - \\\end{array}\) Write down the values of \(p\) and \(q\). [2]

   • A1 for p = 9 (the road AC)
   • A1 for q = 5 (the road DE)

2. (b) Find the shortest route from A to F and its length. [3]

   • M1 for listing or comparing at least two routes
   • A1 for the route A-B-E-D-F
   • A1 for the length 19 km

3. (c) The road BE is closed. Find the new shortest route from A to F and its length. [2]

   • M1 for a route that does not use BE
   • A1 for A-B-D-F, 20 km

A tourist visits five towns, A, B, C, D and E, joined by the roads in the graph. At each town the tourist chooses one of the roads there at random, each equally likely, and drives along it. [6]

1. (a) Write down the transition matrix \(M\) for the random walk, taking the vertices in the order A, B, C, D, E. [2]

   • M1 for each column showing equal probabilities for the roads at that vertex, with a column sum of 1 (at least 3 columns correct)
   • A1 for the whole matrix correct

2. (b) Starting at A, find the probability of being at C after exactly 3 moves. [2]

   • M1 for using \(M^3\)
   • A1 for 0.146 (row C, column A)

3. (c) Find the long-run proportion of time spent at E. [2]

   • M1 for a high power of \(M\) (for example \(M^{50}\)) or the limiting vector
   • A1 for 0.286 (check: degree of E ÷ sum of degrees = 4/14)

Five web pages, A, B, C, D and E, link to each other as the directed graph shows. A visitor clicks one of the links on a page at random, each equally likely. [7]

1. (a) The graph is not strongly connected. Explain what goes wrong with the random walk if a visitor reaches E. [2]

   • R1 for E having no arrow leaving it (out-degree 0), so the visitor cannot move on
   • A1 for the effect: the walk is stuck at E, so in the long run all the probability ends at E and no ranking of the others is possible

2. (b) Add one arrow to the graph so that it is strongly connected. [1]

   • A1 for an arrow from E to A: E needs an arrow leaving it, and A has no arrow into it, so this is the only single arrow that makes every vertex reach every other

3. (c) With a new link from E to A, write down the transition matrix \(M\), taking the pages in the order A, B, C, D and E. [2]

   • M1 for each column showing equal probabilities for the links out of that vertex (at least 3 columns correct)
   • A1 for the whole matrix correct, with 1 in the column of the vertex that has the new link to one place

4. (d) Find the long-run proportion of time spent at each page. [2]

   • M1 for a high power of \(M\) (for example \(M^{200}\)) or the eigenvector for eigenvalue 1 with the entries adding to 1
   • A1 for A 0.235, B 0.118, C 0.176, D 0.235, E 0.235

The table shows the cost, in thousands of euros, of laying a cable between each pair of six villages, A to F. A dash means that no cable can be laid between the pair. [6]

1. (a) Use Kruskal's algorithm to find a minimum spanning tree. List the edges in the order you add them and state the total cost. [3]

   • M1 for taking edges in increasing order of weight, rejecting any that make a cycle (BC (20), CE (23) rejected)
   • A1 for the edges in order: DF (8), AC (9), AB (13), BE (15), BD (24)
   • A1 for total 69

2. (b) Use Prim's algorithm, starting at A, to find the minimum spanning tree. List the edges in the order you add them. [3]

   • M1 for starting at A and joining the cheapest edge to the tree each time
   • A1 for the first three edges: AC, AB, BE
   • A1 for all five edges in order: AC (9), AB (13), BE (15), BD (24), DF (8)

A courier must deliver along every road of an estate shown in the weighted graph, where the weights are lengths in hundreds of metres. The courier starts at A and finishes at B. [5]

1. (a) Write down the vertices of odd degree. [1]

   • A1 for A, B, E, F

2. (b) The route starts at A and finishes at B. State which roads must be repeated. [2]

   • M1 for repeating the shortest path between the two odd vertices that are not the start and finish, E and F
   • A1 for repeating ED, DF (length 7)

3. (c) Find the length of the shortest route. [2]

   • M1 for adding the repeated length 7 to the total weight 59 of all the roads
   • A1 for 66 hundred metres

Four web pages, A, B, C and D, link to each other as the directed graph shows. A visitor is on a page and clicks one of the links on it at random, each equally likely. [12]

1. (a) Write down the in-degree and the out-degree of page C. [2]

   • A1 for in-degree 3 (arrows into C)
   • A1 for out-degree 1 (arrows out of C)

2. (b) Write down the transition matrix \(M\), taking the pages in the order A, B, C, D. [2]

   • M1 for each column showing equal probabilities for the links out of that page (at least 2 columns correct)
   • A1 for the whole matrix correct

3. (c) Find the long-run proportion of time spent on each page. Hence rank the pages, highest first. [3]

   • M1 for a high power of \(M\) (for example \(M^{50}\)) or the limiting vector
   • A1 for the proportions A 0.200, B 0.400, C 0.333, D 0.0667
   • A1 for the ranking B, C, A, D

4. (d) In a second model the visitor stops with probability 0.1 at each move, otherwise clicks a link at random. Write down the transition matrix for this model, using a fifth state E for stopped, in the order A, B, C, D, E. [2]

   • M1 for a fifth row and column, with 0.1 in the E row for each page column and 1 in the bottom right entry
   • A1 for the page entries 0.9 shared equally between the links

5. (e) The visitor starts on page A. Find the probability that the visitor is on each page after 15 moves in the second model. State whether the ranking of the pages is the same as in part (c). [3]

   • M1 for using \(M_2^{15}\) with the start vector for page A
   • A1 for the probabilities A 0.0394, B 0.0854, C 0.0667, D 0.0144
   • A1 for the ranking B, C, A, D: the order is the same as in part (c).

A postal worker must walk along every road in a small town, starting and finishing at the depot A. The graph shows the roads and their lengths in km. [12]

1. (a) Find the degree of each vertex and write down the vertices of odd degree. [2]

   • M1 for finding the degrees (A 3, B 2, C 3, D 3, E 2, F 3)
   • A1 for the odd vertices A, C, D, F

2. (b) List the three ways of pairing the odd vertices. For each pairing, find the shortest path between the vertices in each pair and the total length of the two paths. [4]

   • M1 for the three pairings of A, C, D, F
   • A1 for the first pairing: AC + DF: 8 + 7 = 15
   • A1 for the second pairing: AD + CF: 9 + 4 = 13
   • A1 for the third pairing: AF + CD: 12 + 11 = 23

3. (c) Hence state which edges must be repeated and find the length of the shortest route that uses every edge at least once and returns to the start. [3]

   • A1 for the pairing with the smallest total, AD and CF (13), so the repeated edges are AD, CF
   • M1 for adding the total weight of the graph, 61
   • A1 for 61 + 13 = 74 km

4. (d) Write down how many edges are walked in the shortest route. [1]

   • A1 for 8 edges plus 2 repeated edges = 10

5. (e) Write down a route that starts and finishes at A and has this length. [2]

   • M1 for a closed route from A that uses the repeated edges twice
   • A1 for a valid route of length 74, for example A-D-F-C-E-F-C-A-B-D-A

A touring musician must visit six cities, A to F, once each and return to the start. The table shows the flight times, in hours, between each pair of cities. [12]

1. (a) Use the nearest neighbour algorithm, starting at A, to find an upper bound for the shortest tour. Give the tour and its length. [3]

   • M1 for going to the nearest unvisited vertex each time
   • A1 for the tour A-B-D-E-F-C-A
   • A1 for 18 + 10 + 6 + 11 + 37 + 36 = 118

2. (b) Explain what this upper bound tells you about the shortest tour. [1]

   • R1 for the shortest possible tour is no longer than 118

3. (c) By deleting vertex F, find a lower bound for the shortest tour. [4]

   • M1 for a minimum spanning tree of the vertices other than F
   • A1 for weight 56
   • M1 for adding the two shortest edges at F: 8 + 11
   • A1 for lower bound 75

4. (d) By deleting vertex A instead, find a second lower bound. State which lower bound is better and why. [3]

   • M1 for minimum spanning tree weight 46 plus the two shortest edges at A: 18 + 26
   • A1 for lower bound 90
   • R1 for A is better because it is the larger lower bound

5. (e) Write down an inequality for the length T of the shortest tour, using the best bounds you have found. [1]

   • A1 for \(90 \leq T \leq 118\)

A tour guide must visit six places, A to F, and return to the start. The graph shows the roads between the places, with their lengths in km. The tour guide wants the shortest possible tour that visits every place. [16]

1. (a) The table shows the shortest distances between the six places. Three entries are missing: \(\begin{array}{c|cccccc} & A & B & C & D & E & F \\ \hline A & - & 7 & p & 9 & 10 & 15 \\ B & 7 & - & 20 & 7 & 17 & 13 \\ C & p & 20 & - & q & 3 & r \\ D & 9 & 7 & q & - & 16 & 6 \\ E & 10 & 17 & 3 & 16 & - & 10 \\ F & 15 & 13 & r & 6 & 10 & - \\\end{array}\) Use the graph to find \(p\), \(q\) and \(r\). [3]

   • A1 for p = 13: route A-E-C (the road AC is 14, so it is not the shortest)
   • A1 for q = 19: route C-E-F-D (no direct road)
   • A1 for r = 13: route C-E-F (no direct road)

2. (b) Use the nearest neighbour algorithm on the table, starting at A, to find an upper bound for the shortest tour. [3]

   • M1 for going to the nearest unvisited place each time
   • A1 for the tour A-B-D-F-E-C-A
   • A1 for 7 + 7 + 6 + 10 + 3 + 13 = 46

3. (c) Write the tour from (b) as a route along the roads of the original graph. State its length and which places are visited more than once. [3]

   • M1 for replacing each leg that is not a road by its shortest route
   • A1 for the route A-B-D-F-E-C-E-A of length 46
   • A1 for the places visited more than once: E

4. (d) By deleting C, find a lower bound for the shortest tour. [3]

   • M1 for a minimum spanning tree of the other five places on the table: weight 30
   • M1 for adding the two shortest distances from C: 3 + 13
   • A1 for lower bound 46

5. (e) Hence state, with a reason, whether the tour from (b) is a shortest possible tour. [2]

   • A1 for yes
   • R1 for the upper bound and the lower bound are equal (46)

6. (f) Each road length in the graph is given to the nearest unit. Find a lower bound for the length of the route in part (c) before rounding. [2]

   • M1 for each road could be up to 0.5 shorter, and the route uses 7 roads: 46 − 7 × 0.5
   • A1 for 42.5