生成樹計數(shù)問題

給一副n個節(jié)點的無向圖G，求一個包含n-1條邊的邊集使得邊集的邊構(gòu)成一顆樹，問這樣的邊集的數(shù)量。

矩陣樹定理

以下我們都不對重邊與自環(huán)進(jìn)行討論。 先定義度數(shù)矩陣D，是一個n*n的矩陣。 Di,i=節(jié)點i的度數(shù)，對于i不等于j，Di,j=0。 再定義鄰接矩陣A，也是一個n*n的矩陣。 i與j有邊相連就有Ai,j=1否則Ai,j=0。 最后定義基爾霍夫矩陣C=D-A。 那么，Ci,i=i的度數(shù)，對于i不等于j，若i與j間有邊相連則Ci,j=-1否則Ci,j=0。 為了方便一些萌新，講講行列式吧。 我們都知道一個n*n矩陣a的行列式的定義： ∑b是一個n的排列(?1)b的逆序?qū)€數(shù)?Πni=1ai,bi$/sum_{b是一個n的排列}(-1)^{b的逆序?qū)€數(shù)}*/Pi_{i=1}^na_{i,b_i}$ 這個記作det(a)，或者說|a|。 行列式有一些性質(zhì)： 1、|A|=|AT|$|A|=|A^T|$ 2、|AB|=|A||B| 我們知道矩陣乘法后位置(i,j)由A的第i行與B的第j列點積而來，即A的第i行與BT$B^T$的第j行點積，容易得到|AB|=|A||BT|=|A||B|$|AB|=|A||B^T|=|A||B|$ 3、兩個矩陣都是n*n的，除了第一行完全相同，那么它們的行列式之和等于將它們第一行相加其余不變的新矩陣的行列式。 這個非常好懂。 同樣根據(jù)性質(zhì)能得到一些推論： 1、將A任意兩行或兩列交換得到新矩陣B，則|B|=-|A|。 根據(jù)定義看，容易證明交換后任意排列的逆序?qū)€數(shù)改變了1。 而這樣的話，重排對角線因為每次一定要同時交換行列，所以行列式是不變的。 2、將A任意一行同時乘上x得到新矩陣B，則|B|=x|A|。 易證 3、將A任意一行加到另一行上，得到新矩陣B，則|B|=|A| 我們假如是將第二行加到第一行上。 根據(jù)之前的性質(zhì)3等同于|A|+|C| C是一個前兩行完全相同的矩陣。 容易知道|C|=0，為什么？ 看行列式的定義，例如b1=i，b2=j，那么當(dāng)b1=j而b2=i時逆序?qū)€數(shù)剛好差1，正負(fù)形相反，而無論后面是什么，貢獻(xiàn)完全正負(fù)抵消，因此為0。 這三個推論讓我們可以使用高斯消元求解行列式。 4、每行每列和均為0的矩陣行列式為0。 高斯消元過程中這一性質(zhì)仍然存在。 最后消出來，最后一行前n-1一定為0，又因和為0，所以最后一項也是0，那么行列式即為0。

來定義一個矩陣A的余子式Mi,j表示A去掉第i行與第j列后的行列式。 矩陣樹定理：基爾霍夫矩陣C的任意余子式Mi,i就是圖G的生成樹個數(shù)。 接下來我們嘗試證明吧。

先知道基爾霍夫矩陣的性質(zhì)： 1、|C|=0 容易知道C的每行每列和均為0，那么根據(jù)推論4得出行列式也為0。 2、若圖G不聯(lián)通，則任意余子式Mi,i=0 我們進(jìn)行重標(biāo)號使聯(lián)通的點在主對角線上連續(xù)。 因此同一個聯(lián)通塊對應(yīng)了一個基爾霍夫矩陣（除了該聯(lián)通塊內(nèi)部有邊其余均為0）。 顯然Mi,i是0，因為去掉任意第i行與第i列后，除i所在聯(lián)通塊的基爾霍夫矩陣外還有其他的基爾霍夫矩陣，而Mi,i等于所有這些矩陣行列式的積（這個易證），根據(jù)基爾霍夫矩陣性質(zhì)1得證。 3、若圖G是一顆樹，則任意余子式Mi,i=1 未完待續(xù)