Study notes
No notes have been generated for this topic yet. Open the topic page online and click Generate notes first.
Past exam questions (2)
2024 · Paper 1 · Q1(ii) · p.5
Calculate the shortest total distance the security manager would have to walk if she started at her office (O) and followed the minimum spanning tree to visit each of the camera locations in the shopping centre. [Visual aid: None]
2024 · Paper 1 · Q1(b) · p.4
A security manager wishes to install cameras in the public areas of a shopping centre. She wishes to locate these cameras so as to minimise the total length of the cables between them. In the network shown below node O represents the manager's office. The nodes A to L represent the locations where the security cameras are to be installed. The weight of each edge represents the distance (in meters) between each location. [Network diagram showing nodes O, A, B, C, D, E, F, G, H, I, J, K, L with edges and weights representing distances. For example, edge OA has weight 56, edge AB has weight 62, edge AD has weight 73, edge BD has weight 20, edge BE has weight 71, edge BF has weight 89, edge CD has weight 43, edge CE has weight 82, edge DE has weight 27, edge DF has weight 96, edge DG has weight 66, edge EF has weight 48, edge EG has weight 109, edge EH has weight 97, edge FG has weight 59, edge FH has weight 103, edge FI has weight 88, edge GH has weight 102, edge GI has weight 21, edge HI has weight 112, edge HJ has weight 40, edge IJ has weight 100.] (i) Using an appropriate algorithm, find the minimum spanning tree for the network. Name the algorithm you used. Relevant supporting work must be shown.
Marking scheme
2(56 + 43) + 20 + 45 + 73 + 2(66) + 27 + 48 + 59 + 88 + 21 + 40 = 751 m 5