Graph Theory → Computational Representation

Incidence Matrix

Let \(G=(V,A)\) be a graph with \(V=\{v_1,v_2,\dots,v_n\}\) and \(A=\{a_1,a_2,\dots,a_m\}\). The incidence matrix of \(G\) is the matrix \[ B=(b_{ij}) \in \mathbb{R}^{n \times m}, \] where rows represent edges (or arcs) and columns represent vertices.

Undirected graph

b_{ij} = \begin{cases} 1, & \text{if vertex } v_i \text{ is incident to edge } a_j, \\ 0, & \text{otherwise.} \end{cases}

Each column of the matrix has exactly two values equal to 1, corresponding to the two vertices connected by the edge.

Directed graph (most common in computing)

b_{ij} = \begin{cases} -1, & \text{if } a_j \text{ leaves } v_i, \\ \phantom{-}1, & \text{if } a_j \text{ enters } v_i, \\ 0, & \text{otherwise.} \end{cases}

\(-1\) indicates the source vertex of the arc
\(+1\) indicates the destination vertex of the arc
\(0\) indicates that the vertex does not participate in that arc

Incidence Matrix Example with Directed Graph G

Vertex order: (A, B, C, D, E)

\begin{array}{c|ccccc} & A & B & C & D & E \\\hline q & -1 & 1 & 0 & 0 & 0 \\ w & -1 & 0 & 1 & 0 & 0 \\ r & -1 & 0 & 0 & 1 & 0 \\ t & 0 & -1 & 1 & 0 & 0 \\ y & 0 & 0 & -1 & 1 & 0 \\ u & 0 & -1 & 0 & 0 & 1 \\ i & 0 & 0 & 0 & -1 & 1 \end{array}

Each column represents a vertex and each row represents an edge (arc).

Discrete Mathsfor Engineers

Incidence Matrix

Undirected graph

Directed graph (most common in computing)

Incidence Matrix Example with Directed Graph G