Formula lui Cayley

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
Lista completă a arborilor cu 2, 3 sau 4 noduri etichetate : 22 - 2 = 1 arbori cu două noduri, 33 - 2 = 3 arbori cu trei noduri și 44 - 2 = 16 arbori cu patru noduri.

În matematică, Formula lui Cayley este un rezultat în teoria grafurilor, numit după Arthur Cayley. Formula stabilește că, pentru orice număr natural n, numărul de arbori etichetați este de nn - 2.

Sunt cunoscute multe demonstrații ale formulei lui Cayley, cum ar fi cu ajutorul teoremei lui Kirchhoff pentru arbori de matrici, prin șiruri Prüfer sau prin dublă numărare.

Numărare prin calculul cu specii[modificare | modificare sursă]

După punctarea a două noduri (roșu și albastru) într-un arbore, toate nodurile (roz) de pe unicul traseu liniar care le unește devin la rândul lor determinate producând o vertebră, sau un Lin(Ars).
O mulțime de două cicluri a câte trei și două arborescențe. Orice endo-funcție poate fi reprezentată astfel, urmărind șirurile x, F(x), F(F(x)),.... care afluesc, convergând înspre cicluri.

Să notăm cu Mn numărul de arbori etichetați pentru un n dat. Dacă într-un arbore se marchează două noduri, numărul de realizări ale noii specii „arbore cu două noduri marcate” (numită și vertebră) este de n.n.Mn.

Între oricare două noduri ale unui arbore există un unic drum. Prin marcarea a două noduri (ele pot coincide) se marchează, implicit, și toate nodurile intermediare. Astfel, vertebra poate fi descrisă ca un șir de noduri marcate, în care fiecare nod este rădăcina unui arborescențe (arbore cu rădăcină).

| Vertebră | = n.n.Mn,
Vertebră = Lin (Ars)

Mai departe, specia Lin(Ars) este echipotentă cu specia Perm(Ars) pentru că există tot atâtea ordini lineare câte permutări definite pe o aceeași mulțime.

Lin (Ars) ≈ Perm(Ars)

Însă Perm(Ars) nu este altceva decât specia funcțiilor definite de la o mulțime la ea însăși, Ens(Cyc(Ars))

Perm(Ars) = [Ens(Cyc)]°(Ars) = Ens(Cyc(Ars)) = End,

a cărei număr de realizări este nn :

| End | = nn

În concluzie, Mn = nn-2.

Istoric[modificare | modificare sursă]

Formula a fost descoperită prima dată de către Carl Wilhelm Borchardt in 1860 și demonstrată cu ajurotul determinanților. Cu toate acestea, numele de formula lui Cayley a rămas înrădăcinat în domeniu.

Bibliografie[modificare | modificare sursă]