Incidence matrix

  • The incidence matrix A of an undirected graph has a row for each vertex and a column for each edge of the graph.

  • The element A[[i,j]] of A is 1 if the ith vertex is a vertex of the jth edge and 0 otherwise.

  • The incidence matrix A of a directed graph has a row for each vertex and a column for each edge of the graph. The element A[[i,j] of A is − 1 if the ith vertex is an initial vertex of the jth edge, 1 if the ith vertex is a terminal vertex, and 0 otherwise.

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

  • The sum of the elements in any column of incidence matrix of an undirected graph is always 2.

  • If a directed graph has no self-loops, the sum of the elements of its incidence matrix is always 0.

  • The incidence matrix of a graph with self-loops has entries equal to 2.

Permalink at https://www.physicslog.com/cs-notes/incidence-matrix

Published on Sep 29, 2021

Last revised on Sep 29, 2021