生成樹(shù)的計(jì)數(shù)

鄭藝容，周　雪

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

生成樹(shù)的計(jì)數(shù)

鄭藝容1,2，周雪2

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

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

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

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

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

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

1　預(yù)備知識(shí)

首先介紹一些基本概念和結(jié)論.容斥原理是組合數(shù)學(xué)中一個(gè)非常重要的定理，其內(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ù)容斥原理、對(duì)稱(chēng)性及引理1可得：

特別地，當(dāng)p=n-2時(shí)可得以下推論：

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

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

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

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

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

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

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

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

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

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

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

3　小結(jié)

Cayley’s 公式是圖計(jì)數(shù)中的經(jīng)典公式，已有很多不同的證明方法，本文利用由容斥原理得到的組合恒等式并借助數(shù)學(xué)歸納法給出Cayley’s 公式的又一簡(jiǎn)單證明.接下來(lái)可進(jìn)一步研究Cayley’s 公式的不同證明方法，特別是能將圖的其它經(jīng)典問(wèn)題與圖的計(jì)數(shù)問(wèn)題聯(lián)系起來(lái)證明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ù)學(xué)[M].廣州：華南理工大學(xué)出版社,2000.

2

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

(責(zé)任編輯曉軍)

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

國(guó)家自然科學(xué)基金項(xiàng)目(NSFC11301440 )；福建省教育廳科技項(xiàng)目(JB13155)；廈門(mén)理工學(xué)院科研基金項(xiàng)目(XKJJ201106)

鄭藝容 (1979- )，男，講師，碩士，研究方向?yàn)榻M合圖論．E-mail:yrzheng@xmut.edu.cn

O157A

1673-4432(2015)01-0095-03