D1: Algorithms on graphsEdexcel International A Level Maths: Topic test

1. 1
   A graph $G$ has vertices $P$, $Q$, $R$, $S$ and $T$, and edges $PQ$, $PR$, $QR$, $QS$, $RS$ and $ST$.

   (a)

   How many vertices of $G$ have odd degree?

   [1 mark]

   • A$2$
   • B$3$
   • C$4$
   • D$5$

   (b)

   Which of the following is a cycle in $G$?

   [1 mark]

   • A$P-Q-S-T$
   • B$Q-R-S-T-S-Q$
   • C$P-Q-R-S-T-P$
   • D$P-Q-S-R-P$

   (c)

   State the number of edges in any spanning tree of $G$, and list the edges of one spanning tree of $G$.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   The complete graph $K_7$ has 7 vertices, and every pair of vertices is joined by exactly one edge.

   (a)

   How many edges does $K_7$ have?

   [1 mark]

   • A$21$
   • B$42$
   • C$14$
   • D$7$

   (b)

   How many edges does a spanning tree of $K_7$ have?

   [1 mark]

   • A$5$
   • B$6$
   • C$7$
   • D$15$

   (c)

   Show that the sum of the degrees of the vertices of $K_7$ is twice the number of edges of $K_7$.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A network joins six stations $U$, $V$, $W$, $X$, $Y$ and $Z$. The cost of laying cable along each possible route, in hundreds of pounds, is: $UV=6$, $UW=9$, $VW=4$, $VX=11$, $WX=7$, $WY=10$, $XY=5$, $XZ=8$ and $YZ=13$. The stations are to be connected at minimum total cost.

   (a)

   Use Kruskal's algorithm to find a minimum spanning tree. List the arcs in the order in which they are accepted, and state the total weight of the tree.

   [3 marks]

   (b)

   Use Prim's algorithm, starting at $U$, to find the minimum spanning tree. List the arcs in the order in which they are selected, and state the total weight of the tree.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A courier network joins seven depots $H$, $J$, $K$, $L$, $M$, $N$ and $Z$. The road lengths, in km, are: $HK=14$, $HM=11$, $HN=4$, $JL=13$, $JM=9$, $KL=6$, $KZ=7$, $LN=2$, $LZ=8$, $MN=3$ and $MZ=12$. There are no other direct roads.

   (a)

   Use Dijkstra's algorithm to find the shortest route from $H$ to $Z$. Show the order in which the depots are given permanent labels and the working values at each stage, and state the route and its length.

   [6 marks]

   (b)

   (i) Write down the vertices of odd degree, and show that the sum of the degrees of all the vertices is consistent with the number of roads.
   (ii) Use Kruskal's algorithm to find a minimum spanning tree for the network, listing the arcs accepted and rejected, and state its total weight.

   [6 marks]

   Total for question 4: 12 marks

5. 5
   Kruskal's algorithm is applied to a network with five vertices $V$, $W$, $X$, $Y$ and $Z$. The arcs, in increasing order of weight, are $VW=2$, $XY=3$, $WX=4$, $VY=5$, $YZ=6$, $WZ=7$ and $XZ=9$.

   (a)

   Which arc is the first to be rejected?

   [1 mark]

   • A$VY$
   • B$WZ$
   • C$XZ$
   • D$WX$

   (b)

   Find the total weight of the minimum spanning tree.

   [1 mark]

   • A$9$
   • B$16$
   • C$15$
   • D$36$

   (c)

   Use Prim's algorithm, starting at $V$, and list the arcs in the order in which they are selected.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   Dijkstra's algorithm is used to find the shortest route from $S$ to $D$ in a network with five vertices $S$, $A$, $B$, $C$ and $D$. The arcs and their lengths are $SA=4$, $SB=7$, $AB=2$, $AC=9$, $BC=3$, $BD=8$ and $CD=2$.

   (a)

   Find the final label of vertex $B$.

   [1 mark]

   • A$7$
   • B$6$
   • C$2$
   • D$9$

   (b)

   Find the shortest route from $S$ to $D$.

   [1 mark]

   • A$S-B-D$
   • B$S-B-C-D$
   • C$S-A-C-D$
   • D$S-A-B-C-D$

   (c)

   The working value of $C$ is 13 after $A$ is given its permanent label, but it is 9 after $B$ is given its permanent label. Explain why the working value changes.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   A tree $T$ has 10 vertices. Exactly 6 of the vertices have degree 1, and the other 4 vertices all have the same degree.

   (a)

   Find the degree of each of the 4 vertices that do not have degree 1.

   [3 marks]

   (b)

   A connected graph $H$ has 10 vertices and 12 edges.
   (i) State the number of edges in a spanning tree of $H$.
   (ii) Find the number of edges that must be removed from $H$ to leave a spanning tree.
   (iii) Explain why any 3 edges of $H$ cannot simply be removed.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   A network joins six sensors $P$, $Q$, $R$, $S$, $T$ and $U$. The lengths of the possible cables, in metres, are: $PQ=2$, $PR=9$, $PS=4$, $PT=15$, $QT=10$, $QU=14$, $RS=6$, $RT=5$, $SU=13$ and $TU=3$.

   (a)

   Use Prim's algorithm, starting at $P$, to find a minimum spanning tree. List the arcs in the order in which they are selected, and state the total weight of the tree.

   [6 marks]

   (b)

   (i) Use Dijkstra's algorithm to find the shortest route from $P$ to $U$, showing the working values, and state its length.
   (ii) Find the length of the route from $P$ to $U$ that uses only cables in the minimum spanning tree from (a), and explain why it is not the shortest route.

   [6 marks]

   Total for question 8: 12 marks

End of questions