Enable JavaScript to interact with content and submit forms on Wolfram websites. Learn how

IncidenceMatrix

IncidenceMatrix[g]

gives the vertex-edge incidence matrix of the graph g.

IncidenceMatrix[{vw,…}]

uses rules vw to specify the graph g.

Details

IncidenceMatrix is also known as the vertex-edge incidence matrix.

IncidenceMatrix returns a SparseArray object, which can be converted to an ordinary matrix using Normal.
The incidence matrix for a graph with vertices {v₁,…,v_n} and edges {e₁,…,e_m} is an matrix with entries a_ij given by:
0 v_i is not incident to e_j

1 e_j=v_iv_k, e_j=v_kv_i, or e_j=v_kv_i

-1 e_j=v_iv_k

2 e_j=v_iv_i

-2 e_j=v_iv_i
The vertices v_i are assumed to be in the order given by VertexList[g] and the edges e_j are assumed to be in the order given by EdgeList[g].

Examples

open allclose all

Basic Examples (2)

The incidence matrix of an undirected graph:

The incidence matrix of a directed graph:

Scope (5)

The incidence matrix of an undirected graph has no negative entries:

The sum of the entries in any column is 2:

The incidence matrix of a directed graph has some negative entries:

If there are no self-loops, the sum of the entries in any column is 0:

The incidence matrix of a graph with self-loops has some entries equal to 2:

Use rules to specify the graph:

IncidenceMatrix works with large graphs:

Use MatrixPlot to visualize the matrix:

Properties & Relations (9)

Rows and columns correspond to VertexList and EdgeList order:

The row gives all edge indices incident to the vertex:

The first vertex is incident to edges 2, 3, and 4:

The column gives all vertex indices incident to the edge:

The second edge is incident to vertices 1 and 3:

Use VertexIndex and EdgeIndex to find the indices for vertices and edges:

The incidence matrix can tell whether a vertex and edge are incident:

The incidence matrix for a directed graph indicates the source vertex by and the target vertex by :

Compute the oriented incidence matrix for an undirected graph using DirectedGraph:

The oriented incidence matrix using a random orientation:

The dimensions of the incidence matrix are given by VertexCount and EdgeCount:

Use IncidenceGraph to construct a graph from an incidence matrix:

The adjacency matrix of a line graph can be computed by its IncidenceMatrix:

Top