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.