生成樹計數問題
給一副n個節點的無向圖G，求一個包含n-1條邊的邊集使得邊集的邊構成一顆樹，問這樣的邊集的數量。
矩陣樹定理
以下我們都不對重邊與自環進行討論。 先定義度數矩陣D，是一個n*n的矩陣。 Di,i=節點i的度數，對于i不等于j，Di,j=0。 再定義鄰接矩陣A，也是一個n*n的矩陣。 i與j有邊相連就有Ai,j=1否則Ai,j=0。 最后定義基爾霍夫矩陣C=D-A。 那么，Ci,i=i的度數，對于i不等于j，若i與j間有邊相連則Ci,j=-1否則Ci,j=0。 為了方便一些萌新，講講行列式吧。 我們都知道一個n*n矩陣a的行列式的定義： ∑b是一個n的排列(?1)b的逆序對個數?Πni=1ai,bi 這個記作det(a)，或者說|a|。 行列式有一些性質： 1、|A|=|AT| 2、|AB|=|A||B| 我們知道矩陣乘法后位置(i,j)由A的第i行與B的第j列點積而來，即A的第i行與BT的第j行點積，容易得到|AB|=|A||BT|=|A||B| 3、兩個矩陣都是n*n的，除了第一行完全相同，那么它們的行列式之和等于將它們第一行相加其余不變的新矩陣的行列式。 這個非常好懂。 同樣根據性質能得到一些推論： 1、將A任意兩行或兩列交換得到新矩陣B，則|B|=-|A|。 根據定義看，容易證明交換后任意排列的逆序對個數改變了1。 而這樣的話，重排對角線因為每次一定要同時交換行列，所以行列式是不變的。 2、將A任意一行同時乘上x得到新矩陣B，則|B|=x|A|。 易證 3、將A任意一行加到另一行上，得到新矩陣B，則|B|=|A| 我們假如是將第二行加到第一行上。 根據之前的性質3等同于|A|+|C| C是一個前兩行完全相同的矩陣。 容易知道|C|=0，為什么？ 看行列式的定義，例如b1=i，b2=j，那么當b1=j而b2=i時逆序對個數剛好差1，正負形相反，而無論后面是什么，貢獻完全正負抵消，因此為0。 這三個推論讓我們可以使用高斯消元求解行列式。 4、每行每列和均為0的矩陣行列式為0。 高斯消元過程中這一性質仍然存在。 最后消出來，最后一行前n-1一定為0，又因和為0，所以最后一項也是0，那么行列式即為0。
來定義一個矩陣A的余子式Mi,j表示A去掉第i行與第j列后的行列式。 矩陣樹定理：基爾霍夫矩陣C的任意余子式Mi,i就是圖G的生成樹個數。 接下來我們嘗試證明吧。
先知道基爾霍夫矩陣的性質： 1、|C|=0 容易知道C的每行每列和均為0，那么根據推論4得出行列式也為0。 2、若圖G不聯通，則任意余子式Mi,i=0 我們進行重標號使聯通的點在主對角線上連續。 因此同一個聯通塊對應了一個基爾霍夫矩陣（除了該聯通塊內部有邊其余均為0）。 顯然Mi,i是0，因為去掉任意第i行與第i列后，除i所在聯通塊的基爾霍夫矩陣外還有其他的基爾霍夫矩陣，而Mi,i等于所有這些矩陣行列式的積（這個易證），根據基爾霍夫矩陣性質1得證。 3、若圖G是一顆樹，則任意余子式Mi,i=1 未完待續
