IncidenceMatrix
gives the vertex-edge incidence matrix of the graph g.
IncidenceMatrix[{vw,…}]
uses rules vw 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 {v1,…,vn} and edges {e1,…,em} is an
matrix with entries aij given by: -
0 vi is not incident to ej 1 ej=vivk, ej=vkvi, or ej=vkvi -1 ej=vivk 2 ej=vivi -2 ej=vivi - The vertices vi are assumed to be in the order given by VertexList[g] and the edges ej are assumed to be in the order given by EdgeList[g].
Examples
open all close allBasic Examples (2)
Scope (5)
The incidence matrix of an undirected graph has no negative entries:
g = Graph[{12, 23, 31}](m = IncidenceMatrix[g])//MatrixFormThe sum of the entries in any column is 2:
Total[m]The incidence matrix of a directed graph has some negative entries:
g = Graph[{12, 23, 31}](m = IncidenceMatrix[g])//MatrixFormIf there are no self-loops, the sum of the entries in any column is 0:
Total[m]The incidence matrix of a graph with self-loops has some entries equal to 2:
{Graph[{12, 23, 31, 33}], Graph[{12, 23, 31, 11}]}MatrixForm /@ IncidenceMatrix /@ %Use rules to specify the graph:
IncidenceMatrix[{1 -> 2, 2 -> 3, 3 -> 1}]//MatrixFormIncidenceMatrix works with large graphs:
Graph[Table[i -> Mod[i ^ 2, 10 ^ 3], {i, 0, 10 ^ 3 - 1}]];Timing[m = IncidenceMatrix[%]]Use MatrixPlot to visualize the matrix:
MatrixPlot[m]Properties & Relations (9)
Rows and columns correspond to VertexList and EdgeList order:
b = IncidenceMatrix[g = [image]];TableForm[Normal[b], TableHeadings -> {VertexList[g], EdgeList[g]}]The 
row gives all edge indices incident to the 
vertex:
b = IncidenceMatrix[g = [image]];The first vertex is incident to edges 2, 3, and 4:
b[[1]]//Normal{VertexList[g][[1]], EdgeList[g][[{2, 3, 4}]]}The 
column gives all vertex indices incident to the 
edge:
b = IncidenceMatrix[g = [image]];The second edge is incident to vertices 1 and 3:
b[[ ;; , 2]]//Normal{EdgeList[g][[2]], VertexList[g][[{1, 3}]]}Use VertexIndex and EdgeIndex to find the indices for vertices and edges:
g = [image];{VertexIndex[g, β], EdgeIndex[g, αβ]}The incidence matrix can tell whether a vertex and edge are incident:
b = IncidenceMatrix[g];b[[VertexIndex[g, β], EdgeIndex[g, αβ]]]The incidence matrix for a directed graph indicates the source vertex by 
and the target vertex by 
:
b = IncidenceMatrix[g = [image]];TableForm[Normal[b], TableHeadings -> {VertexList[g], EdgeList[g]}]Compute the oriented incidence matrix for an undirected graph using DirectedGraph:
b = IncidenceMatrix[DirectedGraph[g = [image], "Random"]];The oriented incidence matrix using a random orientation:
TableForm[Normal[b], TableHeadings -> {VertexList[g], EdgeList[g]}]The dimensions of the incidence matrix are given by VertexCount and EdgeCount:
g = PetersenGraph[]Dimensions[IncidenceMatrix[g]] == {VertexCount[g], EdgeCount[g]}Use IncidenceGraph to construct a graph from an incidence matrix:
IncidenceGraph[{{1, 0, 1}, {1, 1, 0}, {0, 1, 1}}]IncidenceMatrix[%]//NormalThe adjacency matrix of a line graph can be computed by its IncidenceMatrix:
g = GridGraph[{2, 3}]m = IncidenceMatrix[g];(Transpose[m].m - 2 IdentityMatrix[EdgeCount[g]])//MatrixPlotAdjacencyMatrix[LineGraph[g]]//MatrixPlotText
Wolfram Research (2010), IncidenceMatrix, Wolfram Language function, https://reference.wolfram.com/language/ref/IncidenceMatrix.html (updated 2015).
CMS
Wolfram Language. 2010. "IncidenceMatrix." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/IncidenceMatrix.html.
APA
Wolfram Language. (2010). IncidenceMatrix. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/IncidenceMatrix.html