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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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