KirchhoffMatrix

KirchhoffMatrix[g]
gives the Kirchhoff matrix of the graph g.

DetailsDetails

  • KirchhoffMatrix returns a SparseArray object, which can be converted to an ordinary matrix using Normal.
  • The diagonal entries equal the degree of .
  • An entry is if vertex is adjacent to .
  • The vertices 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
Background

  • 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 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 -1 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 calculating 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 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.

ExamplesExamplesopen allclose all

Basic Examples  (2)Basic Examples  (2)

The Kirchhoff matrix of an undirected graph:

In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]//MatrixForm=

The Kirchhoff matrix of a directed graph:

In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]//MatrixForm=
Introduced in 2010
(8.0)