This post is also available in: हिन्दी (Hindi)
A graph with n nodes can be represented in the form of a square matrix of order n. Graphs find applications in many areas such as airline scheduling, directions on a map, solving sudoku puzzles, search engine algorithms, social media marketing.
In this article, you will learn two very important concepts of matrices – Adjacency Matrix and Path Matrix.
Adjacency Matrix and Path Matrix of a Graph
A network usually consists of hundreds or thousands of nodes connected to one another by edges. These networks can be represented as graphs, a type of data structure. Have you ever wondered how a path between two nodes is established to facilitate uninterrupted communication?
To understand this, one should know two basic concepts of graphs.
- Adjacency Matrix
- Path Matrix
1. Adjacency Matrix in Graph Theory
In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
Elements of an adjacency matrix are either 0 or 1. If a pair of nodes have a common edge(i.e., nodes are connected), it is represented by 1. If a pair of nodes do not have a common edge(i.e., nodes are not connected), it is represented by 0.
Let’s now understand how undirected and directed graphs are represented by an adjacency matrix.
Adjacency Matrix – Undirected Graph
In this graph node A is adjacent to nodes B and C. Similarly, node B is adjacent to nodes A and C; node C is adjacent to nodes A, B, and D; node D is adjacent to node C.
The adjacency matrix of the above graph is
In the above matrix, since there is a path from A to C as well as from C to A, therefore, entry for A to C and C to A is 1. The same is true for other nodes.
In the case when a node is connected to itself by a loop. (Node C has a loop).
Adjacency Matrix – Directed Graph
Consider a directed graph as shown above. There is a path from node A to node B, but there doesn’t exist any direct path from node B to node A. Similarly there is a path from node C to node A but no such path between node A to node C.
Now consider a pair of nodes B and C. There is a direct path from node B to node C as well as from node C to node B. The adjacency matrix of the above graph is represented as
Path Matrix in Graph Theory
A path matrix in a data structure is a matrix representing a graph, where each value in $m^th$ row and $n^th$ column project whether there is a path from node $m$ to node $n$. The path may be direct or indirect. It may have a single edge or multiple edges.
To understand what is path matrix in data structure, let’s consider the following graph
The adjacency matrix of the above graph is
If we consider the pair of nodes B and E. From the above adjacency matrix, we find that there is no direct path between B and E. But there exists a path from B and E through C. Such a path is known as a path of length 2. Similarly, a path of length 3 will have 2 intermediate nodes. In general, a path of length n will have (n – 1) intermediate nodes.
To obtain a path matrix of length 2, the adjacency matrix is multiplied by itself.
From the above matrix, we find that there exists a path of length 2 between A to B, E to B, A to C, D to C, C to D, and B to E.
Again multiplying the path matrix of length 2 with the adjacency matrix gives a path matrix of length 3.
From the above matrix, we find that there exists a path of length 3 between C to B, A to C, E to C, B to D, A to E, and D to E.
In general, to generate the matrix of the path of length n, take the matrix of the path of length (n – 1), and multiply it with the matrix of a path of length 1.
Practice Problems
1. The number of elements in the adjacency matrix of a graph having 7 vertices is __
a) 7
b) 14
c) 36
d) 49
2. Adjacency matrix of all graphs is symmetric.
a) False
b) True
FAQs
What is the sum of the elements of column i of the adjacency matrix of a graph?
The sum of the elements of column i of the adjacency matrix of a graph is the degree of vertex i.
What is a matrix function?
A function that maps a matrix to another matrix.
What are the areas in which matrices can be applied?
Matrices have varied applications in many fields, including electrical engineering, computer science, seismic surveys, scientific studies, etc.
Conclusion
The adjacency matrix is a connection matrix containing rows and columns used to represent a simple labeled graph. Path matrix in data structure, the element on the $i^{th}$ row and $j^{th}$ column is 1 if there’s a path from $i^{th}$ vertex to $j^{th}$ in the graph, and 0 if there is not. The adjacency and path matrices are used in optic science to account for refraction and reflection and are also useful in electrical circuits and quantum physics.
