Course contentsShow
← Computer Science
Lesson 679 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Incidence Matrix Representation

Learn alternative matrix representation where rows are vertices and columns are edges.

Incidence Matrix Representation

What you'll learn: How to represent a graph using a matrix where rows represent vertices and columns represent edges.

The Core Idea

An incidence matrix is an alternative way to store graph structure. Unlike an adjacency matrix (which shows vertex-to-vertex connections), an incidence matrix has one row per vertex and one column per edge. Each cell tells you whether that vertex is involved in that edge.

Think of it like a sign-up sheet: each row is a person, each column is an event, and you mark which people participate in which events.

How It Works

For an undirected graph with V vertices and E edges, the incidence matrix is V×E:

  • Cell [v][e] = 1 if vertex v is incident to edge e (the edge touches v)
  • Cell [v][e] = 0 otherwise
  • Each column has exactly two 1s (one edge connects two vertices)

For a directed graph:

  • Cell [v][e] = -1 if edge e leaves vertex v
  • Cell [v][e] = +1 if edge e enters vertex v
  • Cell [v][e] = 0 otherwise

When to Use It

Incidence matrices are rarely used in typical programming because they take O(V×E) space—more than adjacency lists. However, they're useful in:

  • Mathematical graph theory (matrix algebra operations)
  • Network flow algorithms
  • Circuit analysis
  • When you need to frequently query or modify edges directly

Example

For a 3-vertex undirected graph with edges (0-1), (1-2), (0-2):

     e1  e2  e3
v0 [  1   0   1 ]
v1 [  1   1   0 ]
v2 [  0   1   1 ]

Key Takeaway: An incidence matrix uses rows for vertices and columns for edges, capturing which vertices participate in which edges—useful for specialized mathematical operations but memory-intensive for general use.