IB Mathematics Applications & Interpretation Question Type 4: Finding Lengths of Paths Between Vertices Using Adjacency Matrices Exercises

Given the adjacency matrix $A$ of a transportation network between cities $\{A,B,C,D\}$: $$A=\left(\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 0& 1& 1& 0\end{array}\right)$$ Determine the number of distinct routes of exactly two legs (two buses) that exist from city $A$ to city $D$.

For the directed adjacency matrix $$A=\left(\begin{array}{cccc}0& 1& 1& 0\\ 0& 0& 1& 1\\ 1& 0& 0& 1\\ 1& 1& 0& 0\end{array}\right),$$ 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$).

Consider a graph representing four research groups $\{W,X,Y,Z\}$ with adjacency matrix $$A=\left(\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 0& 1& 1& 0\end{array}\right).$$ Compute the total number of distinct collaborative sequences of three steps starting at $W$ and ending at $Z$.

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

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.

Given the adjacency matrix $$A=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right),$$ compute $A^2$ and determine the number of distinct paths of length 2 from vertex 1 to vertex 3.

For the directed graph with adjacency matrix $$A=\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right),$$ compute $A^3$ and find the number of paths of length 3 from vertex 2 to vertex 4.

In a social network with adjacency matrix $$A=\left(\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 1& 1\\ 0& 1& 0& 1\\ 0& 1& 1& 0\end{array}\right)$$ calculate $(A^2{)}_{1,4}$ and interpret its meaning in terms of 'friend-of-a-friend' connections.

Given the adjacency matrix $A$ of a 6-city airline network, where cities are numbered 1–6: $$A=\left(\begin{array}{cccccc}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{array}\right)$$ How many routes of exactly 4 flights exist from city 2 to city 5?

In a network of 5 computers with adjacency matrix $$A=\left(\begin{array}{ccccc}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{array}\right),$$ calculate the number of distinct 2-hop walks that start and end at computer 3 (i.e., $(A^2{)}_{3,3}$).

A directed web graph has adjacency matrix $$A=\left(\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 1& 1\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right).$$ Determine whether there is at least one path of length 4 from page 1 to page 3 by checking $(A^4{)}_{1,3}>0$.