Cayley-formula
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ee/Cayley%27s_formula_2-4.svg/220px-Cayley%27s_formula_2-4.svg.png)
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ő csúcsú számozott fa adható meg. Ez az érték:
Történet
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.
Bizonyítás
Tekintsük az
halmazt, mint a gráf csúcsainak halmazát. Jelöljük -nel a lehetséges fák számát csúcson. Nyilvánvalóan adódik, hogy
- .
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
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 v1, v2, … ,vn-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 wk az a pont, amelynek elhagyásakor vk-t feljegyeztük. Tehát ha meghatározzuk wk-t minden k-ra, akkor már egyértelműen rekonstruálható a fa, hiszen élei pontosan a {wk, vk} párok. A wk-k pedig könnyen meghatározhatók, hiszen w1 a legkisebb olyan szám, ami nem fordul elő v1,v2,…,vn-1 között, általánosan pedig wk az a szám, ami nem fordul elő w1,w2,…,wk-1,vk,…,vn-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
é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 v1,v2,…,vn-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 wi 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 wi-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 Tn,k-val. Nyilvánvaló, hogy az A halmaznak csak az elemszáma számít. Ekkor Tn,1 = Tn. 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 Tn-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
Legyen T0,0= 1 és n > 1 esetén Tn,0= 0. T0,0 = 1 azért szükséges, hogy fennálljon Tn,n = 1. Ekkor
amiből speciálisan:
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:
Legyen i = n - k - i
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:
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 Tn, így az adódik, hogy a lehetséges előállítások száma:
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:
Így (1, 2) alapján adódik a Cayley-formula.
Hivatkozások
- 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