RevisionDojo

Question 1

Matrices and Graph Theory

Given the adjacency matrix $A$ of a transportation network between cities $\{A, B, C, D\}$ :

A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}

Determine the number of distinct routes of exactly two legs (two buses) that exist from city $A$ to city $D$ .

[3]

Question 2

For the directed adjacency matrix

A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix},

determine the total number of walks of length 3 originating at vertex 1 (i.e., the row sum of the first row of $A^3$ ).

[5]

Question 3

Consider a graph representing four research groups $\{W, X, Y, Z\}$ with adjacency matrix

A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}.

Compute the total number of distinct collaborative sequences of three steps starting at $W$ and ending at $Z$ .

[4]

Question 4

A directed network of four cities, A, B, C, and D, is represented by the adjacency matrix $\mathbf{A}$ and its square $\mathbf{A}^2$ shown below:

$\mathbf{A} = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}, \quad \mathbf{A}^2 = \begin{pmatrix} 3 & 3 & 3 & 1 \\ 2 & 2 & 2 & 1 \\ 3 & 2 & 3 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}$

where rows 1 to 4 and columns 1 to 4 correspond to cities A, B, C, and D respectively.

Determine the total number of two-transfer routes (paths of length 3) starting and ending at city B.

[3]

Question 5

Let $G$ be a cycle graph on 5 vertices with adjacency matrix $C$ . Compute the entry $(C^2)_{3,5}$ and interpret its meaning in terms of walks of length 2.

[4]

Question 6

Given the adjacency matrix

A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix},

compute $A^2$ and determine the number of distinct paths of length 2 from vertex 1 to vertex 3.

[3]

Question 7

For the directed graph with adjacency matrix

A = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix},

compute $A^3$ and find the number of paths of length 3 from vertex 2 to vertex 4.

[5]

Question 8

Matrices in social networks.

In a social network with adjacency matrix

A = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}

calculate $(A^2)_{1,4}$ and interpret its meaning in terms of 'friend-of-a-friend' connections.

[3]

Question 9

Given the adjacency matrix $A$ of a 6-city airline network, where cities are numbered 1–6:

A = \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \end{pmatrix}

How many routes of exactly 4 flights exist from city 2 to city 5?

[4]

Question 10

In a network of 5 computers with adjacency matrix

A = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{pmatrix},

calculate the number of distinct 2-hop walks that start and end at computer 3 (i.e., $(A^2)_{3,3}$ ).

[3]

Question 11

A directed web graph has adjacency matrix

A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}.

Determine whether there is at least one path of length 4 from page 1 to page 3 by checking $(A^4)_{1,3} > 0$ .

[5]

Question Type 4: Finding lengths of paths between vertices using adjacency matrices Exercises