生成樹的計(jì)數(shù)及其應(yīng)用

1、生成樹的計(jì)數(shù)及其應(yīng)用安徽 周冬目錄生成樹的計(jì)數(shù)及其應(yīng)用1目錄1摘要2關(guān)鍵字2問題的提出2例一高速公路（SPOJ p104 Highways）2分析2預(yù)備知識2排列3行列式4新的方法7介紹7證明9理解12具體應(yīng)用12例二員工組織（UVA p10766 Organising the Organisation）13分析13例三國王的煩惱（原創(chuàng)）13分析14總結(jié)14參考文獻(xiàn)14摘要在信息學(xué)競賽中，有關(guān)生成樹的最優(yōu)化問題如最小生成樹等是我們經(jīng)常遇到的，而對生成樹的計(jì)數(shù)及其相關(guān)問題則少有涉及。事實(shí)上，生成樹的計(jì)數(shù)是十分有意義的，在許多方面都有著廣泛的應(yīng)用。本文從一道信息學(xué)競賽中出現(xiàn)的例題談起，首先介紹了一

2、種指數(shù)級的動態(tài)規(guī)劃算法，然后介紹了行列式的基本概念、性質(zhì)，并在此基礎(chǔ)上引入Matrix-Tree定理，同時通過與一道數(shù)學(xué)問題的對比，揭示了該定理所包含的數(shù)學(xué)思想。最后通過幾道例題介紹了生成樹的計(jì)數(shù)在信息學(xué)競賽中的應(yīng)用，并進(jìn)行總結(jié)。關(guān)鍵字生成樹的計(jì)數(shù) Matrix-Tree定理問題的提出例一高速公路（SPOJ p104 Highways）一個有n座城市的組成國家，城市1至n編號，其中一些城市之間可以修建高速公路?，F(xiàn)在，需要有選擇的修建一些高速公路，從而組成一個交通網(wǎng)絡(luò)。你的任務(wù)是計(jì)算有多少種方案，使得任意兩座城市之間恰好只有一條路徑？數(shù)據(jù)規(guī)模：1n12。分析我們可以將問題轉(zhuǎn)化到成圖論模型。因?yàn)槿?/p>

3、意兩點(diǎn)之間恰好只有一條路徑，所以我們知道最后得到的是原圖的一顆生成樹。因此，我們的問題就變成了，給定一個無向圖G，求它生成樹的個數(shù)t(G)。這應(yīng)該怎么做呢？ 經(jīng)過分析，我們可以得到一個時間復(fù)雜度為O(3n*n2)的動態(tài)規(guī)劃算法，因?yàn)樵}的規(guī)模較小，可以滿足要求。但是，當(dāng)n再大一些就不行了，有沒有更優(yōu)秀的算法呢？答案是肯定的。在介紹算法之前，首先讓我們來學(xué)習(xí)一些基本的預(yù)備知識。預(yù)備知識下面，我們介紹一種重要的代數(shù)工具行列式。為了定義行列式，我們首先來看一下排列的概念。排列定義1 由1，2，n組成的一個有序數(shù)組i1i2in稱為1，2，n的一個排列。由排列的定義可知，i1，i2，in表示了n個不同的

4、自然數(shù)，同時i1，i2，in中的每個自然數(shù)都是集合Sn=1，2，n中的一個元素，換句話說，定義了集合Sn到自身上的一個一一對應(yīng)。這個一一對應(yīng)可以用符號記之，稱為置換，而上述一一對應(yīng)可以改寫為其中j1j2jn是1，2，n的一個排列。所以這個一一對應(yīng)也可以用符號記之，因此對1，2，n的任一排列j1j2jn，可定義任取一個排列i1i2in，將其中兩個相鄰的自然數(shù)ij-1，ij對換一下，便造出一個新的排列i1i2ij-2ijij-1 ij+1in，稱為原來排列的對換排列，這樣一種步驟成為對換。顯然，對于任何一個排列經(jīng)過若干次對換后都可以變成標(biāo)準(zhǔn)排列12n。不過，不管經(jīng)過什么途徑作對換，在給定排列i1i

5、2in后，關(guān)于對換的次數(shù)有下列重要定理。定理1 將任意一個排列i1i2in通過對換變成標(biāo)準(zhǔn)排列12n，所需的對換次數(shù)的奇偶性與對換方式無關(guān)。利用這個定理，我們引入定義2 一個排列i1i2in稱為偶（奇）排列，如果有一種方式，經(jīng)過偶（奇）數(shù)次對換后，可以將排列i1i2in變?yōu)闃?biāo)準(zhǔn)排列12n。設(shè)排列i1i2in經(jīng)過t次對換后變?yōu)闃?biāo)準(zhǔn)排列12n，則數(shù)值(-1)t和對換方式無關(guān)。將它改寫成，即n個確定自然數(shù)1，2，n的排列，可以看作是集合Sn=1，2，n到自身上的一個一一對應(yīng)。將這個概念推廣，任取n個元素的集合S=a1，a2，an。對于集合S到自身上的一一對應(yīng)稱為的一個排列。容易看出，是的排列的充要條

6、件是i1i2in是1，2，n的排列。同樣，排列變?yōu)闃?biāo)準(zhǔn)排列的對換總次數(shù)的奇偶性和對換方式無關(guān)，因此引入符號其中t是某一種將變?yōu)榈膶Q方式的對換總次數(shù)。下面我們介紹行列式。行列式一階行列式是一個變量a11的函數(shù)det(a11)= a11，也可以改寫成為二階行列式是四個變量a11，a12，a21，a22的函數(shù)，也可以改寫成三階行列式是九個變量aij(i，j=1，2，3)的函數(shù)，同樣可以改寫成為通過觀察一、二、三階行列式的定義，我們得出了n階行列式的一般定義。定義3 n階矩陣A的行列式是一實(shí)數(shù)，記作detA，它定義為行列式有下列幾種常用的符號：由行列式的定義可知，利用定義直接計(jì)算行列式是很困難的，只

7、有在階數(shù)低時才可以直接用定義計(jì)算。為了能夠進(jìn)行計(jì)算，需要先導(dǎo)出行列式的若干基本性質(zhì)，在通過這些性質(zhì)，將復(fù)雜的行列式計(jì)算化為簡單的行列式計(jì)算，也可以將高階行列式的計(jì)算化為低階行列式的計(jì)算。性質(zhì)1 設(shè)A是n階矩陣，則detAT=detA。這個定理的重要意義在于，它告訴我們行列式的行和列的地位是平等的。確切地說，每個關(guān)于行的性質(zhì)，對列必然成立；反之亦然。性質(zhì)2 行列式的任兩行（或兩列）互換，行列式變號。推論 行列式的某兩行（或兩列）相同時，行列式的值為0。性質(zhì)3 用實(shí)數(shù)乘以一行（或列）后，所得到的行列式等于原來的行列式乘以。推論 行列式有兩行（或兩列）成比例，則該行列式的值為零。特別的，當(dāng)行列式有一

8、行（或列）全為零時，行列式的值為零。性質(zhì)4對列也有同樣性質(zhì)。推論 將行列式的任意行（或一列）乘以實(shí)數(shù)，再相應(yīng)地加到另一行（或另一列）上去，則行列式的值不變。例如，當(dāng)j1時下面我們介紹一種計(jì)算行列式的方法。首先，不難證明今取行列式我們可以將化為上三角形式，記為，同時記錄行交換次數(shù)S。根據(jù)定理11，易知：再利用剛才的結(jié)論，得。對于矩陣A，任取2p個自然數(shù)1i1i2ip=n，1j1j2jp1)個連通分量G1，G2，Gk，那么，我們可以重新安排C的行和列使得屬于G1的頂點(diǎn)首先出現(xiàn)，然后是G2?；貞浶辛惺降男再|(zhì)2，設(shè)我們一共進(jìn)行了t次行交換，顯然，我們同樣需要進(jìn)行t次列交換。因此，我們總共進(jìn)行了2t次交

9、換，所以，行列式的符號沒有改變。重新安排后的矩陣如下圖所示：帶方框的Gi表示了CGi。注意在方框以外的地方都是0因?yàn)槿我鈨蓚€連通分量之間沒有邊相連。設(shè)r是第i個連通分量中的第j個頂點(diǎn)，那么3、 如果G是一顆樹，那么它的Kirchhoff矩陣C的任一個n-1階主子式的行列式均為1。證明：為了證明這條重要的性質(zhì)，我們通過不斷的變換CrG從而得到一個上三角矩陣并且使得主對角線上所有的數(shù)字都是1。第一步：我們把所有的頂點(diǎn)按照在樹上離vr的距離從近至遠(yuǎn)排列。首先是vr，然后是離vr距離為1的點(diǎn)，接下來是離vr距離為2的點(diǎn)。距離相同的點(diǎn)可以任意排列。我們按照這個順序?qū)⑺械亩c(diǎn)重新編號。同時，把以r為根的

10、有根樹上vi的父結(jié)點(diǎn)vj稱為vi的父親，顯然，在剛才得到的順序中，vj出現(xiàn)在vi之前。第二步：將CrG的n-1行和n-1列按照剛才得到的順序重新排列。因?yàn)樾辛卸夹枰粨Q，所有總交換次數(shù)是偶數(shù)，CrG的行列式不邊。第三步：按照剛才得到的順序的逆序處理，對于每個i，如果vi的父親vj不等于vr，則把第i列加到第j列上去。這樣處理過之后，我們來看一下現(xiàn)在的CrG是否和我們的希望相同。我們通過歸納法來證明。顯然，最后一列符合要求，因?yàn)樽詈笠粋€點(diǎn)只和它的父親之間有邊，它的度為1。假設(shè)當(dāng)前處理的是第i列，并且第i+1至第n-1列都符合要求。我們設(shè)vi的父親是vj，它有k個孩子，顯然，只有第i1，i2，ik

11、列才會加到第i列上來。所有這些列，都在第i行有個-1而在對角線上有個1，而第i列在第j、i1，i2，ik行上為-1而在第i行上為k+1。每一列加上來的時候，第i行第i列減一同時與之相對的那一列加一變?yōu)?。最后第第i行第i列變?yōu)?，第i1，i2，ik行變?yōu)?。也就是說，最后CrG會變成上三角矩陣并且主對角線上所有的數(shù)字都是1。這就證明了我們的結(jié)論。在證明Matrix-Tree定理的過程中，我們使用了無向圖G的關(guān)聯(lián)矩陣B。B是一個n行m列的矩陣，行對應(yīng)點(diǎn)而列對應(yīng)邊。B滿足，如果存在一條邊e=vi,vj，那在e所對應(yīng)的列中，vi和vj所對應(yīng)的那兩行，一個為1、另一個為-1，其他的均為0。至于誰是1誰

12、是-1并不重要，如下圖所示。接下來，我們考察BBT。容易證明，(BBT)ij等于B的第i行與第j列的點(diǎn)積。所以，當(dāng)i=j時，(BBT)ij等于與vi相連的邊的個數(shù)，即vi的度數(shù)；而當(dāng)ij時，如果有一條連接vi、vj的邊，則(BBT)ij等于-1，否則等于0。這與Kirchhoff矩陣的定義完全相同！因此，我們得出：C=BBT！也就是說，我們可以將C的問題轉(zhuǎn)化到BBT上來，這樣做有什么用呢？設(shè)Br為B去掉第r行后得到的新矩陣，易知Cr=BrBrT。根據(jù)Binet-Cauchy公式，我們可以得到：是把Br中屬于x的列抽出后形成的新矩陣。我們注意到，當(dāng)x中的邊形成環(huán)時，總有。例如，如果新圖中存在一個

13、大小為3的環(huán)，那么我們可以重新安排如下圖所示：這樣，等于左上角3階子式的行列式乘以右下角n-4階矩陣的行列式。而左上角的3階子式是退化的，它每行每列的和都是0。因此也等于0。類似的證明可以推廣到環(huán)的大小任意的情況。顯然，可以看成是僅由所有的頂點(diǎn)和屬于x的邊構(gòu)成的新圖的Kirchhoff矩陣的一個n-1階主子式。根據(jù)圖的Kirchhoff矩陣的性質(zhì)，如果將所有屬于x的n-1條邊加入圖中后形成一顆樹，那么為1；而如果沒有形成樹，則必然存在一個環(huán)，那么。也就是說，我們考察邊集所有大小為n-1的子集，如果這個子集中的邊能夠形成一顆樹，那么我們的答案加1，否則不變。這就恰好等于原圖生成樹的個數(shù)！因此，我

14、們成功地證明了Matrix-Tree定理！如果圖中有重邊，Matrix-Tree定理同樣適用，具體的證明方法類似，請讀者自己思考。因?yàn)橛?jì)算行列式的時間復(fù)雜度為O(n3)，因此，生成樹的計(jì)數(shù)也可以在O(n3)的時間內(nèi)完成。理解剛才的分析可能有些“深奧”，下面讓我們從直觀上來理解一下這個定理。我們首先來看一道簡單的數(shù)學(xué)問題：試求方程所有非負(fù)整數(shù)解的個數(shù)。這是我們大家都很熟悉的一道組合計(jì)數(shù)問題。我們通常的做法是設(shè)有2個1和兩個，我們將這4個元素任意排列，那么不同的排列的個數(shù)就等于原方程解的個數(shù)，即。為什么要這樣做呢？我們將所有6種排列列出后發(fā)現(xiàn)，一種排列就對應(yīng)了原方程的一個解：11對應(yīng)x1=0，x2

15、=0，x3=2；11對應(yīng)x1=0，x2=1，x3=1；11對應(yīng)x1=0，x2=2，x3=0；也就是說，我們通過模型的轉(zhuǎn)化，找出了原問題和新問題之間的對應(yīng)關(guān)系，并利用有關(guān)的數(shù)學(xué)知識解決了轉(zhuǎn)化后的新問題，也就同時解決了原問題。這種轉(zhuǎn)化的重要意義在于：在不同問題之間的架起了互相聯(lián)系的橋梁?；氐轿覀冇懻摰腗atrix-Tree定理上來。我們同樣是經(jīng)過模型的轉(zhuǎn)化后（將圖模型轉(zhuǎn)化為矩陣模型），發(fā)現(xiàn)Binet-Cauchy公式展開式中的每一項(xiàng)對應(yīng)著邊集一個大小為n-1的子集。其中，值為1的項(xiàng)對應(yīng)一顆生成樹，而沒有對應(yīng)生成樹的項(xiàng)值為0。這樣，將問題轉(zhuǎn)化為求展開式中所有項(xiàng)之和。再利用已有的數(shù)學(xué)知識，就可以成功解

16、決這個問題。我們將這兩個問題進(jìn)行對比，可以發(fā)現(xiàn)：在第一個問題中，方程的解所扮演的角色與圖的生成樹在第二問題中所扮演的角色類似；而第一個問題中排列方案所扮演的角色與第二個問題中展開式中的每一項(xiàng)所扮演的角色相同。同時，在每個問題中，兩個對象之間又是互相對應(yīng)的。這兩個問題的不同之處僅僅在于：相互之間的對應(yīng)關(guān)系更加隱蔽、復(fù)雜，需要更加強(qiáng)大的數(shù)學(xué)理論來支撐。具體應(yīng)用下面我們通過幾道例題來看一下信息學(xué)競賽中出現(xiàn)的生成樹的計(jì)數(shù)問題。 例二員工組織（UVA p10766 Organising the Organisation）Jimmy在公司里負(fù)責(zé)人員的分級工作，他最近遇到了一點(diǎn)小麻煩。為了提高公司工作的效率

17、，董事會決定對所有的員工重新分級！圖a員工分級圖分級后的情況如圖a所示，A直接領(lǐng)導(dǎo)B和D，D直接領(lǐng)導(dǎo)C。具體來說，除了一個總經(jīng)理例外，其他所有的員工有且只有一個直接領(lǐng)導(dǎo)。由于員工直接的人際關(guān)系，可能出現(xiàn)a和b都不愿意讓對方成為自己直接領(lǐng)導(dǎo)的情況。公司里的n位員工1-n編號，并且董事會已經(jīng)決定讓標(biāo)號為k的員工擔(dān)任總經(jīng)理。Jimmy的任務(wù)就是一共有多少種不同的員工分級方案。數(shù)據(jù)規(guī)模：1n50。分析這道題目的解法比較明顯。如果a和b直接沒有矛盾，就在他們之間連一條邊。顯然，最后我們得到的員工之間的關(guān)系圖就使原圖的一顆生成樹。雖然我們規(guī)定了生成樹的根，但是因?yàn)闊o向圖生成樹的個數(shù)與根無關(guān)，所以我們只需要

18、直接利用Matrix-Tree定理計(jì)算原圖的生成樹的個數(shù)即可。例三國王的煩惱（原創(chuàng)）Byteland的國王Byteotia最近很是煩惱，他的國家遭遇到了洪水的襲擊！百年未遇的洪水沖毀了Byteland許多重要的道路，使得整個國家處于癱瘓狀態(tài)。Byteland由n座城市組成，任何兩個不同城市之間都有道路相連。為了盡快使國家恢復(fù)正常秩序，Byteotia組織了專家進(jìn)行研究，列舉出了所有可以正常同行的道路（其他的道路可能還在洪水中L）。其中有的已經(jīng)被沖毀，需要重新修復(fù);有的則可以繼續(xù)使用。很奇怪的是，所有可以繼續(xù)使用的道路并沒有形成環(huán)。為了最大限度的節(jié)省時間，Byteotia希望只修復(fù)最少的道路就可

19、以使得整個國家連通。Byteotia本來準(zhǔn)備對每一種方案進(jìn)行評估，選擇最優(yōu)的，不過很快他發(fā)現(xiàn)方案的個數(shù)實(shí)在是太多了。因此，他找到了你Byteland最優(yōu)秀的計(jì)算機(jī)專家，幫他計(jì)算一下所有可能的修復(fù)方案的個數(shù)。數(shù)據(jù)規(guī)模：1n500。分析這道題目乍看起來很難，因?yàn)橐蠼y(tǒng)計(jì)修復(fù)道路個數(shù)最少的方案的個數(shù)，同時還有不需要修復(fù)的道路需要考慮。仔細(xì)分析后我們發(fā)現(xiàn)題目中一個十分重要的條件就是：所有可以繼續(xù)使用的道路并沒有形成環(huán)！這就為我們的解題創(chuàng)造了條件。我們都知道，讓一個n個點(diǎn)的圖連通最少需要n-1條邊，而這些邊形成一顆樹，而樹的一個重要性質(zhì)就是無環(huán)，因此所有可以繼續(xù)使用的道路都一定存在于最后得到的樹中。這樣，我