This question involves analyzing a network representing potential locations for installing fibre optic cable. A company wants to connect 7 towns (labelled A to G) with fibre optic cable. The cost (in thousands of dollars) of laying the cable between pairs of towns is given in the following weighted graph.
[VISUALIZATION: The provided diagram illustrates an undirected weighted graph showing 7 towns labelled A, B, C, D, E, F, G. The graph indicates the cost of connecting these towns with fibre optic cables by displaying edges with labels: AB(10), AC(12), AD(15), BC(8), BD(11), BE(18), CD(9), CE(14), CF(20), DE(7), DF(13), DG(16), EF(10), EG(11), FG(9).]
(a) Interpret the information and summarize it in the form of a weighted adjacency table. [3]
(b) (i) Starting at town A, use Prim’s algorithm to determine the minimum spanning tree for this network. List the edges in the order in which they are selected.
(ii) State the total minimum cost for laying the cable. [7]
A technician needs to visit each connection (edge) in the minimum spanning tree found in part (b) to perform checks, starting and finishing at town A.
(c) (i) Explain why it is not possible to find a route that traverses each edge of the minimum spanning tree exactly once, starting and finishing at A.
(ii) Determine the minimum total distance the technician must travel to check every edge of the minimum spanning tree, starting and finishing at town A. [6]
(d) The company considers an alternative plan where they build a central hub H. All 7 towns will be connected directly to H, but not directly to each other. The cost of connecting each town to the hub H is given in the table below:
Town
Cost (thousands of dollars)
A
25
B
22
C
20
D
18
E
15
F
21
G
19
Interpret the data and calculate the total cost of connecting all towns using this hub-and-spoke model. [2]
(e) Interpret the outcomes of the two plans by stating which one is cheaper (the minimum spanning tree or the hub-and-spoke model) and calculating the cost difference. [2]
Finally, the company wants to determine the shortest path from town A to town G using the original network connections shown in the graph.
(f) (i) Use Dijkstra’s algorithm to establish the shortest path from A to G. Present the main steps of your algorithm including the sequence in which vertices become permanent.
(ii) State the length of this shortest path and identify the path itself. [7]
Part a
3 minutes
3 marks
Question
Interpret the information and summarize it in the form of a weighted adjacency table. [3]
Hint Hint
Hint
Use a 7×7 matrix with towns A–G as headers; fill with given weights or ‘–’ where no direct connection exists.
Answer Answer
Mark Scheme Mark Scheme
Explanation Explanation
Answer Answer
Complete Answer
A
B
C
D
E
F
G
A
–
10
12
15
–
–
–
B
10
–
8
11
18
–
–
C
12
8
–
9
14
20
–
D
15
11
9
–
7
13
16
E
–
18
14
7
–
10
11
F
–
–
20
13
10
–
9
G
–
–
–
16
11
9
–
Mark Scheme Mark Scheme
Answer Explanation Answer Explanation
Part b
5 minutes
7 marks
Question
(i) Starting at town A, use Prim’s algorithm to determine the minimum spanning tree for this network. List the edges in the order they are selected.
(ii) State the total minimum cost for laying the cable. [7]
Hint Hint
Hint
At each step, select the smallest edge connecting the growing tree to a new vertex.
(i) Explain why it is not possible to find a route that traverses each edge of the minimum spanning tree exactly once, starting and finishing at A.
(ii) Determine the minimum total distance the technician must travel to check every edge of the minimum spanning tree, starting and finishing at town A. [6]
Hint Hint
Hint
Recall that an Eulerian circuit exists only if all vertices have even degree; for the postman route, consider repeating the shortest path between the odd vertices.
Answer Answer
Mark Scheme Mark Scheme
Explanation Explanation
Answer Answer
Complete Answer
(i) In the MST, vertices A and G have degree 1 (odd), so an Eulerian circuit is not possible.
(ii) The technician must travel the MST path (cost 53) and then repeat the unique A–G route (cost 53), totaling 106.
Mark Scheme Mark Scheme
Answer Explanation Answer Explanation
Part d
2 minutes
2 marks
Question
Interpret the data and calculate the total cost of connecting all towns using this hub-and-spoke model. [2]
Hint Hint
Hint
Sum the connection costs listed for towns A–G.
Answer Answer
Mark Scheme Mark Scheme
Explanation Explanation
Answer Answer
Complete Answer
25 + 22 + 20 + 18 + 15 + 21 + 19 = 140
Mark Scheme Mark Scheme
Answer Explanation Answer Explanation
Part e
2 minutes
2 marks
Question
Interpret the outcomes of the two plans by stating which one is cheaper (the minimum spanning tree or the hub-and-spoke model) and calculating the cost difference. [2]
Hint Hint
Hint
Compare the MST cost (53) against the hub-and-spoke cost (140) and find the difference.
Answer Answer
Mark Scheme Mark Scheme
Explanation Explanation
Answer Answer
Complete Answer
The MST plan (53) is cheaper than the hub-and-spoke model (140) by 87.
Mark Scheme Mark Scheme
Answer Explanation Answer Explanation
Part f
7 minutes
7 marks
Question
(i) Use Dijkstra’s algorithm to establish the shortest path from A to G. Present the main steps of your algorithm including the sequence in which vertices become permanent.
(ii) State the length of this shortest path and identify the path itself. [7]
Hint Hint
Hint
Initialize the distance for A as 0 and all others as infinity, then update and mark permanent vertices sequentially as you calculate shortest distances.
Answer Answer
Mark Scheme Mark Scheme
Explanation Explanation
Answer Answer
Complete Answer
(i) Permanent order and distances: A(0), B(10), C(12), D(15), E(22), F(28), G(31).
(ii) Shortest path is A→D→G with a total length of 31.
Hint: The password should be at least eight characters long. To make it stronger, use upper and lower case letters, numbers, and symbols like ! " ? $ % ^ & ).
