|
|
|
|
|
Kirchhoff's TheoremIn 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. Kirchhoff's Theorem Given a connected graph G with n vertices, let be the non-zero eigenvalues of the admittance matrix of G. Then the number of spanning trees of G is -
In other words the number of spanning trees is equal to any cofactor of the admittance matrix of G. Notes Seeing that Cayley's formula follows from Kirchoff'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.
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|