NEETClass 11thClass 12thClass 12th PlusJEEClass 11thClass 12thClass 12th PlusClass 6-10Class 6thClass 7thClass 8thClass 9thClass 10thOnline CoursesDistance LearningInternational OlympiadNEETClass 11thClass 12thClass 12th PlusJEE (Main+Advanced)Class 11thClass 12thClass 12th PlusJEE MainClass 11thClass 12thClass 12th PlusClass 6-10Class 6thClass 7thClass 8thClass 9thClass 10thNEET2025202420232022JEE20262025202420232022Class 6-10JEE MainPrevious Year PapersSample PapersMock TestResultAnalysisSyllabusExam DatePercentile PredictorAnswer KeyCounsellingEligibilityExam PatternJEE MathsJEE ChemistryJEE PhysicsJEE AdvancedPrevious Year PapersSample PapersMock TestResultAnalysisSyllabusExam DateAnswer KeyEligibilityExam PatternRank PredictorNEETPrevious Year PapersSample PapersMock TestResultAnalysisSyllabusExam DateCollege PredictorAnswer KeyRank PredictorCounsellingEligibilityExam PatternBiologyNCERT SolutionsClass 6Class 7Class 8Class 9Class 10Class 11Class 12TextbooksCBSEClass 12Class 11Class 10Class 9Class 8Class 7Class 6SubjectsSyllabusNotesSample PapersQuestion PapersICSEClass 10Class 9Class 8Class 7Class 6State BoardBiharKarnatakaMadhya PradeshMaharashtraTamilnaduWest BengalUttar PradeshOlympiadMathsScienceEnglishSocial ScienceNSOIMONMTCASATInstant Online ScholarshipAIOT(NEET)TALLENTEXALLEN for SchoolsAbout ALLENBlogsNewsCareersRequest a call backBook a demo
Adjacency Matrix
Let aij denote the number of edges (Vi, Vj) then A = [aij]m×m is called adjacency matrix of G if
1.0Definition of Adjacency Matrix
In graph theory, an adjacency matrix is a square matrix that represents a finite graph. The elements of this matrix indicate whether pairs of vertices in the graph are connected by an edge. For a graph with n vertices, the adjacency matrix is an n × n matrix where the element Aij is:
- 1 if an edge exists between vertex i and vertex j;
- 0 if no edge exists between vertex i and vertex j.
This matrix representation provides a powerful tool for analyzing and manipulating graph structures, making it essential for studying various types of graphs, including undirected and directed graphs.
2.0Adjacency Matrix for Undirected Graphs
In an undirected graph, the edges are not directional, meaning the edge between two vertices is bidirectional. Consequently, the adjacency matrix for an undirected graph is symmetric. If there is an edge between vertices i and j, then both Aij and Aji will be 1.
Example:
Consider an undirected graph with 4 vertices V = {A, B, C, D} and the following edges:
The adjacency matrix for this graph is:
Here, the matrix is symmetric about the diagonal, indicating the undirected nature of the graph.
3.0Adjacency Matrix for Directed Graphs
In a directed graph, the edges have a specific direction, meaning they go from one vertex to another and not necessarily in both directions. The adjacency matrix of a directed graph does not need to be symmetric.
Example:
Consider a directed graph with 4 vertices V = {A, B, C, D} and the following directed edges:
The adjacency matrix for this graph is:
This matrix is not symmetric, which reflects the directed nature of the graph.
4.0Properties of Adjacency Matrices
- Symmetry: The adjacency matrix of an undirected graph is always symmetric.
- Diagonal Elements: In a simple graph, the diagonal elements of the adjacency matrix are 0, as there are no self-loops (no vertex is connected to itself)
- Sparsity: For large graphs, adjacency matrices are typically sparse, meaning most elements are 0, as the number of edges is usually much smaller than the number of possible connections.
- Degree of Vertices: For an undirected graph, the degree of a vertex can be calculated by summing the values in its corresponding row (or column, due to symmetry). For directed graphs, the out-degree is the sum of the row, and the in-degree is the sum of the column.
5.0Solved Examples on Adjacency Matrix
Example 1: Consider the undirected graph G as shown below. Find the Adjacency matrix.
Solutions:
Example 2: Find the Adjacency matrix of graph G.
Solutions:
Example 3: Consider the undirected graph G as shown below. Find the Adjacency matrix.
Solutions:
Example 4: Find the Adjacency matrix of the graph.
Solutions:
Example 5: Plot a graph given by the following adjacency matrix
Solutions:
Example 6: Write down the Adjacency matrix of graph G.
Solutions:
6.0Practice Questions on Adjacency Matrix
- Construct the adjacency matrix for a directed graph with vertices V = {A, B, C, D}.
- Given the adjacency matrix below, determine whether the graph is directed or undirected:
- For a graph with vertices V = {P, Q, R, S} and the adjacency matrix:List all the edges of the graph and state whether it is directed or undirected.
- Construct the adjacency matrix for a directed graph with vertices V = {A, B, C, D, E}.