Graph Representations: Adjacency Matrix
You'll learn how to represent any graph as a rectangular grid of numbers that precisely captures which vertices are connected.
What Is an Adjacency Matrix?
An adjacency matrix is a square array (like a table) where both rows and columns correspond to vertices in your graph. Each cell in the matrix tells you about the edge(s) between two vertices.
For a graph with n vertices labeled v₁, v₂, ..., vₙ, we build an n × n matrix A where:
- The entry A[i,j] (row i, column j) records information about edges from vertex vᵢ to vertex vⱼ
How Entries Encode Edges
For simple graphs (no multi-edges, no loops):
- A[i,j] = 1 if there's an edge between vᵢ and vⱼ
- A[i,j] = 0 if there's no edge
For multigraphs (multiple edges allowed):
- A[i,j] = the number of edges connecting vᵢ and vⱼ
For directed graphs (digraphs):
- A[i,j] counts edges from vᵢ to vⱼ
- Note: A[i,j] may differ from A[j,i] since direction matters!
An Analogy
Think of an adjacency matrix like a distance chart between cities. Each row is a departure city, each column is a destination. Instead of miles, you're recording "how many roads connect these two places."
Example
For a simple undirected graph with vertices {1, 2, 3} and edges {(1,2), (2,3)}:
1 2 3
1 [ 0 1 0 ]
2 [ 1 0 1 ]
3 [ 0 1 0 ]
The diagonal is all zeros (no loops), and the matrix is symmetric (undirected).
Key Takeaway: An adjacency matrix uses matrix entries to encode edge presence (0 or 1) and multiplicity (counts ≥2 for multigraphs), providing a complete numerical representation of any graph structure.