This question explores network analysis applied to a system of interconnected data servers in a research facility. The servers (nodes) are labelled A, B, C, D, E, F. The connections (edges) represent high-speed data links, and their weights represent the cost (in units of $100) of transmitting a large data packet between servers.
The connections and their costs are as follows:
A is connected to B (cost 3) and C (cost 5).
B is connected to A (cost 3), C (cost 4), and D (cost 6).
C is connected to A (cost 5), B (cost 4), D (cost 2), and E (cost 7).
D is connected to B (cost 6), C (cost 2), E (cost 1), and F (cost 8).
E is connected to C (cost 7), D (cost 1), and F (cost 4).
F is connected to D (cost 8) and E (cost 4).
There is no direct link between A and F.
(a) Represent the network connections and costs using a weighted adjacency table (matrix), using ∞ or a suitable large number for non-existent direct links. [3]
A research team needs to establish a secure sub-network connecting servers A, B, C, D, E such that the total cost of the links used is minimized, ensuring all these five servers are connected.
(b) (i) Starting from vertex A, use Prim’s algorithm to find the minimum spanning tree connecting servers A, B, C, D, E. List the edges in the order they are selected.
(ii) Calculate the minimum cost to establish this secure sub-network. [6]
Data packets can sometimes fail during transmission along a link. The probability of a successful transmission along any single link is \(p = 0.9\), independent of other links. A data packet needs to be sent from server A to server F. Two possible paths are considered: Path 1 (A-C-D-F) and Path 2 (A-B-D-F).
(c) (i) Calculate the probability that a packet sent along Path 1 arrives successfully at F.
(ii) Calculate the probability that a packet sent along Path 2 arrives successfully at F. [4]
(d) Find the probability that a packet sent from A arrives successfully at F via at least one of these two paths, assuming the paths operate independently once the packet leaves A. [3]
The number of data transmission requests between any two servers in a given hour follows a Poisson distribution. The average number of requests originating from server A to any directly connected server (B or C) is 1.5 requests per hour for each link.
(e) Find the probability that in a given hour, server A sends:
(i) exactly 2 requests to server B.
(ii) a total of 4 requests to servers B and C combined. [5]
A new direct link A-F is proposed.
(f) If this link AF is added, explain how it would affect the calculation required in part (b)(i). [2]
(g) Let \(W\) be the adjacency matrix where entries are 1 if a direct link exists and 0 otherwise (ignoring weights, and assuming the AF link is not present). Find \(W^2\) and interpret the meaning of the entry in the first row and fourth column (element (1,4)) of \(W^2\) in the context of the server network. [4]
Question
Represent the network connections and costs using a weighted adjacency table (matrix), using ∞ or a suitable large number for non-existent direct links. [3]
Hint
Hint
Hint
Label the rows and columns as A, B, C, D, E, F. Enter the provided weights and use ∞ (or a large number) for non-existent links; use 0 on the diagonal.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
|
A |
B |
C |
D |
E |
F |
| A |
0 |
3 |
5 |
∞ |
∞ |
∞ |
| B |
3 |
0 |
4 |
6 |
∞ |
∞ |
| C |
5 |
4 |
0 |
2 |
7 |
∞ |
| D |
∞ |
6 |
2 |
0 |
1 |
8 |
| E |
∞ |
∞ |
7 |
1 |
0 |
4 |
| F |
∞ |
∞ |
∞ |
8 |
4 |
0 |
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
(i) Starting from vertex A, use Prim’s algorithm to find the minimum spanning tree connecting servers A, B, C, D, E. List the edges in the order they are selected.
(ii) Calculate the minimum cost to establish this secure sub-network. [6]
Hint
Hint
Hint
From A, select the smallest available edge. Continue adding the smallest edge that connects a new vertex. Then sum the weights of the selected edges.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
Edges selected: AB, BC, CD, DE. Total minimum cost = 3 + 4 + 2 + 1 = 10 (units of $100, i.e. $1000).
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
(i) Calculate the probability that a packet sent along Path 1 (A-C-D-F) arrives successfully at F.
(ii) Calculate the probability that a packet sent along Path 2 (A-B-D-F) arrives successfully at F. [4]
Hint
Hint
Hint
Each path has 3 links. Multiply 0.9 three times for each path.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
For both paths, the probability is \(0.9^3 = 0.729\).
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
Find the probability that a packet sent from A arrives successfully at F via at least one of these two paths, assuming the paths operate independently once the packet leaves A. [3]
Hint
Hint
Hint
Use the formula \(P(S_1 \cup S_2)=P(S_1)+P(S_2)-P(S_1 \cap S_2)\), where the intersection involves success along all distinct links.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
The overall probability is \(0.729 + 0.729 – 0.9^5 \approx 0.868\).
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
The number of data transmission requests between any two servers in a given hour follows a Poisson distribution with a mean of 1.5 for each link.
(i) Find the probability that server A sends exactly 2 requests to server B.
(ii) Find the probability that server A sends a total of 4 requests to servers B and C combined. [5]
Hint
Hint
Hint
For a Poisson variable with mean \(\lambda\), use \(P(k)=e^{-\lambda}\,\frac{\lambda^k}{k!}\). For the combined request rate, add the means.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
(i) \(P(X=2)=e^{-1.5}\,\frac{1.5^2}{2!}\approx0.251\). (ii) For the sum with mean 3, \(P(T=4)=e^{-3}\,\frac{3^4}{4!}\approx0.168\).
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
If a new direct link A-F is added, explain how it would affect the calculation required in part (b)(i). [2]
Hint
Hint
Hint
Consider that the new link provides an additional candidate edge for the MST, potentially altering the edge selection process.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
The inclusion of the AF link would add another candidate edge in Prim’s algorithm, which may change the order in which edges are selected when forming the MST.
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
Let \(W\) be the adjacency matrix where entries are 1 if a direct link exists and 0 otherwise (AF link not included). Compute \(W^2\) and interpret the entry in the first row and fourth column (element (1,4)) of \(W^2\) in the context of the server network. [4]
Hint
Hint
Hint
Square the binary matrix \(W\) and note that the (1,4) entry counts the number of distinct paths of exactly two steps from A to D.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
Complete Answer
The (1,4) entry of \(W^2\) is 2, indicating there are 2 distinct paths of exactly two steps from server A to D (namely, A–B–D and A–C–D).
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
