Matrix tree theorem

From Algorithmist
Jump to navigation Jump to search

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

A degree matrix 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: , where is the adjacency matrix, and is the degree matrix.

Matrix tree theorem states, the determinant of a matrix, obtained by deleting the -th row and column from the graph's Laplacian is independent from the choice of , 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.