Kirchhoff's theorem

From Wikipedia, the free encyclopedia

You have new messages (last change).

In the mathematical field of graph theory Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph. It is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.

[edit] Kirchhoff's theorem

Given a connected graph G with n vertices, let λ1,λ2,...,λn − 1 be the non-zero eigenvalues of the admittance matrix of G. Then the number of spanning trees of G is

G=\frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}\,.

In other words the number of spanning trees is equal to any cofactor of the admittance matrix of G.

[edit] An Example Using the Matrix-Tree Theorem

We can compute the number of labeled spanning trees of this kite with the Matrix-Tree Theorem.
We can compute the number of labeled spanning trees of this kite with the Matrix-Tree Theorem.

We first construct a matrix Q for the graph G such that:

  • for i \neq j
    • if vertex i is adjacent to vertex j in G, qi,j equals -1
    • otherwise, qi,j equals 0
  • for i = j, qi,j (that is, qi,i) equals the degree of vertex i in G

Using the kite in this example (see image at right),

Q = \begin{bmatrix} 3 & -1 & -1 & -1 \\ -1 & 2 & -1 & 0 \\ -1 & -1 & 3 & -1 \\ -1 & 0 & -1 & 2 \end{bmatrix}

We now construct a matrix Q* by deleting any row s and any column t (s and t not necessarily distinct) from Q. For this example, we will delete row 1 and column 1 to obtain

Q^\ast = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 3 & -1 \\ 0 & -1 & 2 \end{bmatrix}

Finally, we take the determinant of Q* to obtain t(G), which is 8 in this example.

[edit] Notes

Seeing that Cayley's formula follows from Kirchhoff's theorem as a special case is easy: every vector with 1 in one place, -1 in another place, and 0 elsewhere is an eigenvector of the admittance matrix of the complete graph, with the corresponding eigenvalue being n. These vectors together span a space of dimension n-1, so there are no other non-zero eigenvalues.

Retrieved from "http://en.wikipedia.org../../../k/i/r/Kirchhoff%27s_theorem.html"
In other languages