Adjacency Matrix Representation

00:00 5 marks

In graph theory, adjacency matrices are used to represent connections between nodes. For an undirected graph with four nodes, the adjacency matrix \(A\) is defined as follows: \(A_{ij} = 1\) if there is an edge between node \(i\) and node \(j\), and \(A_{ij} = 0\) otherwise. Given the adjacency matrix:

\(A = \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix}\)

Explain how this matrix encodes the graph’s connectivity. Is this graph regular? Justify your answer.

Hint Hint

Hint

Recall that the sum of each row in an adjacency matrix represents the degree of the corresponding node.

Answer Answer
Mark Scheme Mark Scheme
Explanation Explanation
Common Errors Common Errors
Real World Context Real World Context
Focus Focus
Formula Booklet

Answer Answer

Complete Answer

The matrix uses 1s to indicate connections between nodes. Each row’s sum equals the degree of that node. Here, every row sums to 2, so all nodes have degree 2 and the graph is regular.

Mark Scheme Mark Scheme

Answer Explanation Answer Explanation

Common Errors Common Errors

Focus Focus

Formula Booklet