Watch Free Classes

Definition: A dense approach of representing the finite graph structure is an adjacency matrix. The 2D matrix is used to represent the relationship between network nodes.If a graph contains n vertices, the adjacency matrix for that graph is n x n, with each entry representing the number of edges connecting one vertex to the next.Adjacency matrices are sometimes known as connection matrices. It’s also known a Vertex matrix.

Adjacency Matrix Representation: 

If an Undirected Graph G has n vertices, the graph’s adjacency matrix is n x n matrix A = [aij] and is defined by –

If there is a path from Vi to Vj, aij = 1.

Otherwise, aij = 0

Let’s take a look at some of the most crucial aspects of the adjacency matrix.

  • If an edge exists between vertex Vi and Vj, where i denotes a row and j denotes a column, then aij = 1.
  • The value of aij = 0 , if there is no edge between the vertex Vi and Vj.
  • The vertex matrix (or adjacency matrix) should contain 0s in the diagonal if there are no self loops in the simple graph.
  • An undirected graph’s adjacency matrix is symmetric. It says that the value in the ith row and jth column is the same as the value in the jth row ith column.
  • When the adjacency matrix is multiplied by itself and a non-zero value is present at the ith row and jth column,then there is the route from Vi­ to Vj­­ with a length equivalent to 2. The occurrence of distinct paths is indicated by a non-zero value in the adjacency matrix.

Note : In an adjacency matrix, 0 indicates that there is no connection between two nodes, but 1 indicates that there is a connection between two nodes.

How to create an Adjacency Matrix?

If there are n vertices in a graph g, then the vertex matrix (or adjacency matrix) is given by –

A =  a11 a12 . . . . . a1n

       a21 a22 . . . . . a2n

       .     .          .

       .     .          .

       an1 an2 . . . . . ann

The number of edges from vertex i to j is equal to aij. As previously stated, the Adjacency matrix is symmetric for an undirected graph, hence aij = aji­ for an undirected graph.

The elements of the adjacency matrix will be 0 and 1 when the graphs are simple and there are no weights on the edges or many edges. The diagonal entries of the adjacency matrix will be 0 if there are no self-loops.

Adjacency Matrix for an Undirected Graph: Edges in an undirected graph are not associated with the directions with which they are associated. If an edge exists between Vertex A and Vertex B in an undirected graph, the vertices can be transferred from A to B as well as B to A.

Adjacency Matrix for an Directed Graph: In an adjacency directed matrix,  there is no self-loop, so the diagonal entries of the adjacent matrix will be 0.

Properties of Adjacency Matrix

The following are some of the adjacency matrix’s properties:

  • An adjacency matrix is a matrix with rows and columns that is used to depict a basic labelled graph with the values 0 and 1 in the positions of Vi, Vj , depending on whether the two Vi and Vj are adjacent.
  • If an edge exists between vertex i or Vi and vertex j or Vj in a directed graph, the value of A[Vi][Vj] = 1, otherwise the value will be 0.
  • If an edge exists between vertex i or Vi and vertex j or Vj in an undirected graph, the value of A[Vi][Vj] = 1 and A[Vj][Vi] = 1, otherwise the value will be 0.

Adjacency Matrix Bubble Diagram: The adjacency matrix is used to create a bubble. Furthermore, a bubble diagram visually shows information as a sequence of bubbles. The bubbles can be used to symbolise several types of places in a plan, with different shapes representing different levels of importance and size. The bubble diagram can help you build a general sense of flow, which you can then utilise to refine your plan.

Conclusion

A dense approach of representing the finite graph structure is an adjacency matrix. The 2D matrix is used to represent the relationship between network nodes.If a graph contains n vertices, the adjacency matrix for that graph is n x n, with each entry representing the number of edges connecting one vertex to the next.Adjacency matrices are sometimes known as connection matrices. It’s also known a Vertex matrix. It is of two types :-

  • Adjacency Matrix for an Undirected Graph
  • Adjacency Matrix for an Directed Graph

The adjacency matrix is used to create a bubble. Furthermore, a bubble diagram visually shows information as a sequence of bubbles. The bubbles can be used to symbolise several types of places in a plan, with different shapes representing different levels of importance and size. The bubble diagram can help you build a general sense of flow, which you can then utilise to refine your plan.