Matrix tree theorem

From Algorithmist
Jump to: navigation, search

Matrix tree theorem provides a connection between the number of spanning trees of a graph and graph's Laplacian matrix.

A degree matrix D of an undirected graph is a square matrix, which contains the sequence of degrees of graph's vertices on its diagonal, and zeroes elsewhere.

A Laplacian of a graph is defined as: L=D-A, where A is the adjacency matrix, and D is the degree matrix.

Matrix tree theorem states, the determinant of a matrix, obtained by deleting the k-th row and column from the graph's Laplacian is independent from the choice of k, and is equal to the number of spanning trees of the graph.

References[edit]

  • D.B. West. Introduction to graph theory. Prentice-Hall, 1996. Chapter 2.2.
  • Godsil C., Royle G. Algebraic graph theory. Springer-Verlag, 2001. Chapter 13.2.