Cayley-formula

A Cayley-formula egy gráfelméleti leszámlálási tétel, melyet Arthur Cayley-ről neveztek el. Meghatározza, hogy hány különböző $n$ csúcsú számozott fa adható meg. Ez az érték:

n^{n-2}\,.

Arthur Cayley 1889-ben publikálta cikkét, mely tartalmazza ezt a formulát. A tételt azonban már korábban bebizonyították. 1860-ban Carl W. Borchardt (akinek elsőbbségét maga Cayley is elismerte), és még ennél is korábban, 1857-ben, James Joseph Sylvester közölt egy ezzel egyenértékű eredményt. Cayley cikkében az újdonság a gráfelmélet alkalmazása volt, és a tétel azóta is az ő nevéhez fűződik.

Tekintsük az

N=\{1,2,3,4...,n\}\,

halmazt, mint a gráf csúcsainak halmazát. Jelöljük $T_{n}$ -nel a lehetséges fák számát $n$ csúcson. Nyilvánvalóan adódik, hogy

T_{1}=1,\quad T_{2}=1,\quad T_{3}=3,\quad T_{4}=16\,

.

Hangsúlyozzuk, hogy számozott fákat vizsgálunk, vagyis 3 csúcspontú fa (gráf-izomorfizmus erejéig) csak 1 van, míg a számozott esetben a másodfokú pontot háromféleképpen választhatjuk meg, így ott 3 különböző megoldás létezik.

1. bizonyítás

A tétel legismertebb bizonyítása a Prüfer-kód felhasználásával történik. Mivel ez kölcsönösen egyértelmű (bijektív) megfeleltetést ad a számozott fák száma és az n - 2 hosszú számsorozatok között (melyeknek minden eleme 1 és n közti egész), így nyilvánvalóan adódik az állítás, vagyis

T_{n}=n^{n-2}\,.

Lemma. A számozott fák és a Prüfer-kódok között kölcsönösen egyértelmű megfeleltetés létezik.

Bizonyítás.

Nyilvánvaló, hogy minden fához egyértelműen tartozik egy Prüfer-kód. Azt kell még belátni, hogy minden Prüfer-kódhoz (legyen ez v₁, v₂, … ,v_n-2) is egyértelműen létezik egy fa, amit leír. Abból, hogy hány számból áll a kód azonnal kapjuk n értékét, hiszen a sorozat n - 2 hosszú. Legyen w_k az a pont, amelynek elhagyásakor v_k-t feljegyeztük. Tehát ha meghatározzuk w_k-t minden k-ra, akkor már egyértelműen rekonstruálható a fa, hiszen élei pontosan a {w_k, v_k} párok. A w_k-k pedig könnyen meghatározhatók, hiszen w₁ a legkisebb olyan szám, ami nem fordul elő v₁,v₂,…,v_n-1 között, általánosan pedig w_k az a szám, ami nem fordul elő w₁,w₂,…,w_k-1,v_k,…,v_n-1 számok között. Ilyen szám mindig létezik, hiszen ha mind különböző lenne, akkor is csak n - 1 -et zártunk ki az n-ből. Megkaptuk tehát a

\{v_{1},w_{1}\},\quad \{v_{2},w_{2}\},...,\{v_{n-1},w_{n-1}\}\,

éleket. Be kell látnunk, hogy ezek fát határoznak meg (tehát körmentes gráfot), és ekkor a gráf Prüfer-kódja éppen v₁,v₂,…,v_n-1. Tegyük fel indirekt módon, hogy van a gráfban kör. A Prüfer-kód „visszafejtése” során minden egyes újabb w_i felírásakor egy újabb pontot, és egy újabb élet kapunk meg. Kell lennie egy olyan lépésnek, amikor a kör utolsó élét húzzuk be, de ekkor egy olyan w_i-t kéne felírnunk, amely már korábban szerepelt, ez azonban a fenti eljárásban nem lehetséges. Tehát minden n - 1 elemű sorozathoz, amelyben az első n - 2 elem mindegyike lehet {1,2,…,n} és az utolsó elem n, tartozik egy fa, és különböző sorozatokhoz különböző fa tartozik.

2. bizonyítás

A következő ötlet Riordantól és Rényitől származik. A bizonyítás alapgondolata egy olyan rekurzió megadása, melynek segítségével könnyen megoldható a probléma. A megfelelő rekurzió megtalálásához egy bonyolultabb probléma vizsgálatán keresztül juthatunk el. Legyen A az N = {1,2,3,…,n} csúcsok egy tetszőleges k elemű részhalmaza. Tekintsük az n csúcson megadható k darab fát tartalmazó (számozott) erdők számát, ahol az A halmaz elemei különböző fákban vannak. Jelöljük ezt T_n,k-val. Nyilvánvaló, hogy az A halmaznak csak az elemszáma számít. Ekkor T_n,1 = T_n. Tekintsünk egy F erdőt az A = {1,2,3,…,k} halmazzal, és ennek 1 csúcsát, melynek i db szomszédja van. Amennyiben ezt a csúcsot elhagyjuk, úgy az i db szomszéd és a 2,3,…,k pontok együtt T_n-1,k-1+i darab erdőt adnak. Mivel i-t tetszőlegesen választhatjuk ki aközül az n-k csúcs közül, mely az 1,2,…,k csúcsoktól különbözik, így n ≥ k ≥ 1 -re az következik, hogy

T_{n,k}=\sum _{i=0}^{n-k}{\binom {n-k}{i}}T_{n-1,k-1+i}\qquad \qquad (1)\,.

Legyen T_0,0= 1 és n > 1 esetén T_n,0= 0. T_0,0 = 1 azért szükséges, hogy fennálljon T_n,n = 1. Ekkor

T_{n,k}=kn^{n-k-1}\,

amiből speciálisan:

T_{n,1}=n^{n-2}\,.

Bizonyítás. A bizonyítás teljes indukcióval történik. A rekurziót (1)-et és az állítást felhasználva kapjuk:

T_{n,k}=\sum _{i=0}^{n-k}{\binom {n-k}{i}}T_{n-1,k-1+i}\,

T_{n,k}=\sum _{i=0}^{n-k}{\binom {n-k}{i}}(k-1+i)(n-1)^{n-1-k-i}\,

Legyen i = n - k - i

T_{n,k}=\sum _{i=0}^{n-k}{\binom {n-k}{i}}(n-1-i)(n-1)^{i-1}\,

T_{n,k}=\sum _{i=0}^{n-k}{\binom {n-k}{i}}(n-1)^{i}-\sum _{i=1}^{n-k}{\binom {n-k}{i}}i(n-1)^{i-1}\,

T_{n,k}=n^{n-k}-(n-k)\sum _{i=1}^{n-k}{\binom {n-1-k}{i-1}}(n-1)^{i-1}\,

T_{n,k}=n^{n-k}-(n-k)\sum _{i=0}^{n-1-k}{\binom {n-1-k}{i}}(n-1)^{i}\,

T_{n,k}=n^{n-k}-(n-k)n^{n-1-k}=kn^{n-1-k}.\,

Ezzel bizonyítottuk az állítást és speciálisan a Cayley-formulát.

3. bizonyítás

A következő bizonyítás Jim Pitmantől származik, a kettős leszámlálás technikáját alkalmazza. Azt számoljuk össze kétféleképpen, hogy egy üres gráfból kiindulva, élek hozzáadásával, hányféleképpen lehet előállítani n pontú, címkézett fenyőt. Fenyő alatt olyan irányított fát értünk, ahol egy csúcsból (ún. gyökér) minden más pont elérhető. Jelöljük az n pontú fenyők előállításainak számát a következővel:

CP_{n}\,

Megj.: C mint Create, P mint Pinewood, azaz fenyő angolul.

Első előállítási mód: Kiindulunk egy n pontú fából és ezt élenként, egyesével "beirányítjuk".

Kérdés, hogy egy adott fát hányféle sorrendben tudjuk úgy beirányítani, hogy a végeredmény egy fenyő legyen? A fenyő gyökerét nyilván n-féleképpen tudjuk kiválasztani. Miután a gyökeret rögzítettük, az irányítás egyértelmű, így csak azt kell megadni, hogy milyen sorrendben vesszük az n-1 élt. Ezeket nyilván (n-1)!-féleképpen tudjuk sorba rendezni. Vagyis egy tetszőleges n pontú irányítatlan fát n*(n-1)!=n!-féle sorrendben tudjuk beirányítani.

Mivel a címkézett fák száma T_n, így az adódik, hogy a lehetséges előállítások száma:

CP_{n}=T_{n}n!\qquad \qquad (1)\,

Megj.: Egy "beirányítás" értelemszerűen úgy felel meg egy előállításnak, hogy minden lépésben azt az élet adjuk hozzá a gráfhoz, amit éppen beirányítunk. Azt kell még meggondolni (relatíve triviális), hogy ez kölcsönösen egyértelmű megfeleltetés és így a beirányítások száma azonos az előállítások számával.

Második előállítási mód: Kiindulunk az üres gráfból és egyesével adjuk hozzá az éleket.

Nézzük meg azt először, hogy a k-1. él hozzáadása után, a következő k. él kiválasztására hányféle lehetőség van. Ha az n pontú üres gráfhoz már hozzáadtunk k-1 (irányított) élet, akkor a gráf n-(k-1) darab fenyőből áll (ez pl. indukcióval látható be, ötlet: minden egyes élbehúzás 1-gyel csökkenti az összefüggő komponensek számát). Innen kiindulva a kezdőpontot tetszőlegesen választhatjuk (n db variáció), a végpont pedig az n-(k-1) db fenyő gyökere lehet, kivéve azt a fenyőt, ahol a választott kezdőpont van (n-k variáció). Így összesen n(n-k)-féleképpen tudjuk a k. élet kiválasztani.

Mivel összesen n-1 élet adunk az üres gráfhoz, így ha összeszorozzuk a kombinációkat, az adódik, hogy a lehetséges előállítások száma: n(n-1)*n(n-2)*…*n(n-k)*…*n(n-(n-1)), azaz:

CP_{n}=n^{n-1}(n-1)!=n^{n-2}n!\qquad \qquad (2)\,

Így (1, 2) alapján adódik a Cayley-formula.

Martin Aigner, Günter M. Ziegler: Bizonyítások a könyvből , Typotex, Budapest, 2004, 182-189. old.
Katona Gyula Y., Recski András, Szabó Csaba: A számítástudomány alapjai , Typotex, Budapest, 2006, 26. old.
Bozó Brigitta: Címkézett és címkézetlen fák leszámlálása, ELTE TTK Szakdolgozat, 2010
Mark Haimann: Notes on the Matrix-Tree theorem and Cayley's tree enumerator, 2010