Adjacency Matrix Definition Formula Properties and Solved Examples
The concept of Adjacency Matrix plays a key role in mathematics and is widely applicable to topics in graph theory, discrete mathematics, data structures, and many real-life network problems. This method helps students understand relationships between objects and makes graph algorithms easier to apply in programming or competitive exams. Let's explore this essential topic in a structured, easy-to-read way.
What Is Adjacency Matrix?
An adjacency matrix is a square matrix that represents a graph by showing which vertices (nodes) are connected to which others. If two vertices are connected by an edge, the corresponding position in the matrix contains a 1; otherwise, it contains a 0. This concept is widely used in Graph Theory, Data Structures, and in coding algorithms for computer science.
Key Formula for Adjacency Matrix
Here’s the standard definition: For a graph G with n vertices numbered \( v_1, v_2, ..., v_n \), the adjacency matrix \( A \) is an \( n \times n \) matrix, where each entry \( a_{ij} \) is:
\[ a_{ij} = \begin{cases} 1 & \text{if there is an edge from } v_i \text{ to } v_j \\ 0 & \text{otherwise} \end{cases} \]
Cross-Disciplinary Usage
Adjacency matrices are not only useful in Mathematics, but also play important roles in Physics (network analysis), Computer Science (graph algorithms like BFS and DFS), and even logical reasoning in daily life. Especially for students preparing for exams like JEE, NEET or Olympiads, knowing how to use adjacency matrices makes solving network/graph problems quick and systematic.
Types of Adjacency Matrices
Adjacency matrices can represent both directed and undirected graphs. For undirected graphs, the matrix is symmetric because each edge goes both ways. For directed graphs, the matrix may not be symmetric.
Step-by-Step Illustration
- Suppose we have these vertices: A, B, C, D.
- The edges are: A–B, A–C, B–C, C–D (all undirected).
- Assign numbers: a=1, b=2, c=3, d=4.
- We create the adjacency matrix as follows:
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 1 | 0 |
| C | 1 | 1 | 0 | 1 |
| D | 0 | 0 | 1 | 0 |
Each “1” in a cell means the two vertices are connected by an edge.
Properties of the Adjacency Matrix
- If the graph is undirected, the matrix is symmetric: \( a_{ij} = a_{ji} \).
- Diagonal entries show self-loops: 1 if there is a loop at that vertex (otherwise 0).
- The sum of entries in a row or column tells you the degree of the vertex.
- Multiplying the matrix by itself (raising to a power) tells you about paths of longer length.
- For weighted graphs, “1” is replaced by the edge’s weight.
Adjacency Matrix vs Other Graph Representations
| Feature | Adjacency Matrix | Adjacency List | Incidence Matrix |
|---|---|---|---|
| Space Requirement | O(V²) | O(V+E) | O(V×E) |
| Edge Lookup Speed | Constant | Linear | Linear |
| Best For | Dense Graphs | Sparse Graphs | Theoretical Analysis |
| Example Internal Link | Adjacency Matrix | Matrix Representation | Incidence Matrix |
Step-by-Step Example: Adjacency Matrix for a Directed Graph
Suppose we have a directed graph with vertices A, B, C, D. The edges are: A→B, B→C, C→D.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 0 | 0 |
| B | 0 | 0 | 1 | 0 |
| C | 0 | 0 | 0 | 1 |
| D | 0 | 0 | 0 | 0 |
Notice that only the positions where there is a directed edge have “1”.
Try These Yourself
- Draw an undirected graph with 4 nodes and 3 edges, then write its adjacency matrix.
- Given an adjacency matrix with a “1” in cell [3,2], what does this mean for the underlying graph?
- Convert this adjacency matrix to an adjacency list:
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 0 |
Frequent Errors and Misunderstandings
- Confusing adjacency matrix with adjacency list or incidence matrix.
- Forgetting to include both (i,j) and (j,i) for undirected graphs.
- Assuming graphs with many nodes but few edges should use an adjacency matrix (in fact, use adjacency lists for sparse graphs!).
- Mislabeling vertices when constructing the matrix (always use a clear ordering).
Adjacency Matrix in Programming
Python Example:
# n = number of nodes adj_matrix = [[0 for _ in range(n)] for _ in range(n)] # Add an edge from node i to node j adj_matrix[i][j] = 1
C++ Example:
// n = number of nodes vector<vector<int>> adj_matrix(n, vector<int>(n, 0)); // Add an edge from node i to node j adj_matrix[i][j] = 1;
Algorithms like BFS and DFS can easily use adjacency matrices for graph traversal in coding problems.
Relation to Other Concepts
The idea of adjacency matrix connects closely with topics like matrix representation of graph, symmetric matrix, and incidence matrix. Mastering adjacency matrices also helps when learning about more complex graph algorithms and data structures later on.
Classroom Tip
A useful way to remember adjacency matrices is to imagine the vertices lined up on both sides of a table. Put “1” where an edge connects two vertices. Teachers at Vedantu often use color-coded diagrams and step lists to help students quickly visualize connections during live classes.
We explored Adjacency Matrix — from definition, formulas, worked examples, and differences with other representations, to common mistakes. Keep practicing using Vedantu’s resources and you’ll soon be able to use adjacency matrices confidently in all graph-related problems!
Looking to dive deeper? Visit these related concepts:
FAQs on Adjacency Matrix in Graph Theory Explained Clearly
1. What is an adjacency matrix in graph theory?
An adjacency matrix is a square matrix used to represent a finite graph, where each entry indicates whether a pair of vertices is connected by an edge. For a graph with n vertices, the adjacency matrix is an n × n matrix A where:
- Aij = 1 if there is an edge from vertex i to vertex j
- Aij = 0 if there is no edge
It is commonly used in graph theory, discrete mathematics, and computer science to represent networks and relationships.
2. How do you construct an adjacency matrix from a graph?
To construct an adjacency matrix, list all vertices and fill a square matrix based on edge connections between them. Follow these steps:
- List the vertices in a fixed order (e.g., v₁, v₂, v₃).
- Create an n × n matrix where n is the number of vertices.
- Enter 1 if an edge exists between vertex i and j, otherwise enter 0.
Example: If v₁ is connected to v₂ but not v₃, then A₁₂ = 1 and A₁₃ = 0.
3. What is the adjacency matrix of an undirected graph?
The adjacency matrix of an undirected graph is a symmetric matrix where Aij = Aji. This symmetry occurs because if vertex i is connected to vertex j, then j is also connected to i.
- The matrix is always symmetric about the main diagonal.
- Diagonal entries are 0 unless there are self-loops.
This property helps quickly identify whether a graph is undirected.
4. What is the adjacency matrix of a directed graph?
The adjacency matrix of a directed graph (digraph) records the direction of edges, so Aij = 1 means there is an edge from vertex i to vertex j. Unlike undirected graphs:
- The matrix is not necessarily symmetric.
- Aij may not equal Aji.
This matrix representation preserves edge direction and is widely used in network flow and graph algorithms.
5. How do you find the degree of a vertex using an adjacency matrix?
The degree of a vertex in an undirected graph is the sum of the entries in its corresponding row (or column) of the adjacency matrix. Mathematically:
- Degree of vertex i = ∑ Aij
For directed graphs:
- Out-degree = sum of row i
- In-degree = sum of column i
This makes adjacency matrices useful for quickly calculating vertex degrees.
6. What is the difference between an adjacency matrix and an adjacency list?
The main difference is that an adjacency matrix uses a 2D array to store edges, while an adjacency list stores neighbors in lists for each vertex. Key differences:
- Adjacency matrix uses O(n²) space.
- Adjacency list uses O(n + e) space, where e is the number of edges.
- Matrices are faster for checking if an edge exists.
- Lists are more efficient for sparse graphs.
The choice depends on graph density and algorithm requirements.
7. What is a weighted adjacency matrix?
A weighted adjacency matrix stores edge weights instead of just 0 or 1 to represent weighted graphs. In this case:
- Aij = weight of the edge between i and j
- Aij = 0 or ∞ if no edge exists
Example: If the edge from v₁ to v₂ has weight 5, then A₁₂ = 5. This is commonly used in shortest path algorithms like Dijkstra’s algorithm.
8. How many edges can be represented in an adjacency matrix?
An adjacency matrix for a graph with n vertices can represent up to n(n − 1)/2 edges for an undirected graph without self-loops. For directed graphs:
- Maximum edges = n(n − 1) (without self-loops)
- Maximum edges = n² (with self-loops)
This shows that adjacency matrices are best suited for dense graphs.
9. How do you check if a graph is complete using an adjacency matrix?
A graph is complete if every pair of distinct vertices is connected by an edge. In an adjacency matrix of a simple undirected graph:
- All off-diagonal entries must be 1.
- All diagonal entries must be 0 (if no self-loops).
If these conditions are satisfied, the graph is a complete graph Kn.
10. Can you give an example of an adjacency matrix?
Yes, an adjacency matrix example for a graph with vertices v₁, v₂, v₃ where v₁–v₂ and v₂–v₃ are connected is:
- Adjacency matrix A =
0 1 0
1 0 1
0 1 0
This matrix is symmetric, so it represents an undirected graph, and each 1 indicates an edge between the corresponding vertices.
