Introduction to Adjacency Matrices

Graph theory gives us powerful tools for modelling networks , social connections, transport systems, the internet, and more. One of the most useful representations of a graph is the adjacency matrix, which encodes the entire structure of a graph in a compact, mathematical format that we can manipulate algebraically.

Before defining the matrix, recall the key vocabulary:

A graph consists of vertices (nodes) connected by edges (links).
In an undirected graph, edges have no direction; in a directed graph (digraph), each edge has a specific direction from one vertex to another.
The degree of a vertex is the number of edges incident to it (for directed graphs, we distinguish in-degree and out-degree).

Adjacency Matrix: For a graph with $n$ vertices, an adjacency matrix $A$ is an $n \times n$ square matrix where each entry $a_{ij}$ represents the connection between vertex $i$ and vertex $j$ :

$a_{ij} = 1$ if there is an edge from vertex $i$ to vertex $j$
$a_{ij} = 0$ if there is no direct edge from vertex $i$ to vertex $j$

The power of this representation is that it transforms graph problems into matrix problems , and matrices are something we can compute with directly.

Note

For a simple graph (one with no self-loops and no multiple edges), the diagonal entries $a_{ii}$ are always 0, since no vertex is connected to itself.

For a multigraph (where two vertices may be connected by more than one edge), the entry $a_{ij}$ can be any non-negative integer , it records the number of edges between vertex $i$ and vertex $j$ . For example, $a_{ij} = 3$ means there are three distinct edges between those two vertices.

Note

For undirected graphs, the adjacency matrix is always symmetric: $a_{ij} = a_{j i}$ for all $i$ and $j$ . This is because an edge between vertices $i$ and $j$ goes both ways. For directed graphs (digraphs), the matrix is generally not symmetric.

Constructing an Adjacency Matrix

To build an adjacency matrix, label the vertices $1, 2, 3, \dots, n$ and then systematically fill in the $n \times n$ grid.

Step-by-step process:

List all vertices and assign each a row and a corresponding column.
For each pair of vertices $(i, j)$ , determine whether an edge exists.
Enter $1$ if an edge exists, $0$ if not (for a simple graph).
The diagonal is always $0$ for simple graphs (no self-loops).

Example

Consider an undirected simple graph with 5 vertices and the following edges:
$1 - 2, 1 - 4, 1 - 5, 2 - 3, 2 - 4, 3 - 4, 3 - 5, 4 - 5$

To construct the adjacency matrix, place a $1$ in position $(i, j)$ and position $(j, i)$ for each edge (since the graph is undirected), and $0$ everywhere else. The diagonal entries are all $0$ .

$A = 0101110110010111110110110$

Reading the matrix:

Row $1$ , Column $2$ has entry $1$ → there is an edge between vertex $1$ and vertex $2$ . ✓
Row $1$ , Column $3$ has entry $0$ → there is no direct edge between vertex $1$ and vertex $3$ . ✓
The matrix is symmetric about the main diagonal, confirming this is an undirected graph. ✓

Degree check: The sum of row $i$ equals the degree of vertex $i$ .

Vertex 1: $0 + 1 + 0 + 1 + 1 = 3$ → degree 3
Vertex 4: $1 + 1 + 1 + 0 + 1 = 4$ → degree 4

Exam Tip

A quick check: in an undirected graph, the sum of row $i$ (or column $i$ ) equals the degree of vertex $i$ , the number of edges connected to it.

Example

Multigraph example: Suppose vertices $A$ and $B$ are connected by 2 edges, and $B$ and $C$ are connected by 1 edge, with no other connections. The adjacency matrix is:

$A = 020201010$

Note that entries can be greater than $1$ for multigraphs. The matrix remains symmetric for an undirected multigraph.

Free preview

9 more sections in this topic

Introduction to Adjacency Matrices

Before defining the matrix, recall the key vocabulary:

A graph consists of vertices (nodes) connected by edges (links).
In an undirected graph, edges have no direction; in a directed graph (digraph), each edge has a specific direction from one vertex to another.
The degree of a vertex is the number of edges incident to it (for directed graphs, we distinguish in-degree and out-degree).

Adjacency Matrix: For a graph with $n$ vertices, an adjacency matrix $A$ is an $n \times n$ square matrix where each entry $a_{ij}$ represents the connection between vertex $i$ and vertex $j$ :

$a_{ij} = 1$ if there is an edge from vertex $i$ to vertex $j$
$a_{ij} = 0$ if there is no direct edge from vertex $i$ to vertex $j$

The power of this representation is that it transforms graph problems into matrix problems , and matrices are something we can compute with directly.

Note

For a simple graph (one with no self-loops and no multiple edges), the diagonal entries $a_{ii}$ are always 0, since no vertex is connected to itself.

Note

Constructing an Adjacency Matrix

To build an adjacency matrix, label the vertices $1, 2, 3, \dots, n$ and then systematically fill in the $n \times n$ grid.

Step-by-step process:

List all vertices and assign each a row and a corresponding column.
For each pair of vertices $(i, j)$ , determine whether an edge exists.
Enter $1$ if an edge exists, $0$ if not (for a simple graph).
The diagonal is always $0$ for simple graphs (no self-loops).

Example

Consider an undirected simple graph with 5 vertices and the following edges:
$1 - 2, 1 - 4, 1 - 5, 2 - 3, 2 - 4, 3 - 4, 3 - 5, 4 - 5$

To construct the adjacency matrix, place a $1$ in position $(i, j)$ and position $(j, i)$ for each edge (since the graph is undirected), and $0$ everywhere else. The diagonal entries are all $0$ .

$A = 0101110110010111110110110$

Reading the matrix:

Row $1$ , Column $2$ has entry $1$ → there is an edge between vertex $1$ and vertex $2$ . ✓
Row $1$ , Column $3$ has entry $0$ → there is no direct edge between vertex $1$ and vertex $3$ . ✓
The matrix is symmetric about the main diagonal, confirming this is an undirected graph. ✓

Degree check: The sum of row $i$ equals the degree of vertex $i$ .

Vertex 1: $0 + 1 + 0 + 1 + 1 = 3$ → degree 3
Vertex 4: $1 + 1 + 1 + 0 + 1 = 4$ → degree 4

Exam Tip

A quick check: in an undirected graph, the sum of row $i$ (or column $i$ ) equals the degree of vertex $i$ , the number of edges connected to it.

Example

Multigraph example: Suppose vertices $A$ and $B$ are connected by 2 edges, and $B$ and $C$ are connected by 1 edge, with no other connections. The adjacency matrix is:

$A = 020201010$

Note that entries can be greater than $1$ for multigraphs. The matrix remains symmetric for an undirected multigraph.

Free preview

AHL 3.15—Adjacency matrices and tables

Introduction to Adjacency Matrices

Constructing an Adjacency Matrix

9 more sections in this topic

AHL 3.15—Adjacency matrices and tables

Introduction to Adjacency Matrices

Constructing an Adjacency Matrix

9 more sections in this topic