6. [Maximum mark: 19]
The following table shows the distances (in km) between six towns connected by roads. A dash (–) indicates that there is no direct road between the towns.
|
A |
B |
C |
D |
E |
F |
| A |
– |
12 |
15 |
– |
– |
20 |
| B |
12 |
– |
8 |
10 |
– |
– |
| C |
15 |
8 |
– |
7 |
11 |
18 |
| D |
– |
10 |
7 |
– |
9 |
– |
| E |
– |
– |
11 |
9 |
– |
14 |
| F |
20 |
– |
18 |
– |
14 |
– |
(a) Draw a weighted graph representing the towns and the distances between them. [2]
A company wants to install fibre optic cables along the roads to connect all six towns with the minimum total length of cable.
(b) (i) Use Kruskal’s algorithm to find the minimum spanning tree for this network. List the edges in the order they are added.
(ii) State the minimum total length of cable required. [5]
A salesperson needs to start at town A, visit every other town exactly once, and return to town A.
(c) (i) Use the nearest neighbour algorithm, starting at A, to find an upper bound for the length of the salesperson’s route.
(ii) By deleting vertex A, find a lower bound for the length of the salesperson’s route. [7]
(d) Determine if the original graph contains an Eulerian circuit. Justify your answer. [2]
e) Find the minimum length of a route starting and finishing at A that traverses every road at least once (the Chinese Postman Problem). [3]
Question
(a) Draw a weighted graph representing the towns and the distances between them. [2]
Hint
Hint
Hint
Include vertices A–F and draw every existing road with its correct distance label.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
A graph with six vertices labelled A, B, C, D, E, F, and edges labelled:
AB=12, AC=15, AF=20,
BC=8, BD=10,
CD=7, CE=11, CF=18,
DE=9,
EF=14.
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
(b)(i) Use Kruskal’s algorithm to find the minimum spanning tree. List the edges in the order they are added.
Hint
Hint
Hint
Sort all edges by increasing distance and add one at a time, skipping any that would form a cycle.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
Sorted edges: CD(7), BC(8), DE(9), BD(10), CE(11), AB(12), EF(14), AC(15), CF(18), AF(20).
Edges added to MST in order: CD, BC, DE, AB, EF.
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
(b)(ii) State the minimum total length of cable required. [2]
Hint
Hint
Hint
Sum the weights of the MST edges found in (i).
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
Total = 7 + 8 + 9 + 12 + 14 = 50 km.
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
(c)(i) Use the nearest neighbour algorithm, starting at A, to find an upper bound for the salesperson’s route. [4]
Hint
Hint
Hint
From each current town, move to the closest unvisited town.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
Route: A → B (12) → C (8) → D (7) → E (9) → F (14) → A (20). Total = 12+8+7+9+14+20 = 70 km.
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
(c)(ii) By deleting vertex A, find a lower bound for the route length. [3]
Hint
Hint
Hint
Compute MST of remaining vertices B–F and add two smallest A‑connections.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
MST of {B,C,D,E,F}: edges CD(7), BC(8), DE(9), EF(14) sum = 38. Two smallest from A: AB(12), AC(15). Lower bound = 38+12+15 = 65 km.
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
(d) Determine if the original graph contains an Eulerian circuit. Justify your answer. [2]
Hint
Hint
Hint
Count the degree of each vertex; Eulerian circuit exists only if all degrees are even.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
Vertex degrees: A=3, B=3, C=4, D=3, E=3, F=3. More than two odd‐degree vertices ⇒ no Eulerian circuit.
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
(e) Find the minimum length of a route starting and finishing at A that traverses every road at least once (Chinese Postman). [3]
Hint
Hint
Hint
Identify odd vertices, find minimum matching, add those path lengths to sum of all edges.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
Odd vertices: A, B, D, E, F. Minimum matching: AB(12) + DE(9) = 21. Sum of all edges = 124. Total = 124 + 21 = 145 km.
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
