IB Mathematics AHL 3.15: Adjacency matrices AI HL Paper 1- Exam Style Questions- New Syllabus
▶️ Answer/Explanation
(a)(i)
No, \(G\) is not a simple graph because there are two different edges joining vertices \(A\) and \(B\). A simple graph cannot contain multiple edges between the same pair of vertices.
✅ Answer: No, because there is more than one edge between \(A\) and \(B\).
(a)(ii)
No, \(G\) is not connected. The vertices \(E\) and \(F\) form a separate component from the vertices \(A\), \(B\), \(C\) and \(D\).
For example, there is no path from \(A\) to \(F\).
✅ Answer: No, because not every pair of vertices is joined by a path.
(b)
The entry in row \(i\), column \(j\) records the number of edges joining vertices \(i\) and \(j\).
There are two edges between \(A\) and \(B\), one edge between \(B\) and \(C\), one edge between \(A\) and \(D\), one edge between \(B\) and \(D\), and one edge between \(E\) and \(F\).
| \(A\) | \(B\) | \(C\) | \(D\) | \(E\) | \(F\) | |
|---|---|---|---|---|---|---|
| \(A\) | \(0\) | \(2\) | \(0\) | \(1\) | \(0\) | \(0\) |
| \(B\) | \(2\) | \(0\) | \(1\) | \(1\) | \(0\) | \(0\) |
| \(C\) | \(0\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) |
| \(D\) | \(1\) | \(1\) | \(0\) | \(0\) | \(0\) | \(0\) |
| \(E\) | \(0\) | \(0\) | \(0\) | \(0\) | \(0\) | \(1\) |
| \(F\) | \(0\) | \(0\) | \(0\) | \(0\) | \(1\) | \(0\) |
✅ Answer: The missing entries are \(2\), \(2\), \(1\) and \(1\).
(c)
Let \(M\) be the adjacency matrix of \(G\).
The \((A,B)\) entry of \(M^k\) gives the number of walks of length \(k\) from \(A\) to \(B\).
Since the walks must have fewer than four edges, we count walks of lengths \(1\), \(2\) and \(3\).
For walks of length \(1\):
\(M_{AB}=2\).
For walks of length \(2\):
\((M^2)_{AB}=1\).
For walks of length \(3\):
\((M^3)_{AB}=14\).
Therefore, the required number is
\((M+M^2+M^3)_{AB}=2+1+14\)
\(=17\).
✅ Answer: \(17\) walks