Key Idea: An adjacency matrix stores a graph as a grid of numbers. Its powers count routes, and a weighted version stores distances, costs or times.
| Job | Tool |
|---|---|
| Whether connected | Adjacency matrix A (0s and 1s) |
| Count walks of length n | The entry of Aⁿ (use a GDC) |
| How far or how costly | Weighted (distance or cost) matrix |
Building the matrix
- Rows and columns list the vertices in the same order.
- Entry (i, j) = number of edges from i to j.
- Undirected ⇒ symmetric; directed ⇒ usually not.
- In a weighted matrix, replace each 1 with the length, cost or time. Use 0 (or a blank or ∞) where there is no edge.
Each power of A adds one more edge to the walks it counts.
P, Q and R are all joined. How many closed walks of length 2 start and end at P? 2: P→Q→P and P→R→P.
Roads P–Q = 4 and Q–R = 6. How long is P → Q → R? 10 km.
A graph has a one-way edge from X to Y. Is its matrix symmetric? No.
Which entry of A³ counts the 3-step walks from vertex 2 to vertex 1? Row 2, column 1.