Graph theory: exam review Exam review

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

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

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

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]
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 A to D. [2]

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

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

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

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

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

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

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