Kirchhoff矩陣樹定理可以簡稱矩陣樹定理，可以解決了一張圖的生成樹個數(shù)計數(shù)問題。

本篇中的圖，無論無向還是有向，都允許重邊，但是不允許自環(huán)。

一、概況

1. 無向圖情況

設G是一個有 n 個頂點的無向圖。定義度數(shù)矩陣 D(G) 為：

設為點 i 與點 j 相連的邊數(shù)，并定義鄰接矩陣A為：

定義 Laplace 矩陣（亦稱 Kirchhoff 矩陣）L為：

記圖G的所有生成樹個數(shù)為t(G)。

2. 有向圖情況

設G是一個有 n 個頂點的有向圖。定義出度矩陣為：

類似地定義入度矩陣

設為點 i 指向點 j 的有向邊數(shù)，并定義鄰接矩陣A為：

定義出度 Laplace 矩陣為：

定義入度 Laplace 矩陣為：

記圖G的以 r 為根的所有根向樹形圖個數(shù)為 。所謂根向樹形圖，是說這張圖的基圖是一棵樹，所有的邊全部指向父親。

記圖G的以 r 為根的所有葉向樹形圖個數(shù)為。所謂葉向樹形圖，是說這張圖的基圖是一棵樹，所有的邊全部指向兒子。

二、定理敘述

矩陣樹定理具有多種形式。其中用得較多的是定理 1、定理 3 與定理 4。

定理 1（矩陣樹定理，無向圖行列式形式） 對于任意的 i，都有

其中記號表示矩陣L(G)的第行與第列構成的子矩陣。也就是說，無向圖的 Laplace 矩陣具有這樣的性質，它的所有 n-1 階主子式都相等。

定理 2（矩陣樹定理，無向圖特征值形式） 設為L(G)的 n-1 個非零特征值，那么有

定理 3（矩陣樹定理，有向圖根向形式） 對于任意的 k，都有

因此如果要統(tǒng)計一張圖所有的根向樹形圖，只要枚舉所有的根 k 并對求和即可。

定理 4（矩陣樹定理，有向圖葉向形式） 對于任意的 k，都有

因此如果要統(tǒng)計一張圖所有的葉向樹形圖，只要枚舉所有的根 k 并對求和即可。

BEST 定理

定理 5 (BEST 定理） 設G是有向歐拉圖，那么G的不同歐拉回路總數(shù)ec(G)是

 注意，對歐拉圖G的任意兩個節(jié)點，都有，且歐拉圖G的所有節(jié)點的入度和出度相等。