鄭藝容，周　雪

(1.廈門理工學院應用數(shù)學學院,福建 廈門 361024;2.福州大學離散數(shù)學中心，福建 福州 350003 )

生成樹的計數(shù)

鄭藝容1,2，周雪2

(1.廈門理工學院應用數(shù)學學院,福建 廈門 361024;2.福州大學離散數(shù)學中心，福建 福州 350003 )

從組合數(shù)學的角度研究生成樹的計數(shù).先利用容斥原理，得到3個組合恒等式，再從組合數(shù)學的角度出發(fā)，并利用數(shù)學歸納法給出了Cayley’s公式的又一簡便證明.該計數(shù)方法將圖的計數(shù)問題與組合數(shù)學中的經(jīng)典問題聯(lián)系起來，更好地揭示了生成樹計數(shù)的本質(zhì).

Cayley’s公式；生成樹；容斥原理；數(shù)學歸納法

計算圖的不同生成樹的個數(shù)是圖的計數(shù)問題中的一個重要研究課題.1857年，Cayley[1]在研究給定碳原子數(shù)n的飽和碳氫化合物(CnH2n+2)的同分異構(gòu)體的數(shù)目時，提出“樹”的概念， 即不含圈的連通圖.如果連通圖G的一個子圖T是一棵樹，且包含G的所有頂點，則該子圖T稱為G的生成樹(SpanningTree).設(shè)G是一個圖，t(G)表示G中不同生成樹的個數(shù).Cayley于1889年給出計算n階完全圖的不同生成樹個數(shù)的公式，即著名的Cayley’s公式.

定理1[2](Cayley’s公式)n階完全圖的不同生成樹的個數(shù)

Cayley’s公式有很多不同的證明方法，參見文獻[2-5].本文又給出Cayley’s公式的又一簡單證明.

1　預備知識

首先介紹一些基本概念和結(jié)論.容斥原理是組合數(shù)學中一個非常重要的定理，其內(nèi)容如下：

定理2[6 ](容斥原理)設(shè)A是有限集，Ai?A(i=1,2,…,n,n≥2)，則

設(shè)N={1,2,…,n}，M={1,2,…，m}，A表示N上所有p維數(shù)組構(gòu)成的集合， 其中p

定理3設(shè)n,m,p∈N+,p

又A=A1∪A2∪…∪Am，根據(jù)容斥原理、對稱性及引理1可得：

特別地，當p=n-2時可得以下推論：

2　生成樹計數(shù)公式的再證明

證明由上述定義可知：T1∩T2∩…∩Tk那么表示頂點1,2,…,k(1≤k≤n)均為樹葉的n階生成樹構(gòu)成的集合，這樣的任意一棵樹可經(jīng)過下述兩個步驟得到.

(i)由頂點k+1,k+2,…,n導出的子圖T是一棵樹，易知恰好有tn-k個這樣的T；

證明T表示所有n階生成樹構(gòu)成的集合，Ti(i=1,2,…n)表示所有n階生成樹中頂點i為樹葉的生成樹構(gòu)成的集合，由于每棵非平凡樹至少有兩片樹葉，故T=T1∪T2∪…∪Tn，由容斥原理、對稱性及引理2可知：

以下給出Cayley’s 公式的另一證明.

定理4所有不同n階生成樹的個數(shù)tn=nn-2( Cayley’s 公式)

證明用數(shù)學歸納法

(i)易知t1=t2=1，t3=3 結(jié)論顯然成立.

(ⅱ)假設(shè)定理對小于n的正整數(shù)都成立.

(ⅲ)以下證明對n結(jié)論成立.根據(jù)引理3

注3第1，第2，第3個等號成立分別根據(jù) 引理3，歸納假設(shè)第2步， 推論1.

3　小結(jié)

Cayley’s 公式是圖計數(shù)中的經(jīng)典公式，已有很多不同的證明方法，本文利用由容斥原理得到的組合恒等式并借助數(shù)學歸納法給出Cayley’s 公式的又一簡單證明.接下來可進一步研究Cayley’s 公式的不同證明方法，特別是能將圖的其它經(jīng)典問題與圖的計數(shù)問題聯(lián)系起來證明Cayley’s 公式，更好地揭示圖論中的一些本質(zhì)聯(lián)系.

[1]CAYLEY A.On the theory of the analytical forms called trees[J].Philophical Magazine,1857,13(4):172-176.

[2]CAYLEY A.A theorem on trees[J].Quart J Math,1989,23:376-378.

[3]SHOR P W.A new proof of Cayley’s formula for counting labeled trees[J].J Combin Theory:Series A,1995,71:154-158.

[4]ARIANNEJAD M,EMAMI M.A new proof of Cayley’s formula for counting labeled spanning trees[J].Electronic Notes in Discr Math,2014,45:99-102.

[5]GODSIL C,ROYLE G.Algebraic graph theory[M].New York:Springer-Verlag,2001.

[6]曹汝成.組合數(shù)學[M].廣州：華南理工大學出版社,2000.

2

(1.SchoolofAppliedMathematics,XiamenUniversityofTechnology,Xiamen361024,China;2.CenterforDiscreteMathematics,FuzhouUniversity,Fuzhou350003,China)

(責任編輯曉軍)

Counting Spanning Trees

ZHENG Yi-rong1,2， ZHOU Xue

Inthispaper,weexploredthepossibilityofcountingspanningtreeinacombinatorialapproach.Wegotthreecombinatorialidentifiesapplyingtheinclusion-exclusionprinciple.Basedontheseidentifiesandmathematicsinduction,wegaveaneasyprooffortheCayley’sformulausingacombinatorialargument.Theapproachcombinestheproblemofgraphicalenumerationwithclassicalproblemsincombinatorialmathematicsandrevealstheessenceoftheproblemofcountingspanningtreeswithbettereffect.

Cayley’sformula;spanningtrees;inclusion-exclusion;induction

2014-09-24

2015-02-02

國家自然科學基金項目(NSFC11301440 )；福建省教育廳科技項目(JB13155)；廈門理工學院科研基金項目(XKJJ201106)

鄭藝容 (1979- )，男，講師，碩士，研究方向為組合圖論．E-mail:yrzheng@xmut.edu.cn

O157A

1673-4432(2015)01-0095-03