`incidence`

Incidence matrix: which edges touch which nodes.

Category: Mathematics > Graph and Network Algorithms

Syntax

I = incidence(G)

Returns the node-by-edge incidence matrix.

Description

Each column describes one edge, so every column has exactly one -1 and one 1 (a self-loop gives a column of zeros). Multiplying I by its own transpose gives the graph Laplacian: I*I' equals laplacian(G) for an undirected graph without loops.

The incidence matrix is the basis of flow and network-circuit formulations, where it expresses conservation: I*f is the net flow into each node for an edge flow vector f.

Input arguments

G: A graph or digraph.

Output arguments

I: Matrix with numnodes(G) rows and numedges(G) columns. Column k has -1 at the source node of edge k, 1 at its target node, and zeros elsewhere.

Example

Incidence and Laplacian

G = graph([1 1 2 3], [2 3 3 4]);
I = incidence(G)
isequal(I*I', laplacian(G))

Output

I = 4×4

    -1    -1     0     0
     1     0    -1     0
     0     1     1    -1
     0     0     0     1
ans = logical
   1

Notes

MatLivre returns full (dense) matrices here, where MATLAB returns sparse ones. Values and sizes are the same.

incidence