KirchhoffMatrix

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

KirchhoffMatrix[{vw,}]
uses rules vw to specify the graph g.

DetailsDetails

  • 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
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 d_i) and the adjacency matrix A. The diagonal elements l_(i⁣i) of L are therefore equal to the degree d_i of vertex v_i and off-diagonal elements l_(i⁣j) are equal to -1 if vertex v_i is adjacent to v_j 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 l_(i⁣i)=1 if i=j and d_j!=0, l_(i⁣j)=-(d_id_j)^(-1/2) if v_i and v_j 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)
| Updated in 2015
(10.3)
Translate this page: