Cayley公式是說(shuō)，一個(gè)完全圖K_n有n^(n-2)棵生成樹(shù)，換句話(huà)說(shuō)n個(gè)節(jié)點(diǎn)的帶標(biāo)號(hào)的無(wú)根樹(shù)有n^(n-2)個(gè)。今天我學(xué)到了Cayley公式的一個(gè)非常簡(jiǎn)單的證明，證明依賴(lài)于Prüfer編碼，它是對(duì)帶標(biāo)號(hào)無(wú)根樹(shù)的一種編碼方式。
給定一棵帶標(biāo)號(hào)的無(wú)根樹(shù)，找出編號(hào)最小的葉子節(jié)點(diǎn)，寫(xiě)下與它相鄰的節(jié)點(diǎn)的編號(hào)，然后刪掉這個(gè)葉子節(jié)點(diǎn)。反復(fù)執(zhí)行這個(gè)操作直到只剩兩個(gè)節(jié)點(diǎn)為止。由于節(jié)點(diǎn)數(shù)n>2的樹(shù)總存在葉子節(jié)點(diǎn)，因此一棵n個(gè)節(jié)點(diǎn)的無(wú)根樹(shù)唯一地對(duì)應(yīng)了一個(gè)長(zhǎng)度為n-2的數(shù)列，數(shù)列中的每個(gè)數(shù)都在1到n的范圍內(nèi)。下面我們只需要說(shuō)明，任何一個(gè)長(zhǎng)為n-2、取值范圍在1到n之間的數(shù)列都唯一地對(duì)應(yīng)了一棵n個(gè)節(jié)點(diǎn)的無(wú)根樹(shù)，這樣我們的帶標(biāo)號(hào)無(wú)根樹(shù)就和Prüfer編碼之間形成一一對(duì)應(yīng)的關(guān)系，Cayley公式便不證自明了。
注意到，如果一個(gè)節(jié)點(diǎn)A不是葉子節(jié)點(diǎn)，那么它至少有兩條邊；但在上述過(guò)程結(jié)束后，整個(gè)圖只剩下一條邊，因此節(jié)點(diǎn)A的至少一個(gè)相鄰節(jié)點(diǎn)被去掉過(guò)，節(jié)點(diǎn)A的編號(hào)將會(huì)在這棵樹(shù)對(duì)應(yīng)的Prüfer編碼中出現(xiàn)。反過(guò)來(lái)，在Prüfer編碼中出現(xiàn)過(guò)的數(shù)字顯然不可能是這棵樹(shù)（初始時(shí)）的葉子。于是我們看到，沒(méi)有在Prüfer編碼中出現(xiàn)過(guò)的數(shù)字恰好就是這棵樹(shù)（初始時(shí)）的葉子節(jié)點(diǎn)。找出沒(méi)有出現(xiàn)過(guò)的數(shù)字中最小的那一個(gè)（比如④），它就是與Prüfer編碼中第一個(gè)數(shù)所標(biāo)識(shí)的節(jié)點(diǎn)（比如③）相鄰的葉子。接下來(lái)，我們遞歸地考慮后面n-3位編碼（別忘了編碼總長(zhǎng)是n-2）：找出除④以外不在后n-3位編碼中的最小的數(shù)（左圖的例子中是⑦），將它連接到整個(gè)編碼的第2個(gè)數(shù)所對(duì)應(yīng)的節(jié)點(diǎn)上（例子中還是③）。再接下來(lái)，找出除④和⑦以外后n-4位編碼中最小的不被包含的數(shù)，做同樣的處理……依次把③⑧②⑤⑥與編碼中第3、4、5、6、7位所表示的節(jié)點(diǎn)相連。最后，我們還有①和⑨沒(méi)處理過(guò)，直接把它們倆連接起來(lái)就行了。由于沒(méi)處理過(guò)的節(jié)點(diǎn)數(shù)總比剩下的編碼長(zhǎng)度大2，因此我們總能找到一個(gè)最小的沒(méi)在剩余編碼中出現(xiàn)的數(shù)，算法總能進(jìn)行下去。這樣，任何一個(gè)Prüfer編碼都唯一地對(duì)應(yīng)了一棵無(wú)根樹(shù)，有多少個(gè)n-2位的Prüfer編碼就有多少個(gè)帶標(biāo)號(hào)的無(wú)根樹(shù)。
一個(gè)有趣的推廣是，n個(gè)節(jié)點(diǎn)的度依次為D1, D2, ..., Dn的無(wú)根樹(shù)共有(n-2)! / [ (D1-1)!(D2-1)!..(Dn-1)! ]個(gè)，因?yàn)榇藭r(shí)Prüfer編碼中的數(shù)字i恰好出現(xiàn)Di-1次。