This question explores network analysis applied to a city’s public transport system. The system connects five main hubs: Central (C), North (N), East (E), South (S), and West (W). The direct connections (routes) and their travel times (in minutes) are represented by the weighted graph described below.
Graph Description:
Vertices: C, N, E, S, W
Edges and Weights:
• (C, N) weight 10
• (C, E) weight 12
• (C, S) weight 8
• (C, W) weight 15
• (N, E) weight 7
• (N, W) weight 18
• (E, S) weight 9
• (S, W) weight 11
(a) Represent the direct connections (ignoring travel times for this part) using an adjacency matrix A, where rows and columns correspond to C, N, E, S, W in that order. [3]
(b) Calculate A². [2]
(c) Using your answer to part (b), state the number of ways to travel between North (N) and South (S) using exactly two direct routes. Describe these routes. [3]
(d) Use Prim’s algorithm, starting at Central (C), to find the minimum total time required to create a network connecting all hubs (Minimum Spanning Tree). List the edges in the order they are selected and state the total minimum time. [6]
(e) Use Dijkstra’s algorithm to find the shortest path and the minimum travel time from West (W) to East (E). Show the steps of the algorithm clearly. [7]
(f) Determine the range of values for x such that adding the route (N,S) would change the shortest path from West (W) to East (E) found in part (e). [3]
(g) Determine if an Eulerian circuit exists for this network of direct connections. Justify your answer. [3]
Question
Represent the direct connections (ignoring travel times for this part) using an adjacency matrix A, where rows and columns correspond to C, N, E, S, W in that order. [3]
Hint
Hint
Hint
Ensure a 5×5 matrix with zeros along the diagonal and 1’s indicating a direct connection.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
A = [[0, 1, 1, 1, 1], [1, 0, 1, 0, 1], [1, 1, 0, 1, 0], [1, 0, 1, 0, 1], [1, 1, 0, 1, 0]]
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
Using your answer to part (b), state the number of ways to travel between North (N) and South (S) using exactly two direct routes. Describe these routes. [3]
Hint
Hint
Hint
Examine the (N,S) entry in A² (2nd row, 4th column).
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
There are 3 ways: N-C-S, N-E-S, and N-W-S.
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
Use Prim’s algorithm, starting at Central (C), to find the minimum total time required to create a network connecting all hubs (Minimum Spanning Tree). List the edges in the order they are selected and state the total minimum time. [6]
Hint
Hint
Hint
Start at C and at each stage choose the smallest edge that connects a new vertex.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
Edges selected: (C,S) with 8, (S,E) with 9, (E,N) with 7, (S,W) with 11. Total minimum time = 35 minutes.
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
Use Dijkstra’s algorithm to find the shortest path and the minimum travel time from West (W) to East (E). Show the steps of the algorithm clearly. [7]
Hint
Hint
Hint
Start at W (distance 0), update the distances of its neighbours, and choose the vertex with the smallest temporary distance in each iteration.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
The shortest path is W → S → E with a total travel time of 20 minutes.
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
Determine the range of values for x such that adding the route (N,S) would change the shortest path from West (W) to East (E) found in part (e). [3]
Hint
Hint
Hint
Consider the alternative path W → S → N → E and set up an inequality for its total travel time compared to the current 20 minutes.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
0 < x < 2
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
Determine if an Eulerian circuit exists for this network of direct connections. Justify your answer. [3]
Hint
Hint
Hint
Check the degree (number of connections) for each vertex. An Eulerian circuit requires every vertex to have an even degree.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
No, an Eulerian circuit does not exist because vertices N, E, S, and W have odd degrees.
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
