Decision Mathematics 1: Algorithms on graphsEdexcel A-Level Further Maths: Topic test

1. 1
   A network has six vertices $A$, $B$, $C$, $D$, $E$ and $F$. The weights of the edges are $AB=6$, $AC=3$, $BC=4$, $BD=7$, $CD=5$, $CE=8$, $DE=2$, $DF=9$ and $EF=10$.

   (a)

   When Kruskal's algorithm is applied to the network, which edge is the first to be rejected?

   [1 mark]

   • A$DE$
   • B$AB$
   • C$BD$
   • D$CE$

   (b)

   What is the total weight of the minimum spanning tree?

   [1 mark]

   • A$14$
   • B$24$
   • C$29$
   • D$23$

   (c)

   Use Prim's algorithm, starting at $A$, to list the edges of the minimum spanning tree in the order in which they are added.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A road network joins towns $S$, $A$, $B$, $C$, $D$ and $T$. The road lengths in km are $SA=4$, $SB=7$, $AB=2$, $AC=6$, $BC=3$, $BD=9$, $CD=5$, $CT=10$ and $DT=4$. Dijkstra's algorithm is used to find the shortest route from $S$ to $T$.

   (a)

   What is the final (permanent) label of $C$?

   [1 mark]

   • A$9$
   • B$10$
   • C$12$
   • D$3$

   (b)

   In which order do the vertices receive their permanent labels?

   [1 mark]

   • A$S, B, A, C, D, T$
   • B$S, A, C, B, D, T$
   • C$S, A, B, C, D, T$
   • D$S, A, B, D, C, T$

   (c)

   The road $BC$ is closed. Find the new shortest distance from $S$ to $T$.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   Floyd's algorithm is applied to a directed network with four vertices $A$, $B$, $C$ and $D$. The initial distance matrix, with rows and columns in the order $A$, $B$, $C$, $D$ and $\infty$ meaning that there is no direct arc, is $\begin{pmatrix} 0 & 4 & \infty & 10 \\ 3 & 0 & 5 & \infty \\ \infty & 2 & 0 & 3 \\ 6 & \infty & 7 & 0 \end{pmatrix}$. In iteration $k$ the intermediate vertex is the $k$th vertex, taken in the order $A$, $B$, $C$, $D$.

   (a)

   Complete iteration 1 and write down the updated distance matrix.

   [3 marks]

   (b)

   Complete iterations 2, 3 and 4 to find the final distance matrix.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A network has seven vertices $S$, $A$, $B$, $C$, $D$, $E$ and $T$. The edges and their weights are $SA=5$, $SB=9$, $SC=6$, $AB=3$, $AD=11$, $BC=13$, $BD=7$, $BE=10$, $CE=8$, $DT=4$ and $ET=12$.

   (a)

   Use Kruskal's algorithm to find a minimum spanning tree for the network. List the edges in the order considered, stating clearly which are accepted and which are rejected, and give the total weight of the tree.

   [6 marks]

   (b)

   Use Dijkstra's algorithm to find the shortest route from $S$ to $T$, showing the order of permanent labels and the working values. State whether this route uses only edges of the minimum spanning tree found in part (a).

   [6 marks]

   Total for question 4: 12 marks

5. 5
   The distances in km between five towns $P$, $Q$, $R$, $S$ and $T$ are given by the matrix $\begin{pmatrix} - & 8 & 5 & 11 & - \\ 8 & - & 6 & - & 9 \\ 5 & 6 & - & 7 & 13 \\ 11 & - & 7 & - & 4 \\ - & 9 & 13 & 4 & - \end{pmatrix}$, with rows and columns in the order $P$, $Q$, $R$, $S$, $T$. A dash means that there is no direct road. A minimum spanning tree for the towns is to be found.

   (a)

   Prim's algorithm is started at $P$. Which edge is added second?

   [1 mark]

   • A$PQ$
   • B$RS$
   • C$QR$
   • D$PS$

   (b)

   What is the weight of the minimum spanning tree?

   [1 mark]

   • A$22$
   • B$24$
   • C$15$
   • D$31$

   (c)

   The road $ST$ is closed. Find the weight of the minimum spanning tree for the remaining roads.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   A network of roads has vertices $S$, $A$, $B$, $C$, $D$, $E$ and $T$ and the road lengths in km are $SA=4$, $SC=7$, $SB=9$, $AB=8$, $AT=14$, $CB=1$, $CD=6$, $CE=10$, $BD=4$, $DE=3$ and $DT=5$. Dijkstra's algorithm is applied from $S$. At one stage $S$, $A$ and $C$ have permanent labels 0, 4 and 7, and no other vertex has a permanent label.

   (a)

   Which vertex is given the next permanent label?

   [1 mark]

   • A$D$
   • B$E$
   • C$T$
   • D$B$

   (b)

   After $B$ is made permanent, what is the new working value of $D$?

   [1 mark]

   • A$13$
   • B$12$
   • C$4$
   • D$14$

   (c)

   Complete the algorithm to find the shortest distance from $S$ to $T$ and state the route.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   Floyd's algorithm is applied to a directed network with four vertices $P$, $Q$, $R$ and $S$. The initial distance matrix, with rows and columns in the order $P$, $Q$, $R$, $S$ and $\infty$ meaning that there is no direct arc, is $\begin{pmatrix} 0 & 6 & \infty & 2 \\ \infty & 0 & 3 & \infty \\ 4 & \infty & 0 & 7 \\ \infty & 1 & \infty & 0 \end{pmatrix}$. The route matrix initially has the column vertex in every entry, so each row reads $P$, $Q$, $R$, $S$. When $d(i,j)$ is improved using intermediate vertex $k$, the route entry for $(i,j)$ is replaced by the route entry for $(i,k)$. In iteration $k$ the intermediate vertex is the $k$th vertex in the order $P$, $Q$, $R$, $S$.

   (a)

   Complete iteration 1 for both the distance matrix and the route matrix, stating the entries that change.

   [3 marks]

   (b)

   The algorithm is completed. The final distance matrix is $\begin{pmatrix} 0 & 3 & 6 & 2 \\ 7 & 0 & 3 & 9 \\ 4 & 7 & 0 & 6 \\ 8 & 1 & 4 & 0 \end{pmatrix}$ and the final route matrix, with rows and columns in the order $P$, $Q$, $R$, $S$, is $\begin{pmatrix} P & S & S & S \\ R & Q & R & R \\ P & P & R & P \\ Q & Q & Q & S \end{pmatrix}$. Use the final matrices to find the shortest route from $R$ to $Q$ and its length.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   A network has four vertices $J$, $K$, $L$ and $M$. The roads and their lengths in km are $JK=8$, $JL=12$, $JM=6$, $KL=3$ and $LM=9$. There is no direct road between $K$ and $M$.

   (a)

   Write down the initial distance matrix with rows and columns in the order $J$, $K$, $L$, $M$, then use Floyd's algorithm to find the shortest distance between every pair of vertices, showing the matrix after each iteration.

   [6 marks]

   (b)

   Use Prim's algorithm, starting at $J$, to find a minimum spanning tree for the original network and its total weight. Show that the route between $K$ and $M$ in this tree is longer than the shortest distance found in part (a), and explain why this happens.

   [6 marks]

   Total for question 8: 12 marks

End of questions