RevisionDojo

Exercises for Question Type 4: Finding lengths of paths between vertices using adjacency matrices - IB | RevisionDojo

Question 1

Skill question

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 paths of length 2.

Question 2

Skill question

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.

Question 3

Skill question

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}, $$compute $(A^2)_{1,4}$ and explain its interpretation in terms of 'friend‐of‐a‐friend' connections.

Question 4

Skill question

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.

Question 5

Skill question

Given the adjacency matrix 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},

how many distinct routes of exactly two legs (two buses) exist from city A to city D?

Question 6

Skill question

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}, $$compute the number of distinct 2‐hop data paths that start and end at computer 3 (i.e. $(A^2)_{3,3}$).

Question 7

Skill question

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.

Question 8

Skill question

For the same network in question 4, determine the total number of two‐transfer routes (paths of length 3) starting and ending at city B.

Question 9

Skill question

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. ow sum of the first row of $A^3$).

Question 10

Skill question

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$.

Question 11

Skill question

Given the adjacency matrix 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?

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