Counting Spanning Trees

I really enjoy Atabey Kaygun’s blog. If you like Mathematics and Lisp, you’re sure to enjoy it too. A typical post looks at a mathematical problem and either presents a solution or experiments with the problem with Common Lisp.

One of his recent posts considers spanning trees (ST) and how to count them. Most of us—at least those who have taken an algorithms course—are familiar with the simple construction to find an ST but may not know how to count them.

Atabey introduces the notion of the Laplacian of a graph, \(L\), defined by \[l_{ij} = \begin{cases} \text{deg}(i) & \text{if } i=j,\\ -1 & \text{if there is an edge between } i \text{ and } j,\\ 0 & \text{otherwise}. \end{cases}\]

Kirchhoff’s theorem tells us that the number of spanning trees is equal to any of the minor determinants of the Laplacian. This is a pretty neat result and one that I didn’t know. Atabey’s post has a couple of worked examples and Lisp code to make the calculations.

As I said, if you like Mathematics and enjoy programming in Lisp, you should definitely give this post a read.

This entry was posted in General and tagged , . Bookmark the permalink.