Cayley-formula

A Wikipédiából, a szabad enciklopédiából
Az ábra azt mutatja, hogy a 2, 3 és 4 csúcspontú, különbőző színű csúcsokkal rendelkező üres gráf a csúcsai összekötésével összesen hányféle faként állítható elő.

A Cayley-formula egy gráfelméleti 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}\,.

Történet[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 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

\{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 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[szerkesztés | forrásszöveg szerkesztése]

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. Amennyiban 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 nk ≥ 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 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

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[szerkesztés | forrásszöveg szerkesztése]

A következő bizonyítás Jim Pitmantől származik, a kettős leszámlálás technikáját alkalmazza [1]. Azt számoljuk össze 2-fé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 Tn, így az adódik, hogy a lehetséges előállítások száma:

CP_n = T_nn!\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.

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]