Adjacency Matrix

Let a_ij denote the number of edges (V_i, V_j) then A = [a_ij]_m×m is called adjacency matrix of G if

$a_{ij}=\{\begin{array}{cc}1& \text{ if }\left(V_i,V_j\right)\text{ is an edges }\\ 0& \text{ otherwise }\end{array}$

1.0Definition of Adjacency Matrix

In graph theory, an adjacency matrix is a square matrix that represents a finite graph. The elements of this matrix indicate whether pairs of vertices in the graph are connected by an edge. For a graph with n vertices, the adjacency matrix is an n × n matrix where the element Aij is:

• 1 if an edge exists between vertex i and vertex j;
• 0 if no edge exists between vertex i and vertex j.

This matrix representation provides a powerful tool for analyzing and manipulating graph structures, making it essential for studying various types of graphs, including undirected and directed graphs.

2.0Adjacency Matrix for Undirected Graphs

In an undirected graph, the edges are not directional, meaning the edge between two vertices is bidirectional. Consequently, the adjacency matrix for an undirected graph is symmetric. If there is an edge between vertices i and j, then both A_ij and A_ji will be 1.

Example: 

Consider an undirected graph with 4 vertices V = {A, B, C, D} and the following edges:

The adjacency matrix for this graph is:

$V=\left[\begin{array}{llll}0& 1& 1& 0\\ 1& 0& 0& 1\\ 1& 0& 0& 0\\ 0& 1& 0& 0\end{array}\right]$

Here, the matrix is symmetric about the diagonal, indicating the undirected nature of the graph.

3.0Adjacency Matrix for Directed Graphs

In a directed graph, the edges have a specific direction, meaning they go from one vertex to another and not necessarily in both directions. The adjacency matrix of a directed graph does not need to be symmetric.

Example: 

Consider a directed graph with 4 vertices V = {A, B, C, D} and the following directed edges:

The adjacency matrix for this graph is:

$V=\left[\begin{array}{llll}0& 1& 1& 0\\ 0& 0& 0& 1\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right]$

This matrix is not symmetric, which reflects the directed nature of the graph.

4.0Properties of Adjacency Matrices

1. Symmetry: The adjacency matrix of an undirected graph is always symmetric.
2. Diagonal Elements: In a simple graph, the diagonal elements of the adjacency matrix are 0, as there are no self-loops (no vertex is connected to itself)
3. Sparsity: For large graphs, adjacency matrices are typically sparse, meaning most elements are 0, as the number of edges is usually much smaller than the number of possible connections.
4. Degree of Vertices: For an undirected graph, the degree of a vertex can be calculated by summing the values in its corresponding row (or column, due to symmetry). For directed graphs, the out-degree is the sum of the row, and the in-degree is the sum of the column.

5.0Solved Examples on Adjacency Matrix

Example 1: Consider the undirected graph G as shown below. Find the Adjacency matrix.

Solutions:

$A=\left[\begin{array}{lllll}0& 1& 0& 0& 1\\ 1& 0& 1& 0& 0\\ 0& 1& 0& 1& 0\\ 0& 0& 1& 0& 1\\ 1& 0& 0& 1& 0\end{array}\right]$

Example 2: Find the Adjacency matrix of graph G.

Solutions:

$A=\left[\begin{array}{lllll}0& 1& 0& 0& 1\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0\end{array}\right]$

Example 3: Consider the undirected graph G as shown below. Find the Adjacency matrix.

Solutions:

$G=\left[\begin{array}{llll}0& 0& 1& 1\\ 0& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 0\end{array}\right]$

Example 4: Find the Adjacency matrix of the graph.

Solutions:

$G=\left[\begin{array}{lllll}0& 1& 0& 1& 0\\ 0& 0& 1& 0& 0\\ 1& 0& 0& 1& 1\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}\right]$

Example 5: Plot a graph given by the following adjacency matrix$G=\left[\begin{array}{llll}0& 0& 1& 1\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 0\end{array}\right]$

Solutions:

Example 6: Write down the Adjacency matrix of graph G.

Solutions:

$G=\left[\begin{array}{lllll}0& 1& 1& 0& 1\\ 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 0\\ 0& 1& 0& 0& 1\\ 1& 0& 0& 1& 0\end{array}\right]$

6.0Practice Questions on Adjacency Matrix

1. Construct the adjacency matrix for a directed graph with vertices V = {A, B, C, D}. 

2. Given the adjacency matrix below, determine whether the graph is directed or undirected:$\left[\begin{array}{llll}0& 1& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}\right]$
3. For a graph with vertices V = {P, Q, R, S} and the adjacency matrix:$\left[\begin{array}{llll}0& 1& 1& 0\\ 0& 0& 1& 1\\ 1& 0& 0& 1\\ 1& 1& 0& 0\end{array}\right]$List all the edges of the graph and state whether it is directed or undirected.
4. Construct the adjacency matrix for a directed graph with vertices V = {A, B, C, D, E}.