3.15 Adjacency matrices and walksIB Maths: Applications and Interpretation HL: Subtopic test

1. 1
   A network has four routers $P$, $Q$, $R$ and $S$. The links are $PQ$, $PR$, $QR$ and $RS$, and each link works in both directions. The network is modelled as a graph with the routers as vertices and the links as edges. Let $\mathbf{A}$ be its adjacency matrix with rows and columns in the order $P$, $Q$, $R$, $S$.

   (a)

   Which of these is the row of $\mathbf{A}$ that belongs to router $R$?

   [1 mark]

   • A$(1,1,0,1)$
   • B$(1,1,1,1)$
   • C$(0,0,1,0)$
   • D$(1,1,0,0)$

   (b)

   Find the number of walks of length 3 from $P$ to $S$.

   [1 mark]

   • A$0$
   • B$2$
   • C$1$
   • D$3$

   (c)

   Use your GDC to find the number of walks of length 4 from $P$ to $S$.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A delivery company has four hubs $A$, $B$, $C$ and $D$ with one-way routes $A\to B$, $B\to C$, $C\to A$, $C\to D$ and $D\to B$. This is modelled as a directed graph. Let $\mathbf{M}$ be its adjacency matrix, where the entry in row $i$, column $j$ is the number of routes from hub $i$ to hub $j$, in the order $A$, $B$, $C$, $D$.

   (a)

   Find the number of walks of length 2 from $C$ to $B$.

   [1 mark]

   • A$0$
   • B$1$
   • C$3$
   • D$2$

   (b)

   Find the number of walks of length 3 from $A$ to $A$.

   [1 mark]

   • A$0$
   • B$1$
   • C$2$
   • D$3$

   (c)

   Use your GDC to find the number of walks of length 5 from $D$ to $C$.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   Four villages $W$, $X$, $Y$ and $Z$ are joined by two-way roads, with distances in km: $WX$ is 12, $WY$ is 7, $XY$ is 5, $XZ$ is 9 and $YZ$ is 4. There are no other roads.

   (a)

   Write down the weighted adjacency table for the villages, in the order $W$, $X$, $Y$, $Z$, using $\text{–}$ where there is no direct road.

   [3 marks]

   (b)

   The adjacency matrix of the road network, ignoring distances, is $\mathbf{B}=\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}$.
   Use your GDC to find (i) the number of walks of length 3 from $W$ to $Z$, (ii) the number of walks of length at most 3 from $W$ to $Z$.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A small website has four pages $A$, $B$, $C$ and $D$. Page $A$ links to $B$ and $C$; page $B$ links to $C$; page $C$ links to $A$ and $D$; page $D$ links to $A$. A surfer on a page clicks one of its links at random, each link equally likely. The surfer's movement is modelled by the transition matrix $\mathbf{T}$, whose entry in row $i$, column $j$ is the probability of moving from page $j$ to page $i$, with the pages in the order $A$, $B$, $C$, $D$.

   (a)

   (i) Write down the transition matrix $\mathbf{T}$.
   (ii) The surfer starts on page $A$. Find the probability of being on each page after 2 clicks.
   (iii) State why every column of $\mathbf{T}$ sums to 1.

   [6 marks]

   (b)

   (i) Use your GDC to find the steady state vector $\mathbf{s}$ satisfying $\mathbf{T}\mathbf{s}=\mathbf{s}$, where the entries of $\mathbf{s}$ sum to 1.
   (ii) Write down the pages with the highest PageRank, and explain what this means for the surfer.
   (iii) The owner of page $D$ adds a link from $D$ to $B$, so $D$ now links to both $A$ and $B$. Write down the new column $D$ of $\mathbf{T}$.

   [6 marks]

   Total for question 4: 12 marks

End of questions