Topic 3.15: Adjacency matrices (HL only) Questions

A directed graph has the arrow A→B but not B→A. In the adjacency matrix this means:

In an undirected graph, the adjacency matrix is always:

A bus network of three stops X, Y, Z has two-way routes X–Y and Y–Z only. Write down the adjacency matrix, taking the order X, Y, Z, and state whether it is symmetric.

A weighted (distance) matrix differs from an adjacency matrix because its entries store:

To count walks of length 5 between two vertices, you compute:

A one-way street network of three junctions S, T, U has arrows S→T, T→U and U→S. Write down the adjacency matrix in the order S, T, U.

For a network with adjacency matrix A = ((0,1,1),(1,0,1),(1,1,0)) (vertices A, B, C), use your GDC to find A², then state the number of walks of length 2 from A to C.

Interpret this value.

A walk of length 4 in a graph uses how many edges and visits how many vertices (counting repeats)?

Sketch the graph.

Find what the entry in row $A$, column $C$ of ${\mathbf{M}}^3$ represents.

A delivery network of three depots L, M, N has two-way roads with distances (km): L–M = 5, M–N = 8, L–N = 12. Write down the distance (weighted) matrix in the order L, M, N, and find the length of the route L → M → N. Comment on whether it beats the direct road L–N.

A directed web-link network of four pages P, Q, R, S has adjacency matrix A = ((0,1,1,0),(0,0,1,1),(0,0,0,1),(1,0,0,0)). Use your GDC to find the number of directed walks of length 2 from P to S.

A triangle of cities A, B, C is fully connected by two-way roads, with adjacency matrix A = ((0,1,1),(1,0,1),(1,1,0)). Use a GDC to find the number of closed walks of length 4 that start and end at A, and explain how you read it off.