生成樹(shù)計(jì)數(shù)問(wèn)題

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

矩陣樹(shù)定理

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

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

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