Skip to content

Incidence Matrices

Chapter 5

Interactive Notebook

Summary

This chapter introduces incidence matrices as an alternative graph representation:

  • Incidence vs Adjacency - Adjacency matrices have nodes as both rows and columns; incidence matrices have nodes as rows and edges as columns
  • Incidence Matrix Structure - Each column represents an edge, with non-zero entries indicating which nodes participate in that edge
  • Matrix Multiplication with Incidence - Multiplying incidence matrices to derive relationships and construct new graph structures
  • Multi-graphs - Graphs with multiple edges between the same pair of nodes, naturally represented through incidence matrices
  • Hypergraphs - Generalized graphs where edges can connect more than two nodes, enabling complex relationship modeling
  • Applications - Network flow, bipartite matching, and modeling relationships that go beyond simple pairwise connections