Incidence matrix
|
|
In mathematics, the incidence matrix of an undirected graph G is a p × q matrix <math>[b_{ij}]<math> where p and q are the number of vertices and edges respectively, such that <math>b_{ij} = 1<math> if the vertex <math>v_i<math> and edge <math>x_j<math> are incident and 0 otherwise.
The incidence matrix of a directed graph G is a p × q matrix <math>[b_{ij}]<math> where p and q are the number of vertices and edges respectively, such that <math>b_{ij} = -1<math> if the edge <math>x_j<math> leaves vertex <math>v_i<math>, <math>1<math> if it enters vertex <math>v_i<math> and 0 otherwise.
The incidence matrix is related to the adjacency matrix of its line graph <math>L(G)<math> by the following theorem:
- <math>
A(L(G)) = B(G)^{T}B(G) - 2I_q <math>
where <math>A(L(G))<math> is the adjacency matrix of the line graph of <math>G<math>, <math>B(G)<math> is incidence matrix, and <math>I_q<math> is the identity matrix of dimension q.
The cycle space of a graph is equal to the null space of its incidence matrix.
The incidence matrix of an incidence structure C is a p × q matrix <math>[b_{ij}]<math> where p and q are the number of points and lines respectively, such that <math>b_{ij} = 1<math> if the point <math>p_i<math> and line <math>L_j<math> are incident and 0 otherwise. In this case the incidence matrix is also a biadjacency matrix of the Levi graph of the structure.