Writing the matrix for a cabling network
Figure 1 shows the possible routes for data cables between six buildings, A, B, C, D, E and F, on a college site. The number on each arc is the length of the route, in metres.
(a) Write down the matrix (distance table) that represents this network. (2)
(b) Write down the number of arcs in any spanning tree of this network. (1)
(c) Explain why the arc DF must be in every spanning tree of this network. (1)
- 1
(a) Go round each vertex in turn. Every arc gives two equal entries, one in each row of its two end vertices, so the table is symmetrical about its leading diagonal. A pair of vertices with no direct arc gets a dash, not 0, and so does the diagonal. Reading Figure 1: A–B 45, A–C 60, B–C 38, B–D 52, C–D 41, C–E 70, D–E 33, D–F 26 (eight arcs). B1
- 2
The completed matrix: B1
A B C D E F A – 45 60 – – – B 45 – 38 52 – – C 60 38 – 41 70 – D – 52 41 – 33 26 E – – 70 33 – – F – – – 26 – – - 3
(b) A spanning tree on vertices has arcs. Here . B1
- 4
(c) A spanning tree must include every vertex and be connected. DF is the only arc incident to F (F has degree 1), so the only way to join F to the rest of the tree is along DF. B1
Answer
(a) The symmetric matrix above, with dashes where there is no direct arc (b) 5 (c) F has degree 1, so DF is the only arc that can connect F to the tree
Examiner tip
In (a) the first B1 needs at least six of the eight arcs entered correctly in both their places, the second the whole table. Entering an arc once only, or writing 0 where there is no arc, costs the second B1: 0 would mean a route of zero length. In (c) "DF is the shortest arc" scores B0; the reason is that F has degree 1, so no spanning tree can avoid DF whatever its length.