Course contentsShow
← Mathematics
Lesson 2655 of 3,12153. Graph TheoryFree lesson

Graph Representations: Adjacency Matrix

Represent graphs using adjacency matrices, showing how matrix entries encode edge presence and multiplicity.

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.