生成樹計數(shù)及其應用

引入最?。ù螅┥蓸?/p>

最?。ù螅┒认拗粕蓸渥顑?yōu)比率生成樹……[例一]高速公路一個國家需要在n座城市之間建立通信網(wǎng)絡。某些城市之間可以鋪設通信線路。要求任意兩座城市之間恰好有一條通訊路線，試求方案個數(shù)。滿足：1≤n

≤12。分析首先將問題抽象成圖論模型點：城市邊：通訊線路任意兩點之間恰好只有一條路徑這是一顆樹！問題轉(zhuǎn)化為：給定一個n個點的無向圖，其中無重邊和自環(huán)，試求其生成樹的個數(shù)。分析由于原題規(guī)模較小，因此

可以使用一些復雜度較高的算法來解決它，如指數(shù)級的動態(tài)規(guī)劃算法。但是，如果規(guī)模更大一些呢？預備知識行列式、關(guān)聯(lián)矩陣、Kirchhoff矩陣行列式行列式是一種十分重要的代數(shù)工具由n2個數(shù)組成的n階矩陣A的行列式是一個實數(shù)，記作detA，它定義為當n=1時，detA=A11當n>1時，–其中Mij是去掉A中第i行和第j列全部元素后，按原來順序排成的新矩陣。det

A

a11

det

M11

a12

det

M

12

ni11i1i1i1

a

det

M行列式可以它的一些性根據(jù)行列式的定義，質(zhì)1、一個矩陣的轉(zhuǎn)置矩陣的行列式的值不變2、矩陣的任兩行（或兩列）互換，行列式變號3、當矩陣有一行（或列）全為零時，行列式的值為04、用實數(shù)λ乘矩陣的任一行（或列），行列式的值也乘以λ5、將矩陣的任一行（或列）乘以實數(shù)λ，再相應地加到另一行（或列）上去，行列式的值不變行列式的計算方法

根據(jù)行列式的性質(zhì)，可以得到一種易于編程的計算矩陣的行列式的方法由性質(zhì)2可知知道，矩陣的行或列進行交換時，僅僅改變行列式的符號；由性質(zhì)5可知，可以在不改變其行列式的前提下化簡矩陣因此，只需將矩陣化為上三角形式，同時記錄行交換次數(shù)，然后計算其主對角線元素的乘積，如果交換次數(shù)為奇數(shù)，則取乘積的相反數(shù)時間復雜度為O(n3)圖的關(guān)聯(lián)矩陣對于無向圖G，

定義它的關(guān)聯(lián)矩陣B是一個n*m的矩陣，并且滿足：–如果ek=(vi，vj)，那么Bik和Bjk一個為1，另一個為-1，而第k列的其他元素均為0。圖G的關(guān)聯(lián)矩陣如右下角所示：v1v2v3圖Ge1e2e3

01

e1

e2

e3

1

1 0

1

0

11v1v2v3圖的關(guān)聯(lián)矩陣圖的關(guān)聯(lián)矩陣有什么特殊的性質(zhì)呢？不妨來 一下B和它的轉(zhuǎn)置矩陣BT的乘積。圖的關(guān)聯(lián)矩陣根據(jù)矩陣乘法的定義，

可以得到：也就是說，BBTij是B第i行和第j行的內(nèi)積。因此，當i=j時，BBTij=vi的度數(shù)；而當i≠j時，如果存在邊(vi，vj)，那么BBTij=-1，否則BBTij=0。通常將BBT稱為圖的Kirchhoff矩陣。BBT

ij

m

mkjT

ik

ik

jkB

B

B

Bk

1

k

1圖的Kirchhoff矩陣對于無向圖G，它的Kirchhoff矩陣C定義為它的度數(shù)矩陣D減去它的鄰接矩陣A。顯然，這樣的定義滿足剛才描述的性質(zhì)?？梢砸胗辛薑irchhoff矩陣這個工具，Matrix-Tree定理：對于一個無向圖G，它的生成樹個數(shù)等于其Kirchhoff矩陣任何一個n-1階主子式的行列式的絕對值。所謂n-1階主子式，就是對于任意一個r，將C的第r行和第r列同時刪去后的新矩陣，用Cr表示。Matrix-Tree定理讓通過一個例子來解釋一下定理。如圖所示，G是一個由5個點組成的無向圖。它的Kirchhoff矩陣C為2

0

10

1

0

10

11

2

1

1

0 0

3

1

11

01

20

1Matrix-Tree定理取r=2，根據(jù)行列式的定義|detC2

|=11，這11顆生成樹如下圖所示。這個定理看起來非常“神奇”，讓試著去證明一下吧！嘗定理的證明經(jīng)過分析，

可以發(fā)現(xiàn)圖的Kirchhoff矩陣C具有一些有趣的性質(zhì)：C的行列式總是0。如果圖是不連通的，則C的任一個n-1階主子式的行列式均為0。如果圖是一顆樹，那么C的任一個n-1階主子式的行列式均為1。證明略。定理的證明

知道，C=BBT，因此，的問題轉(zhuǎn)化到BBT上來?？梢园袰設Br為B去掉第r行得到的矩陣，容

道Cr

=B

Br

T。這時，根據(jù)Binet-Cauchy公式，

可以將Cr的行列式展開。r是把B

中屬于x的列抽出后形成的新矩陣。det2detdxrxxTr

rTxrdet

B

det

B

BBetB1,2,,

mx

1,2,,

mx||x1n

||x1n

x

r1,2,,

mx||x1nTrr

det

BC

B

rxr其中，B定理的證明x式。的子圖。detC2detdxrdetB1,2,,

mxxn

|1|Txxr

rTxr

r

B

Tr

r

detBBrBBet

detBx1,2,,

mxxn

|1|x1,2,,

mxn

|1|Tx

xr

rBB若注屬意于觀察x的上n面-1的條式邊子形，成了一實顆際樹上時是，圖由G

的Kirchhoff矩陣的性個質(zhì)可n-知1主子其等中于G1x。x若是屬由于所有x的的n頂-1點條和邊屬沒于有x形的成邊樹組，成則的G一中個將G至少含有兩個連通塊，這時等于0。因此，認為：每次從邊集中選出n-1條邊，若它們形成了生成樹，則答案加1，否則不變。Txxr

rBdet

B

Tx

xr

rBdet

B定理的理解當x取遍邊集所有大小為n-1的子集后，我們就可以得到原圖生成樹的個數(shù)。這樣我們成功證明了定理！剛才的證明過程看起來有些“深奧”，下面就讓

從直觀上來理解一下這個定理的原理。定理的理解試求方程x1

+x2

+

x3

=2所有非負整數(shù)解的個數(shù)。這是大家都很熟悉的一道組合計數(shù)問題。通常的解法是，設有2個1和兩個*，這4個元素任意排列，那么不同的排列的個為什么要這樣做呢？4數(shù)就等于原方程解的個數(shù)，即C2

。定理的理解?所有6種排列列出后發(fā)現(xiàn)，一種排列就對應了原方程的一個解：–**11對應x1=0，x2=0，x3=2–*1*1對應x1=0，x2=1，x3=1–*11*對應x1=0，x2=2，x3=0–

……也就是說，通過模型的轉(zhuǎn)化，找出了原問題和新問題之間的對應關(guān)系，并利用有關(guān)的數(shù)學知識解決了轉(zhuǎn)化后的新問題，也就同時解決了原問題。這種轉(zhuǎn)化的重要意義在于：在不同問題之間的架起了互相聯(lián)系的橋梁。定理的理解回到的Matrix-Tree定理上來。

同樣是經(jīng)過模型的轉(zhuǎn)化后（將圖模型轉(zhuǎn)化為矩陣模型），發(fā)現(xiàn)Binet-Cauchy公式展開式中的每一項對應著邊集一個大小為n-1的子集。其中，值為1的項對應一顆生成樹，而沒有對應生成樹的項值為0。這樣，將問題轉(zhuǎn)化為求展開式中所有項之和。再利用已有的數(shù)學知識，就可以成功解決這個問題。兩個問題的對比類似方程的解

圖的生成樹對應類似排列方案

展開式的項不同之處在于：相互之間的對應關(guān)系更加隱蔽、復雜需要更加強大的數(shù)學理論來支撐對應定理的擴展利用該定理，

可以容易得到著名的Cayley公式：完全圖Kn有nn-2顆生成樹。

剛才只對圖中沒有重邊的情況進行了分析。實際上，圖中有重邊時該定理仍然成立，并且證明與沒有重邊的情況類似。該定理也可以擴展到有向圖上，用來計算有向圖的外向樹的個數(shù)。[例二]

UVa

p10766the

anisation[例三]國王的煩惱anising信息學競賽中的應用[例三]國王的煩惱By

and由n座城市組成。，許多道路都被沖由于遭到了洪水的毀了。國王Byteotia組織了進行研究，列舉出了所有可以正常通行的道路。其中有的已經(jīng)被沖毀，需要重新修復；有的則可以繼續(xù)使用。并且所有可以繼續(xù)使用的道路沒有形成環(huán)。[例三]國王的煩惱下–紅面通示過可一以個繼例續(xù)子使來用看的一道下路。bacdB如y右te圖ot所ia示希，望修建

最By

a道nd路由，a、使b得、任c意、兩d個，城4座市城之市間組都成能其互中達。請–藍你色計邊算表可示行可方以案通的行總但數(shù)需。要修復的道路共有2種方案，如右下角所示bacdbacd方案2方案1問題分析簡單情況如果沒有可以繼續(xù)使用的路？樹！樹的重要特征無環(huán)！所有可以繼續(xù)使用的道路必然存在于某顆生成樹上！將問題轉(zhuǎn)化為：求原圖生成樹的個數(shù)，其中某些邊必選。問題分析難點在于–由于必選邊的存在，Matrix-Tree定理無法直接應用

知道，如果要求生成樹中必須包含某條邊e，那么，可以將e壓縮，將原圖的問題轉(zhuǎn)化到新圖上來。因此，需要1、