矩陣-樹定理

矩陣樹定理是一個計數定理，常用於解決無向聯通圖的生成樹計數問題。

定理內容：

矩陣一樹定理(matrix-tree theorem)是一個計數定理.若連通圖G的鄰接矩陣為A，將A的對角線(i,i)元素依次換為節點i的度d(i)，其餘元素(i,j) (j!=i) 取Aij的相反數，所得矩陣記為M，則M的每個代數餘子式相等，且等於G的生成樹的數目.這就是矩陣一樹定理.我們常常稱矩陣M為基爾霍夫矩陣。

使用方法：

套用矩陣樹定理解無向聯通圖的生成樹計數問題，也就是求解這個聯通圖的基爾霍夫矩陣的某個代數餘子式的值。對於此類行列式求值的問題，常用的方法是著名的高斯消元法。因為將行列式的某一行整體加上另一行的某倍數，行列式的值不變，利用這一性質進行高斯消元可以將原行列式變成一個等價的上三角行列式，進而快速得到其值。其效率（時間複雜度）是O(n^3)的，其中n表示圖中點的個數。

值得注意的是，在實數意義下的高斯消元往往存在精度問題，而由於生成樹計數問題的解的大小往往極大，所以我們常常關注這個解對某個大質數取模後的精確結果，這就意味這實數意義下的高斯消元已無法勝任這一問題。這時我們需要尋求一種可以保證行列式每一個位置的值始終是整數的變換。其實這只需要在高斯消元的過程中使用對兩行輾轉相除的做法來代替用某一列的實數倍直接消除另一列的某值的做法即可，這樣做的效率（時間複雜度）是O(n^3logV)的，當然這個做法也支持在消元的過程中取模，可以說是非常適用於這個問題了。