Teorema numărului de arbori a lui Cayley

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 9 ianuarie 2022; verificarea necesită 1 editare .

Teorema numărului de arbori a lui Cayley este o teoremă care afirmă că numărul de arbori cu vârfuri numerotate este . $n$ $n^{{n-2}}$

Istorie

Teorema poartă numele lui Arthur Cayley , care a demonstrat-o în 1889. [1] Cayley însuși a admis că aceeași afirmație fusese dovedită mai devreme de Carl Borchard și într-o formulare echivalentă chiar mai devreme într-o lucrare din 1857 a lui James Joseph Sylvester . [2]

În lucrarea sa, Cayley demonstrează în esență o afirmație mai generală. Dacă deschideți parantezele expresiei

{(x_{1}+\dots +x_{n})}^{n-2}\cdot (x_{1}\cdot x_{2}\cdot \ldots \cdot x_{n}),

atunci coeficientul monomului formei va fi egal cu numărul de arbori ale căror grade de vârfuri sunt egale cu gradele variabilelor termenului dat: . $x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}$ $d_{1},\dots,d_{n)$

Cayley detaliază cazul și afirmă că dovada este ușor generalizabilă. $n=6$

Formulări

Două formulări echivalente:

Numărul de arbori diferiți de pe vârfuri, numerotați de la până la este egal cu . $n$ $unu$ $n$ $n^{{n-2}}$

Numărul de arbori care se întind în graficul complet este . $K_n$ $n^{{n-2}}$

Declarații înrudite

Numărul de arbori de pe vârfurile numerotate se dovedește, de asemenea, a fi egal cu numărul de descompunere ale ciclului în produsul transpoziției . $n$ $n$ $(1\dots n)$ $n-1$

Numărul de arbori de pe vârfuri numerotate se dovedește, de asemenea, a fi egal cu numărul de polinoame de grade (normalizate corespunzător) cu valori critice date în poziție generală. $n$ $n$ $n-1$
- În sfârșit, acesta din urmă este un caz special de clasificare topologică a acoperirilor ramificate a sferei Riemann - astfel, numărarea numărului de arbori se dovedește a fi un caz special de calcul al numerelor Hurwitz corespunzătoare cazului unei suprafețe de acoperire. din genul 0.

Despre dovezi

Formula lui Cayley decurge imediat din proprietățile codului Prufer , o modalitate de a codifica unic un arbore etichetat cu n-vertex printr-o succesiune ordonată a numerelor sale de vârf. $n$ $n-2$

Formula lui Cayley este, de asemenea, ușor derivată din teorema arborelui matrice .

Una dintre dovezi se bazează pe următoarea relație $a(x)=x\cdot e^{a(x))$

la funcţia generatoare exponenţială

a(x)=a_{1}\cdot x+{\tfrac {1}{2}}\cdot a_{2}\cdot x^{2}+\dots +{\tfrac {1}{n !}}\cdot a_{n}\cdot x^{n}+\dots

unde denotă numărul de arbori înrădăcinați la vârfurile date. Conform teoremei Lagrange asupra inversării seriilor rezultă din această relaţie că . Acesta din urmă implică formula lui Cayley, deoarece pentru fiecare arbore care se întinde există exact modalități de a alege un vârf de rădăcină. [3]

un

n

a_{n}=n^{n-1)

n

Variații și generalizări

Numărul de moduri de a lega un grafic format din componente deconectate, fiecare cu o dimensiune a vârfurilor, este $m$ $x_{i}$ $T[x_{m}]=x_{1}\cdot x_{2}\dots x_{m}\cdot (x_{1}+x_{2}+\dots +x_{m})^{ m-2}=[x_{m}]!\ n^{m-2}$ Iată numărul total de vârfuri ale graficului. $n=x_{1}+x_{2}+\dots +x_{m)$ Dacă fiecare componentă constă dintr-un vârf , atunci , iar formula dă numărul original Cayley . $(x_{i}=1)$ $n=m$ $n^{{n-2}}$

Numărul de arbori care se întind dintr-un grafic bipartit complet este $K_{{m,n}}$ $T(K_{m,n})=m^{n-1}\cdot n^{m-1}.$

Teorema arborelui matricei oferă o expresie pentru numărul de arbori spanning ai unui grafic ca determinant al Laplacianului (matricea Kirchhoff) al graficului.

Note

↑ Cayley A. O teoremă asupra copacilor. Quart. J. Pure Appl. Math. 23 (1889), 376-378; Lucrări de matematică adunate, vol. 13, Cambridge University Press, 1897 , 26–28.
↑ Biggs NL, Lloyd EK, Wilson RJ Graph Theory 1736-1936. Clarendon Press, Oxford, 1976.
↑ Harari F., Palmer E. Enumeration of graphs. - Lumea, 1977.

Literatură

Yu. M. Burman, note de curs „ Valorile critice ale polinoamelor ”: [1] , [2] , [3] , [4] .
M. E. Kazaryan, note ale cursului „ Geometria, topologia și combinatoria acoperirilor ramificate ale sferei ”.
A. Cayley. O teoremă asupra copacilor (neopr.) // Quart. J Math. - 1889. - T. 23 . - S. 376-378 .
T. Ekedahl, S. Lando, M. Shapiro, A. Vainshtein. Numerele Hurwitz și integralele Hodge .