Cayleyho věta o počtu stromů

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 9. ledna 2022; ověření vyžaduje 1 úpravu .

Cayleyův teorém o počtu stromů je teorém, který říká, že počet stromů s očíslovanými vrcholy je . $n$ $n^{{n-2}}$

Historie

Věta je pojmenována po Arthuru Cayleym , který ji dokázal v roce 1889. [1] Cayley sám připustil, že stejné tvrzení bylo dokázáno již dříve Carlem Borchardem a v ekvivalentní formulaci ještě dříve v článku Jamese Josepha Sylvestra z roku 1857 . [2]

Cayley ve svém příspěvku v podstatě dokazuje obecnější tvrzení. Pokud otevřete závorky výrazu

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

pak koeficient monomiálu tvaru bude roven počtu stromů, jejichž stupně vrcholů se rovnají stupňům proměnných daného členu: . $x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}$ ${\displaystyle d_{1},\tečky ,d_{n))$

Cayley rozvádí případ a uvádí, že důkaz lze snadno zobecnit. $n=6$

Formulace

Dvě ekvivalentní formulace:

Počet různých stromů ve vrcholech očíslovaných od do se rovná . $n$ $jeden$ $n$ $n^{{n-2}}$

Počet kostrových stromů v kompletním grafu je . $K_n$ $n^{{n-2}}$

Související prohlášení

Počet stromů na očíslovaných vrcholech se také rovná počtu rozkladů -cyklu na součin transpozice . $n$ $n$ $(1\tečky n)$ $n-1$

Počet stromů na číslovaných vrcholech se také rovná počtu (vhodně normalizovaných) polynomů stupňů s danými kritickými hodnotami v obecné poloze. $n$ $n$ $n-1$
- Konečně, toto je speciální případ topologické klasifikace rozvětvených krytin Riemannovy koule - takže počítání počtu stromů se ukazuje jako speciální případ výpočtu Hurwitzových čísel odpovídajících případu krycí plochy. z rodu 0.

O důkazech

Cayleyho vzorec okamžitě vyplývá z vlastností Pruferova kódu , způsobu, jak jedinečně zakódovat n- vertexový strom označený uspořádanou posloupností jeho čísel vrcholů. $n$ $n-2$

Cayleyův vzorec je také snadno odvozen z věty o maticovém stromu .

Jeden z důkazů je založen na následujícím vztahu ${\displaystyle a(x)=x\cdot e^{a(x)))$

na exponenciální generující funkci

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}+\tečky

kde udává počet zakořeněných stromů v daných vrcholech. Podle Lagrangeovy věty o inverzi řad z tohoto vztahu vyplývá, že . To druhé implikuje Cayleyho vzorec, protože pro každý kostru existují přesně způsoby, jak vybrat kořenový vrchol. [3]

a_n

n

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

n

Variace a zobecnění

Počet způsobů, jak propojit graf sestávající z odpojených komponent, z nichž každá má velikost vrcholu, je $m$ $x_{i}$ $T[x_{m}]=x_{1}\cdot x_{2}\tečky x_{m}\cdot (x_{1}+x_{2}+\tečky +x_{m})^{ m-2}=[x_{m}]!\ n^{m-2}$ Zde je celkový počet vrcholů grafu. ${\displaystyle n=x_{1}+x_{2}+\tečky +x_{m))$ Pokud se každá komponenta skládá z jednoho vrcholu , pak a vzorec dává původní Cayleyovo číslo . $(x_{i}=1)$ $n=m$ $n^{{n-2}}$

Počet překlenovacích stromů v kompletním bipartitním grafu je $K_{{m,n}}$ $T(K_{m,n})=m^{n-1}\cdot n^{m-1}.$

Věta o maticovém stromě dává výraz pro počet kostry grafu jako determinantu Laplacianova (Kirchhoffova matice) grafu.

Poznámky

↑ Cayley A. Věta o stromech. Kvart. J. Pure Appl. Math., 23 (1889), 376-378; Collected Mathematical Papers, 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. Výčet grafů. - Svět, 1977.

Literatura

Yu. M. Burman, poznámky ke kurzu " Kritické hodnoty polynomů ": [1] , [2] , [3] , [4] .
M. E. Kazaryan, poznámky z kurzu " Geometrie, topologie a kombinatorika rozvětvených obalů koule ".
A. Cayley. Věta o stromech (neopr.) // Quart. J Math. - 1889. - T. 23 . - S. 376-378 .
T. Ekedahl, S. Lando, M. Shapiro, A. Vainshtein. Hurwitzova čísla a Hodgeovy integrály .