Graph theory: exam review Exam review: second paper

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]
2. (b) Use your matrix to find the degree of vertex R. [1]
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]
4. (d) Explain why the graph is not a tree. [2]

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]
2. (b) Find the number of walks of length at most 3 from P to T. [2]
3. (c) List all the paths of length 3 from P to S. [2]

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]
2. (b) Write down a journey that uses every road exactly once. [2]
3. (c) Write down a Hamiltonian cycle. [2]

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]
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]
3. (c) Use \(A^5\) to find the number of walks of length 5 from P to S. [2]

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]
2. (b) Write down a Hamiltonian path. [1]
3. (c) A complete graph has 9 vertices. Find the number of different Hamiltonian cycles in it. [2]
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]

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]
2. (b) Find the shortest route from A to F and its length. [3]
3. (c) The road DE is closed. Find the new shortest route from A to F and its length. [2]

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]
2. (b) Starting at P, find the probability of being at R after exactly 3 moves. [2]
3. (c) Find the long-run proportion of time spent at R. [2]

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]
2. (b) Add one arrow to the graph so that it is strongly connected. [1]
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]
4. (d) Find the long-run proportion of time spent at each stop. [2]

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]
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]

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]
2. (b) The route starts at C and finishes at F. State which roads must be repeated. [2]
3. (c) Find the length of the shortest route. [2]

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]
2. (b) Write down the transition matrix \(M\), taking the pages in the order A, B, C, D. [2]
3. (c) Find the long-run proportion of time spent on each page. Hence rank the pages, highest first. [3]
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]
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]

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]
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]
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]
4. (d) Write down how many edges are walked in the shortest route. [1]
5. (e) Write down a route that starts and finishes at A and has this length. [2]

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]
2. (b) Explain what this upper bound tells you about the shortest tour. [1]
3. (c) By deleting vertex F, find a lower bound for the shortest tour. [4]
4. (d) By deleting vertex B instead, find a second lower bound. State which lower bound is better and why. [3]
5. (e) Write down an inequality for the length T of the shortest tour, using the best bounds you have found. [1]

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]
2. (b) Use the nearest neighbour algorithm on the table, starting at A, to find an upper bound for the shortest tour. [3]
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]
4. (d) By deleting F, find a lower bound for the shortest tour. [3]
5. (e) Hence state, with a reason, whether the tour from (b) is a shortest possible tour. [2]
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]