Education Journalist | Study Abroad Lead
Adjacency Matrix is a square matrix used to describe the directed and undirected graph. Adjacency Matrix contains rows and columns that represent a labeled graph. The position of (Vi, Vj) is labeled on the graph with values equal to 0 and 1. This value depends on whether the vertices (Vi, Vj) are adjacent or not. The adjacency matrix is also referred to as the connection or vertex matrix.
| Table of Content |
Key Takeaways: Adjacency Matrix, Matrix, Determinant, Directed Graph, Undirected Graph, Vertex, Edges, Verticles, Square matrix
Adjacency Matrix
[Click Here for Sample Questions]
Adjacency Matrix is a simple way to represent a finite graph having n vertices of the square matrix M. The rows and columns of the Adjacency Matrix represent the position of vertices (Vi, VJ). In some books, the Adjacency Matrix is also referred to as a vertex matrix. The Adjacency or Connect Matrix is defined as
\(\left| \begin{array}{ll} 1 & \text { if } \mathrm{Pi} \rightarrow \mathrm{Pj} \\ 0 & \text { otherwise } \end{array} \right|\)
According to the definition, if the graph has no loops, then the adjacency matrix has 0s in the diagonal position. The value 1 states the edge between two vertices The adjacency matrix is symmetric for an undirected graph. The adjacency matrix is defined as a square matrix in which each row represents the out-vertice and the column represents the in-vertice of a graph.
For an undirected graph, the adjacency matrix is symmetric. In simple words, the value of an element in the jth row and ith column is identical to the value of ith row and jth column.
Also Read:
How to Create an Adjacency Matrix
[Click Here for Sample Questions]
If a graph containing n vertices is given then, the adjacency matrix of order n × n, M is given by
Adjacency Matrix
In the matrix given above, the value aij represents the number of vertices from i to j vertex. Since, for an undirected graph, the adjacency matrix is a symmetric matrix, therefore, aij = aji for all i and j.
Explanation:
Let graph G have vertex set {vhave v3, ….., vn} then, the adjacency matrix of graph G would be n × n matrix that will have 1 in (i, j) position only if there is an edge between vi and vj otherwise 0.
Also Read: Symmetric Matrix and Skew-Symmetric Matrices
Properties of Adjacency Matrix
[Click Here for Sample Questions]
The following are given below some fundamental properties of Adjacency Matrix
Matrix Powers: The best way to get the information about the graph from an operation on this matrix is through its powers.
Theorem: Let, M be the adjacency matrix of a graph then, the entries i, j of Mn (M1 an x M2 x M3 x…..) will count n-steps from vertex i to j.
Spectrum: The study of eigenvalues of an adjacency matrix of a given graph can be defined in spectral graph theory. Let's consider, M to be the adjacency matrix of a k-regular graph and u to be the column vector in Rn. Then according to the theorem, the ith entry of Mu is equal to the sum of entries in the ith row of M. Here, k is the number of edges starting from vertex i.
Therefore, we can say that Au = λu and it can be written as:
M =
\(\left[\begin{array}{c}1 \\ 1 \\ \vdots \\ 1\end{array}\right] \times\left[\begin{array}{c}k \\ k \\ \vdots \\ k\end{array}\right]=k\left[\begin{array}{c}1 \\ 1 \\ \vdots \\ 1\end{array}\right]\)
Here u is an eigenvector of matrix M having the eigenvalue equal to k.
Isomorphisms
Two graphs are said to be isomorphic if one graph can be formed by relabelling the vertices of another graph. It is important to note that two isomorphic graphs are not necessary to have the same connection matrix just because the graphs depend on their labeling of vertices.
Theorem: Suppose two graphs A and B have n vertices with adjacency matrices M and N respectively. Then the graphs A and B are said to be isomorphic only if permutation matrix P exists such as B = PAP-1.
Also Read: Vectors
Adjacency Matrix Undirected Graph
[Click Here for Sample Questions]
For an undirected graph, each edge adds 1 to the cell and each loop adds 2. By taking the sum of the values in either rows or columns, we can find the degree of a vertex. The example of an undirected graph is given below:
Undirected Graph
The adjacency matrix M is given by:
\(M=\left[\begin{array}{llllll} 0 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 \end{array}\right]\)
Maximum edges in Directed Graph
Let n be the total number of vertices in a directed graph D, then
D(n) = n(n - 1)
D(n): Maximum number of edges in the directed graph
Also Read:
| Related Articles | ||
|---|---|---|
| Transpose of a Matrix | Symmetric and Skew Symmetric Matrix | Invertible Matrix |
| Matrix Multiplication | Operations on Matrices | Determinant Formula |
Adjacency Matrix Directed Graph
[Click Here for Sample Questions]
The graph shown is an example of a directed graph. The adjacency matrix for the directed graph can be written by following the conventions used in the undirected graph.
Maximum edges in Undirected Graph
Let n be the total number of vertices in a directed graph D, then
D(n) = n(n -1)/2
D(n): Maximum number of edges in the directed graph
Things to Remember
- Adjacency Matrix is a simple way of representing the graph having n vertices of the square matrix M.
- The adjacency matrix is symmetric for an undirected graph.
- If the graph has no loops, then the adjacency matrix has 0s in the diagonal positions.
- The value 1 represents the edge between two vertices.
- If any adjacency matrix is multiplied by itself and if there is no non-zero value present in the jth column and ith row, then there is a route of length two in form between Vi and Vj.
Also Read:
Sample Questions
Ques. The Adjacency matrix M is given by \(\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ \end{bmatrix}\)
Find the total number of ways in which every vertex can walk using 2 edges. (5 marks)
Ans. To calculate the number of ways using 2 edges first calculate M2.
Then compare the corresponding vertices of M and M2.
The given Adjacency Matrix is
\(\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ \end{bmatrix}\)
Now calculate M2 (by using multiplication of matrix)
M2 = \(\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ \end{bmatrix}\) \(\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ \end{bmatrix}\)
According to the multiplication theorem, we have
M2 = \(\begin{bmatrix} 1 & 0 & 0 \\ 1 & 2 & 1 \\ 1 & 1 & 1 \\ \end{bmatrix}\)
The above matrix can be written as M2 = [ [1,0,0], [1,2,1], [1,1,1] ]
Also we have a matrix M that can be written as M = [ [1,0,0], [0,1,1], [1,1,0] ]
We can say that every vertex to walk using 2 edges is 0. As the first vertex of M is [1,0,0] and the first vertex of M2 is [1,0,0]. That means 1 - 1, 0 - 0, 0 - 0 = 0, 0, 0. So there are 0 ways for every vertex to walk using 2 edges.
Ques. Find the maximum number of edges in the graph shown below. (3 marks)
Ans. The above graph shown is an undirected graph.
For the undirected graph having ‘n’ vertices is denoted D(n) and is given by:
D(n) = n(n -1)/2
For the given graph, n(number of vertices) = 5
Hence, putting n=5 in the given formula we have,
D(n) = 5(5 -1)/2
= 5(4)/2
= 10
Therefore, the graph with 5 vertices can have a maximum of 10 edges.
Ques. For the given undirected graph find the adjacency matrix. (5 marks)
Ans. We have given an undirected graph of 6 vertices. So the adjacency matrix will be of the order
6 × 6.
To find the adjacency matrix we have to write the weights on every edge of the corresponding vertex.
The vertices of the graph can be written as:
Vertex 1 = [0,6,1,5,0,0]
Vertex 2 = [6,0,5,0,3,0]
Vertex 3 = [1,5,0,5,6,4]
Vertex 4 = [5,0,5,0,0,2]
Vertex 5 = [0,3,6,0,0,6]
Vertex 6 = [0,0,4,2,6,0]
Let the adjacency matrix M represent the vertices of the graph. Then we have,
\(M=\begin{bmatrix} 0 & 6 & 1 & 5 & 0 & 0 \\ 6 & 0 & 5 & 0 & 3 & 0 \\ 1 & 5 & 0 & 5 & 6 & 4 \\ 5 & 0 & 5 & 0 & 0 & 2 \\ 0 & 3 & 6 & 0 & 0 & 6 \\ 0 & 0 & 4 & 2 & 6 & 0 \end{bmatrix}\)
Ques. The Adjacency matrix M is given as
\(\begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}\)
Draw the graph of this adjacency matrix. (5 marks)
Ans. The order of the adjacency matrix M is 4 × 4. So, the number of nodes will be 4.
Let these 4 vertices be V1, V2, V3, and V4. Re-write the adjacency matrix as given below
M = 
Step 1: Write these 4 vertices as shown below:
Step 2: Now check the loop or self-loops and edges between two vertices.
For Vertex V1: No loop on the first node, edge from 1 to 2, no edge from 1 to 3 edge from 1 to 4
For Vertex V2: edge from 2 to 1, self-loop at 2, an edge from 2 to 3, an edge from 2 to 4.
For Vertex 3: self-loop only.
This is the required Directed Graph obtained from the given Adjacency Matrix.
Ques. Show that the two graphs shown below are isomorphic. (5 marks)
Ans. First, check if both the graphs have the same vertices or not.
The sequence of degrees in the ascending order is (2,2,2,3,3)
Now, begin labeling the vertices and start from the vertices of degree 3. Mark them a and b we have,
Notice here, there is a vertex which is adjacent to a and b. So label this vertex as c in each graph. Now we have,
As of now, only two vertices are left. Label them as d and e. Here d is labeled in such a way that is adjacent to a and e is adjacent to b.
At last to verify the isomorphism, relabel each graph and check vertex to vertex. We have,
Here we can see that one graph is obtained by another graph by rebelling, therefore these two graphs are isomorphic.
Ques. Find the Adjacency Matrix for the given graph. (5 marks)
Ans. The number of vertices in the graph is 5. Therefore the order of the adjacency matrix would be 5 × 5.
The 5 vertices of the graph are termed V1, V2, V3, V4, and V5.
Considering each vertex and their relation with another vertex one by one.
Remember, if there is any loop or self-loop if there is an edge between two vertices
the value will be 1. Otherwise, in all conditions, it is 0.
Mij = 1 if i j ∊ E(G)
Mij = 0 otherwise
Now we have
V1 = no loop on vertex, an edge from 1 to 2, an edge from 1 to 4
V1 = [0,1,0,1,0]
V2 = no loop on vertex, an edge from 2 to 1, an edge from 2 to 3, edge from 2 to 4
V2 = [0,1,1,1,0]
V3 = no loop on vertex, an edge from 3 to 2, an edge from 3 to 4, an edge from 3 to 5.
V3 = [0,0,1,1,1]
V4 = no loop on vertex, an edge from 4 to 1, an edge from 4 to 2, an edge from 4 to 3.
V4 = [0,1,1,1,0]
V5 = no loop on vertex, an edge from 5 to 3, an edge from 5 to 4.
V5 = [0,0,0,1,1]
The Adjacency Matrix M of order 5 × 5 it can be written as
Ques. Draw the undirected graph of the matrix given below. (5 marks)
\(\begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix}\)
Ans. The order of the given matrix is 4 × 4. Therefore, the total number of vertices will be 4 in the graph.
Let these vertices be V1, V2, V3, and V4. The description of each vertex can be obtained by looking at its given adjacency matrix.
Rewrite the given adjacency matrix as:
Observing each vertex we have,
Vertex 1 = no self-loop, edge from 1 to 2, edge from 1 to 3.
Vertex 2 = no self-loop, edge from 2 to 1, edge from 2 to 4.
Vertex 3 = no self-loop, edge from 3 to 1, edge from 3 to 4.
Vertex 4 = no self-loop, the edge from 4 to 2, an edge from 4 to 3.
From the information given above, the undirected graph will be
Ques. Find the Adjacency Matrix for the undirected graph given below. (5 marks)
Ans. The given undirected graph has a total of 7 vertices. Hence it is clear the order of the Adjacency matrix will be 7 x 7. Let M be the Adjacency Matrix.
Now consider each vertex and its connection with another vertex.
Remember,
Mij = 1 if i j ∊ E(G)
Mij = 0 otherwise
Vertex 0 = no self-loop, an edge from 0 to 2, edge from 0 to 4.
V0 = [0,0,1,1,1,0,0]
Vertex 1 = no self-loop, an edge from 1 to 4, an edge from 1 to 5, and an edge from 1 to 6.
V1 = [0,0,0,0,1,1,1]
Vertex 2 = no self-loop, edge from 2 to 0, an edge from 2 to 4.
V2 = [1,0,0,0,1,0,0]
Vertex 3 = no self-loop, edge from 3 to 0, an edge from 3 to 5, an edge from 3 to 6.
V3 = [1,0,0,0,0,1,1]
Vertex 4 = no self-loop, an edge from 4 to 0, an edge from 4 to 1, an edge from 4 to 2.
V4 = [1,1,1,0,0,0,1]
Vertex 5 = no self-loop, an edge from 5 to 1, an edge from 5 to 3, and an edge from 5 to 6.
V5 = [0,1,0,1,0,0,1]
Vertex 6 = no self-loop, an edge from 6 to 1, an edge from 6 to 3, and edge from 6 to 4, an edge from 6 to 5.
V6 = [0,1,0,1,1,1,0]
Combining the result obtained above and creating a matrix we have,
\(M=\begin{bmatrix} 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \end{bmatrix}\)
M is the Adjacency Matrix of the given undirected graph.
For Latest Updates on Upcoming Board Exams, Click Here: https://t.me/class_10_12_board_updates
Check-Out:
Comments