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 an undirected graph, can be constructed using the concept of adjacency matrices. 

The adjacency matrix is often also referred to as a connection matrix or a vertex matrix. It is a part of Class 12 Maths and can be defined as a matrix containing rows and columns that are generally used to represent a simple labeled graph. Numbers such as 0 or 1 are present in the position of (Vi, Vj). However, this depends on whether Vi and Vj are adjacent to each other or not.

To put it simply, an adjacency matrix is a compact way to represent the finite graph containing n vertices of a m x m matrix M. 

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 labeled graph, with the two numbers 0 or 1 in the position of (Vi, Vj) according to the condition whether the two Vi and Vj are adjacent or not. From the Adjacency matrix definition, we already know it can be picturized 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 be 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. 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 Vj of 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 be given by, 

(Image will be uploaded soon)

Here, the value is equal to the number of edges from vertex I to vertex j. For an undirected graph, the value 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 the image will be uploaded soonThe adjacency matrix example using coordinates can be written as the 

(Image will be uploaded soon)

Properties of Adjacent Matrix –

The following are the fundamental properties of the adjacent matrix:

1. Matrix Powers: This is one of the most well-known properties of the 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 eigenvalues of the connection matrix of any given graph can be clearly defined in 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 labeling 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.

For an undirected graph, we will have to depend on the given lines and loops to construct a proper graph. That means each edge or line will add 1 to the appropriate cell in the matrix. In contrast to this, each loop will add 2 to the cell in the matrix. Ultimately, by making use of this practice, we can find the degree of a vertex easily. We can achieve our aim in a matter of minutes by taking the sum of the values in either their respective row or column in the adjacency matrix. 

Adjacency Matrix of an Undirected Graph-

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

(Image will be uploaded soon)

The 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 Adjacency matrix of the above-directed graph can be written as − Adjacency Matrix of a Directed Graph

Adjacency Matrix of a Directed Graph

Questions to be Solved-

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

Ans: Let’s discuss the properties of the Adjacent matrix -An Adjacency Matrix named AVVVVVV is a 2D array of size V × V where V is equal to the number of vertices in an undirected graph. If there is an edge present between Vx to Vy then the value of the matrix \[A[V_{x}][V_{y}]\] = 1 and \[A[V_{y}][V_{x}]\] =1, otherwise the value would be equal to zero. If we have a directed graph, then there is an edge between Vx to Vy, then the value of  \[A[V_{x}][V_{y}]\] =1, otherwise the value will be equal to zero. 

Question 2) In a connected graph, calculate the distance between two vertices 𝑣i and 𝑣j when k is the smallest integer for which [Xk]ij is not equal to 0.

Ans: We know that k is the smallest integer such that \[[X_{k}]_{ij}\] is not equal to 0. Therefore, we can imply from here that there are no edge sequences of length 1, 2, ..., k −1. Similarly, there are no paths of length 1, 2, or k−1 between vertices 𝑣i and 𝑣j. Thus, we can say the shortest path between 𝑣i and 𝑣j is of length k so that d(𝑣i, 𝑣j ) comes out to be equal to k.