Graph theory: exam review Exam review: second paper Worked solutions

A school has five buildings, P, Q, R, S and T. The graph shows the covered walkways between them. [7]

1. (a) Write down the adjacency matrix of the graph, taking the vertices in the order P, Q, R, S, T. [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 R. [1]

   • A1 for 3 (the sum of row R)

3. (c) Two walks in the graph are W₁: Q-R-T-S-R and W₂: R-S-T-R. 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 R 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 R-S-T-R
   • R1 for a tree has no cycles (or: a tree on 5 vertices has 4 edges, this graph has 6)

Five computers, P, Q, R, S and T, are linked by cables, as the graph shows. The link at P is a loop that starts and ends at P. The adjacency matrix of the graph is \(A=\begin{pmatrix}1 & 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 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 R. [2]

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

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

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

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-Q-T-S; P-Q-R-S

A park ranger has a map of the roads between six lookouts, 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: A (degree 3) and D (degree 3)

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

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

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 rooms in an escape game, P, Q, R, S and T, are joined by doors. The adjacency matrix of the doors is \(A=\begin{pmatrix}0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0\end{pmatrix}\), with the vertices in the order P, Q, R, S and T. [6]

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

   • A1 for P and S (the 1s in row T)

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, 2, 3, 2 for P, Q, R, S, T
   • A1 for exactly two odd degrees, at Q and S, so an Euler trail but no Euler circuit
   • A1 for start and finish at Q and S

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

   • M1 for calculating \(A^5\) (or the relevant entry)
   • A1 for 10 (row P, column S of \(A^5\))

A drone inspects six towers, A to F, joined by the cables 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 F 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 B-A-E-D-C-F

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

   • M1 for \(\frac{(9-1)!}{2}\)
   • A1 for 20,160

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

   • M1 for \(\frac{(16-1)!}{2} \div 10,000,000\) seconds, then dividing by 3600, giving 653,837,184,000 cycles and about 65,384 s
   • A1 for 18.1640625 hours, with a comment that the number of cycles grows too fast to check every cycle for larger graphs

The graph shows the train links between six stations, A to F. The weight of each edge is the journey time in minutes. [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 & - & p & q & - & - & - \\ B & p & - & 11 & 7 & - & - \\ C & q & 11 & - & 9 & 11 & - \\ D & - & 7 & 9 & - & 2 & 14 \\ E & - & - & 11 & 2 & - & 5 \\ F & - & - & - & 14 & 5 & - \\\end{array}\) Write down the values of \(p\) and \(q\). [2]

   • A1 for p = 11 (the road AB)
   • A1 for q = 14 (the road AC)

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-D-E-F
   • A1 for the length 25 min

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

   • M1 for a route that does not use DE
   • A1 for A-C-E-F, 30 min

A robot moves between five landing pads, P, Q, R, S and T, along the paths in the graph. From each pad it chooses one of the paths at random, each equally likely. [6]

1. (a) Write down the transition matrix \(M\) for the random walk, taking the vertices in the order P, Q, R, S, T. [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 P, find the probability of being at R after exactly 3 moves. [2]

   • M1 for using \(M^3\)
   • A1 for 0.287 (row R, column P)

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

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

Five bus stops, P, Q, R, S and T, are joined by one-way routes, as the directed graph shows. A passenger takes one of the routes leaving a stop at random, each equally likely. [7]

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

   • R1 for T having no route leaving it (out-degree 0), so the passenger cannot move on
   • A1 for the effect: the walk is stuck at T, so in the long run all the probability ends at T 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 T to P: T needs an arrow leaving it, and P 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 T to P, write down the transition matrix \(M\), taking the stops in the order P, Q, R, S and T. [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 stop. [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 P 0.235, Q 0.176, R 0.118, S 0.235, T 0.235

The table shows the cost, in thousands of euros, of building a pipe between each pair of six farms, A to F. A dash means that no pipe can be built 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 (DE (15), AB (19), CD (21) rejected)
   • A1 for the edges in order: BC (3), BD (5), CE (6), AC (12), DF (24)
   • A1 for total 50

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, BC, BD
   • A1 for all five edges in order: AC (12), BC (3), BD (5), CE (6), DF (24)

A meter reader must walk along every street of a village shown in the weighted graph, where the weights are lengths in hundreds of metres. The meter reader starts at C and finishes at F. [5]

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

   • A1 for B, C, E, F

2. (b) The route starts at C and finishes at F. 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, B and E
   • A1 for repeating BE (length 9)

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

   • M1 for adding the repeated length 9 to the total weight 58 of all the roads
   • A1 for 67 hundred metres

Four blog 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 2 (arrows into C)
   • A1 for out-degree 2 (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.0667, B 0.200, C 0.400, D 0.333
   • A1 for the ranking C, D, B, A

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.0116, B 0.0465, C 0.0735, D 0.0743
   • A1 for the ranking D, C, B, A: the order is different from the order in part (c).

A street sweeper must clean every street in a small district, starting and finishing at the garage A. The graph shows the streets and the time to clean each one in minutes. [12]

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

   • M1 for finding the degrees (A 2, B 3, C 5, D 3, E 2, F 3)
   • A1 for the odd vertices B, 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 B, C, D, F
   • A1 for the first pairing: BC + DF: 5 + 10 = 15
   • A1 for the second pairing: BD + CF: 12 + 11 = 23
   • A1 for the third pairing: BF + CD: 16 + 8 = 24

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, BC and DF (15), so the repeated edges are BC, DF
   • M1 for adding the total weight of the graph, 73
   • A1 for 73 + 15 = 88 min

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

   • A1 for 9 edges plus 2 repeated edges = 11

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 88, for example A-C-B-C-E-F-D-F-C-D-B-A

A courier must visit six depots, A to F, once each and return to the start. The table shows the driving distances, in km, between each pair of depots. [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-E-D-C-B-F-A
   • A1 for 12 + 18 + 17 + 10 + 15 + 16 = 88

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

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

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 52
   • M1 for adding the two shortest edges at F: 15 + 16
   • A1 for lower bound 83

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

   • M1 for minimum spanning tree weight 63 plus the two shortest edges at B: 10 + 13
   • A1 for lower bound 86
   • R1 for B 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 \(86 \leq T \leq 88\)

An engineer must inspect six places, A to F, and return to the start. The graph shows the roads between the places, with the travel time in minutes. The engineer 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 & - & 5 & 8 & 14 & 17 & 12 \\ B & 5 & - & p & q & 13 & 7 \\ C & 8 & p & - & 18 & 9 & 16 \\ D & 14 & q & 18 & - & r & 2 \\ E & 17 & 13 & 9 & r & - & 7 \\ F & 12 & 7 & 16 & 2 & 7 & - \\\end{array}\) Use the graph to find \(p\), \(q\) and \(r\). [3]

   • A1 for p = 13: route B-A-C (no direct road)
   • A1 for q = 9: route B-F-D (the road BD is 14, so it is not the shortest)
   • A1 for r = 9: route D-F-E (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-F-D-E-C-A
   • A1 for 5 + 7 + 2 + 9 + 9 + 8 = 40

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-F-D-F-E-C-A of length 40
   • A1 for the places visited more than once: F

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

   • M1 for a minimum spanning tree of the other five places on the table: weight 31
   • M1 for adding the two shortest distances from F: 2 + 7
   • A1 for lower bound 40

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 (40)

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: 40 − 7 × 0.5
   • A1 for 36.5