Consider a directed graph representing a network of 5 cities. The connections between the cities are recorded in an adjacency matrix A where the entry \(a_{ij}\) is 1 if there is a direct route from city i to city j, and 0 otherwise. The adjacency matrix A is given as follows:
\( A = \begin{bmatrix} 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \)
Question
Compute \( A^2 \). Explain what the non-zero entries of \( A^2 \) represent in terms of paths between cities.
Hint
Hint
Hint
The entry \( (A^2)_{ij} \) is obtained by taking the dot product of row i of A and column j of A. This sum represents the number of 2-step paths from city i to city j.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
- Formula Booklet
Complete Answer
\( A^2 = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{bmatrix} \). A non-zero entry \( (A^2)_{ij} = n \) indicates that there are exactly \( n \) paths of length 2 from city i to city j.
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
Based on matrix \( A \) and your computed matrix \( A^2 \), assess whether the network is strongly connected. Justify your conclusion.
Hint
Hint
Hint
A directed network is strongly connected if and only if for every pair of cities (i, j), there is a directed path from city i to city j. Examine the rows of \( A \) and \( A^2 \) to determine if every city can reach every other city.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
- Formula Booklet
Complete Answer
The network is not strongly connected. City 5 cannot be reached from any other city because row 5 of both \( A \) and \( A^2 \) (and consequently any higher power of \( A \)) are all zeros, indicating no outgoing paths from city 5. For strong connectivity, there must be a path from every city to every other city, and this condition is not met for city 5.
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
Question
Propose a minimal route from city 1 to city 4 using the information from matrix \( A \) and your computations of \( A^2 \). Describe the sequence of cities in your chosen route and state the length of the route.
Hint
Hint
Hint
Examine matrix \( A \) for direct routes and \( A^2 \) for 2-step routes originating from city 1. If neither provides a path to city 4, consider paths of length 3 or more by examining connections from intermediate cities reachable from city 1.
-
Answer
Answer
-
Mark Scheme
Mark Scheme
-
Explanation
Explanation
- Formula Booklet
Complete Answer
A minimal route from city 1 to city 4 is: city 1 \( \rightarrow \) city 2 \( \rightarrow \) city 3 \( \rightarrow \) city 4. This route has a length of 3 steps. This is confirmed by noting that \( A_{12} = 1 \), \( A_{23} = 1 \), and \( A_{34} = 1 \). There is no direct route from city 1 to city 4 (\( A_{14} = 0 \)) and no 2-step route (\( (A^2)_{14} = 0 \)).
-
Mark Scheme
Mark Scheme
-
Answer Explanation
Answer Explanation
