| Abstract: |
The matrix-tree theorem states that the number of spanning
trees in a graph equals to the determinant of any cofactor of its
Laplacian matrix. We will analyze the theorem carefully, and show that
what the determinant really counts is the signed number of subgraphs
with good orientations. With this interpretation, it is then
straightforward to generalize the matrix-tree theorem to mixed graphs,
that is graphs where directed edges, undirected edges, loops and
parallel edges are allowed. At the end, we will show how to recover some
of previously known generalizations of the matrix-tree theorem from this
mixed graph version.
|