Discrete Mathematics 2: NetworksAQA A-Level Further Maths: Topic test

1. 1
   A network has six nodes $U,\ V,\ W,\ X,\ Y,\ Z$. The arcs and their weights are $UV$ 7, $UW$ 4, $VW$ 6, $VX$ 9, $WX$ 3, $WY$ 8, $XY$ 5, $XZ$ 10 and $YZ$ 2.

   (a)

   How many arcs does a minimum spanning tree of this network contain?

   [1 mark]

   • A$6$
   • B$5$
   • C$4$
   • D$9$

   (b)

   What is the total weight of a minimum spanning tree?

   [1 mark]

   • A$21$
   • B$23$
   • C$14$
   • D$20$

   (c)

   When Kruskal's algorithm is applied, arc $UV$ is rejected. Explain why.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A council inspects every street in a district. The streets and their lengths, in hundreds of metres, are $PQ$ 6, $PR$ 4, $PS$ 9, $QR$ 5, $QS$ 7, $RS$ 3, $RT$ 8, $ST$ 4, $SU$ 6 and $TU$ 5. The inspector must travel along every street at least once, starting and finishing at the same junction.

   (a)

   Which junctions have odd degree?

   [1 mark]

   • A$P,\ Q,\ S,\ T$
   • B$R$ and $U$
   • C$P,\ Q,\ R,\ T$
   • D$P,\ S,\ T,\ U$

   (b)

   What is the least total length, in hundreds of metres, of the streets that must be repeated?

   [1 mark]

   • A$18$
   • B$4$
   • C$10$
   • D$6$

   (c)

   Find the length of the shortest route that the inspector can take, in hundreds of metres.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   Five depots $H,\ J,\ K,\ L,\ M$ are joined by direct roads. The distances, in km, are $HJ$ 12, $HK$ 9, $HL$ 15, $HM$ 11, $JK$ 8, $JL$ 14, $JM$ 10, $KL$ 13, $KM$ 7 and $LM$ 6. A van must visit every depot and return to its start.

   (a)

   Use the nearest neighbour algorithm, starting at $H$, to find an upper bound for the length of the shortest tour.

   [3 marks]

   (b)

   Delete $H$ and use a minimum spanning tree of the remaining depots to find a lower bound for the length of the shortest tour.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   Six towns $A,\ B,\ C,\ D,\ E,\ F$ are to be linked by cable, and a surveyor must also visit each town. The distances, in km, between the towns are $AB$ 14, $AC$ 20, $AD$ 11, $AE$ 17, $AF$ 9, $BC$ 12, $BD$ 18, $BE$ 10, $BF$ 15, $CD$ 16, $CE$ 8, $CF$ 13, $DE$ 19, $DF$ 7 and $EF$ 21.

   (a)

   Use Prim's algorithm, starting at $A$, to find a minimum spanning tree. State the order in which the arcs are added and the total weight.

   [6 marks]

   (b)

   The surveyor starts at $A$ and must visit every town and return to $A$. Use the nearest neighbour algorithm from $A$ to find an upper bound, and delete $A$ to find a lower bound, for the length of the shortest tour. Write down the interval in which the shortest length lies.

   [6 marks]

   Total for question 4: 12 marks

5. 5
   Six computer labs $K,\ L,\ M,\ N,\ P,\ Q$ in a school are to be joined by cable. The possible links and their weights, in metres, are $KL$ 9, $KM$ 5, $KN$ 12, $LM$ 7, $LP$ 6, $MN$ 8, $MP$ 11, $NP$ 4, $NQ$ 10 and $PQ$ 13.

   (a)

   Prim's algorithm is applied starting at $K$. Which arc is added third?

   [1 mark]

   • A$LM$
   • B$MN$
   • C$LP$
   • D$NP$

   (b)

   What is the total weight of the minimum spanning tree, in metres?

   [1 mark]

   • A$32$
   • B$22$
   • C$39$
   • D$41$

   (c)

   The link $NQ$ is no longer possible. State whether the minimum spanning tree changes and find its new weight.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   A courier company has five depots $S,\ T,\ U,\ V,\ W$. The distances, in km, are $ST$ 14, $SU$ 10, $SV$ 17, $SW$ 9, $TU$ 13, $TV$ 8, $TW$ 16, $UV$ 12, $UW$ 11 and $VW$ 15. A van must visit every depot and return to its start.

   (a)

   What is the length of the tour $S,\ U,\ T,\ V,\ W,\ S$?

   [1 mark]

   • A$46$ km
   • B$45$ km
   • C$64$ km
   • D$55$ km

   (b)

   Deleting $S$ and using a minimum spanning tree of the other four depots, what lower bound is found?

   [1 mark]

   • A$31$ km
   • B$50$ km
   • C$40$ km
   • D$62$ km

   (c)

   The tour $S,\ U,\ T,\ V,\ W,\ S$ has length $55$ km and the lower bound is $50$ km. Explain what this tells you about the shortest possible tour.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   A postal worker must deliver along every street in a village. The streets and their lengths, in hundreds of metres, are $XY$ 5, $XZ$ 8, $YZ$ 4, $YW$ 7, $ZW$ 6, $ZV$ 9 and $WV$ 3.

   (a)

   Show that the worker can walk along every street exactly once by starting at $Y$ and finishing at $W$, and find the length of this route.

   [3 marks]

   (b)

   The worker now has to start and finish at the same junction, $X$. Find the length of the shortest route.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   Cables are to be laid between six substations $D,\ E,\ F,\ G,\ H,\ J$ and an engineer must also inspect every cable once laid. The possible cables and their lengths, in km, are $DE$ 8, $DF$ 5, $EF$ 6, $EG$ 9, $FG$ 7, $FH$ 10, $GH$ 4, $GJ$ 11, $HJ$ 6 and $DJ$ 12.

   (a)

   The engineer starts at one substation, travels along every cable at least once, and returns to the start. Find the length of the shortest route.

   [6 marks]

   (b)

   The cables are to be laid so that every substation is connected using the least total length. Use Kruskal's algorithm to find the arcs chosen and the total length, and explain why arc $DE$ is not used.

   [6 marks]

   Total for question 8: 12 marks

End of questions