gives the Kirchhoff matrix of the graph g.
uses rules vw to specify the graph g.
- KirchhoffMatrix returns a SparseArray object, which can be converted to an ordinary matrix using Normal.
- The diagonal entries ki,i equal the degree of vi.
- An entry ki,j is -1 if vertex vi is adjacent to vj.
- The vertices vi are assumed to be in the order given by VertexList[g].
- The Kirchhoff matrix for a graph will have dimensions × where is the number of vertices.
Background & Context
- KirchhoffMatrix returns the Kirchhoff matrix, also known as the Laplacian matrix, admittance matrix, or discrete Laplacian. This is a square matrix with integer elements. For efficiency, KirchhoffMatrix returns the matrix as a sparse array. The (usual) Kirchhoff matrix L is defined as the difference L=D-A of the degree matrix D (the diagonal matrix of graph vertex degrees ) and the adjacency matrix A. The diagonal elements of L are therefore equal to the degree of vertex and off-diagonal elements are equal to if vertex is adjacent to and 0 otherwise.
- For a graph on n vertices, the Kirchhoff matrix has dimensions n×n. For an undirected graph, the Kirchhoff matrix is symmetric.
- The Kirchhoff matrix plays a central role in spectral graph theory, which is the study of graphs based on the eigenvalues of their adjacency or Kirchhoff matrices. It can be used to calculate resistance distances between vertices of a graph, which are defined as the effective resistances between vertices (as when a battery is attached across them) when each graph edge is replaced by a unit resistor. It also appears in the matrix tree theorem, which gives the number of spanning trees of a graph. The second smallest eigenvalue of the Kirchhoff matrix is known as the algebraic connectivity of a graph, and a graph is connected if and only if this eigenvalue is greater than 0. The eigenvector corresponding to the algebraic connectivity of a graph is known as the Fiddler vector and is important in spectral graph partitioning, which is the division of a given graph into smaller components with specific properties based on the eigenvalues of the adjacency or Kirchhoff matrix.
- Note that physicists commonly use the term “Laplacian matrix” instead of “Kirchhoff matrix”. Some physicists and mathematicians also use a version of the matrix with a different normalization, namely that defined by if i=j and , if and are adjacent, and 0 otherwise. Furthermore, while the term “graph spectrum” generally refers to eigenvalues of a graph adjacency matrix to mathematicians, to physicists it often refers to eigenvalues of the normalized Kirchhoff matrix. Care is therefore needed when encountering these terms in the wild.
- KirchhoffGraph can be used to construct a graph from a Kirchhoff matrix. The similar functions AdjacencyGraph and IncidenceGraph construct graphs from a given adjacency and incidence matrix, respectively.
Examplesopen allclose all
Introduced in 2010
(8.0)| Updated in 2015