3.15 Adjacency matrices and walksIB Maths: Applications and Interpretation HL: Flashcards

Exam questions on 3.15 Adjacency matrices and walks

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$.
   Use your GDC to find the number of walks of length 4 from $P$ to $S$.2 marks
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$.
   Use your GDC to find the number of walks of length 5 from $D$ to $C$.2 marks
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.
   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