Incidence matrix

Incidence

A node is incident with an edge if the node is one of the endpoints of that edge.

The incidence matrix of an undirected graph is a $n\times m$ matrix $B$, where $n$ and $m$ denote the number of nodes and edges respectively, such that¹

$$B_{ij}=\{\begin{array}{ll}1& \text{if vertex }{v}_i\text{ is connected with edge }{e}_j\\ 0& \text{otherwise}\end{array}$$

Representing weights

The definition can be extended to represent weighted edges within weighted graphs:

$$B_{ij}=\{\begin{array}{ll}\text{weight of }{e}_j& \text{if vertex }{v}_i\text{ is connected with edge }{e}_j\\ 0& \text{otherwise}\end{array}$$

Example

Given an undirected graph: The incidence matrix is:

Footnotes

1. https://en.wikipedia.org/wiki/Incidence_matrix ↩