Adjacency Matrix

What is Adjacency Matrix?

  • In much simpler terms the adjacency matrix definition can be thought of as a finite graph containing rows and columns.

  •  A directed graph as well as undirected graph can be constructed using the concept of adjacency matrices, Following is an Adjacency Matrix Example.

Following Are The Key Properties of an Adjacency Matrix:

  • The adjacency matrix can also be known as the connection matrix.

  • It  is a matrix that contains rows and columns which are used to represent a simple labelled graph, with the two numbers 0 or 1 in the position of (V, Vj) according to the condition whether  the two Vi and Vj are adjacent or not. 

  • From Adjacency matrix definition we already know it can be picturised as a compact way to represent the finite graph containing n number of vertices of a (m x m )matrix named M.

  •  Sometimes adjacency matrix is also known as vertex matrix and it can defined in the general form  as follows -

Image will be uploaded soon

If the simple graph has no self-loops, Then the vertex matrix should contain 0s in the diagonal and this is symmetric for an undirected graph. The connection matrix can be considered as a square array where each row represents the out-nodes of a graph and each column represents the in-nodes of a graph. Entry 1 represents that there is an edge between two nodes.

 

The adjacency matrix for an undirected graph is symmetric in nature. This indicates the value in the jth column and ith row is identical with the value in the ith column and jth row.. If the adjacency matrix is multiplied by itself,if there is any nonzero value present in the ith row and jth column, there is a route from Vi to Vjof length equal to two. It does not specify the path though there is a path created. The nonzero value of the matrix indicates the number of distinct paths present.

How To Create An Adjacency Matrix?

If we have a graph named G with n number of vertices, then the vertex matrix ( n x n ) can given by, 

Image will be uploaded soon

Here, the value aij  is equal to the number of edges from the vertex i to the vertex  j. For an undirected graph, the value aij is equal to aji for all the values of i, j , so that the adjacency matrix becomes a symmetric matrix.

Here’s an adjacency matrix example  and from the given directed graph, it is written as

Image will be uploaded soon

The adjacency matrix example using coordinates can be written as ,s

Image will be uploaded soon

Properties of Adjacent Matrix –

The following are the fundamental properties of adjacent matrix:

1) Matrix Powers

This is one of the most well-known properties of adjacent matrix to get information about any given graph from operations on any matrix through its powers. The entries of the powers of any given matrix give information about the paths in the given graph. The theorem given below represents the powers of any adjacency matrix.

 

Theorem You Need To Know: Let us take for example, A be the connection matrix of any given graph. Then the entries that are i, j of An counts n-steps walks from vertex i to j.

 

2) Spectrum

 

The study of the eigen values of the connection matrix of any given graph can be clearly defined in the spectral graph theory. Suppose we assume that, A is equal to the connection matrix of a k-regular graph and v be known as the all-ones column vector in Rn. We can say that the i-th entry of A is equal to the sum of the entries in the ith row of  the matrix A. This represents that the number of edges proceeds from vertex i, which is exactly k. So we can say,

 

Image will be uploaded soon

  Here the variable V is an eigenvector of the matrix A that contains the eigenvalue k

3) Isomorphisms

The given two graphs are said to be isomorphic if one graph can be obtained from the other by relabeling vertices of another graph. It is noted that the isomorphic graphs need not have the same adjacency matrix. Because this matrix depends on the labelling of the vertices. But the adjacency matrices of the given isomorphic graphs are closely related.

 

Theorem: Assume that, G and H be the graphs having n vertices with the adjacency matrices A and B. Then G and H are said to be isomorphic if and only if there is an occurrence of permutation matrix P such that B=PAP-1.

Adjacency Matrix of an Undirected Graph-

Matrix

a

b

c

d

a

0

1

1

0

b

1

0

1

0

c

1

1

0

1

d

0

0

1

0


Let us consider the following undirected graph and construct the adjacency matrix for the graph −

Image will be uploaded soon

Adjacency matrix of the above undirected graph can be represented as the above.

Now let us consider the following directed graph and construct the adjacency matrix for it −

Image will be uploaded soon

Adjacency matrix of the above directed graph can be written as −

Adjacency Matrix of a Directed Graph

Matrix

a

b

c

d

a

0

1

1

0

b

0

0

1

0

c

0

0

0

1

d

0

0

0

0


Questions to be Solved-

Question 1) List down the properties of an Adjacent Matrix.

Answer)Let’s discuss the properties of Adjacent matrix -

  1. An Adjacency Matrix named A[V][V] is basically a 2D array of size V × V where V is  equal to the number of vertices in a undirected graph.

  2. If there is an edge present between Vx to Vy then the value of the matrix A[Vx][Vy] = 1 and A[Vy][Vx]=1, otherwise the value would be equal to zero.

  3. If we have a directed graph, then there is an edge between Vx to Vy, then the value of  A[Vx][Vy]=1, otherwise the value will be  equal to zero.

FAQ (Frequently Asked Questions)

1. What is an adjacency matrix with example and how is the adjacency matrix calculated?

The adjacency matrix, sometimes also referred to as the connection matrix, of an easy labeled graph may be a matrix with rows and columns labeled by graph vertices, with a 1 or 0 in position consistent with whether and. are adjacent or not. For an easy graph with no self-loops, the adjacency matrix must have 0s on the diagonal.

The size of the adjacency matrix is adequate to the amount of vertices within the graph. it's a matrix (that is that the number of rows is adequate to the amount of columns). has one common edge, then element (a, b) = 1 and element (b, a) = 1.


2. What's an adjacency list and explain the difference between adjacency matrix and incidence matrix?

In graph theory and computing , an adjacency list may be a collection of unordered lists that represent a finite graph. Each list describes the set of neighbors of a vertex within the graph. This is often one among several commonly used representations of graphs to be used in computer programs.

Here’s the difference between adjacency matrix and incidence matrix -
The adjacency matrix should be distinguished from the incidence matrix for a graph, a special matrix representation whose elements indicate whether vertex–edge pairs are incident or not, and degree matrix which contains information about the degree of every vertex.