Cayley fák száma tétel

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. január 9-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

Cayley fák száma tétele egy olyan tétel, amely szerint a számozott csúcsú fák száma . $n$ $n^{{n-2}}$

Történelem

A tétel Arthur Cayley nevéhez fűződik , aki 1889-ben bebizonyította. [1] Cayley maga is elismerte, hogy ugyanezt az állítást korábban Carl Borchard is bebizonyította, és egyenértékű megfogalmazásban még korábban James Joseph Sylvester 1857 -es tanulmányában. [2]

Írásában Cayley lényegében egy általánosabb kijelentést bizonyít. Ha megnyitja a kifejezés zárójelét

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

akkor az alak monomiális együtthatója egyenlő lesz azon fák számával, amelyek csúcsfoka megegyezik az adott tag változóinak fokszámaival: . $x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}$ ${\displaystyle d_{1},\dots ,d_{n))$

Cayley kifejti az esetet , és kijelenti, hogy a bizonyíték könnyen általánosítható. $n=6$

Formulációk

Két egyenértékű készítmény:

A különböző fák száma a csúcsokon, től ig számozva egyenlő . $n$ $egy$ $n$ $n^{{n-2}}$

A feszítőfák száma a teljes grafikonban . $K_n$ $n^{{n-2}}$

Kapcsolódó nyilatkozatok

A számozott csúcsokon lévő fák száma is megegyezik a -ciklus transzpozíció szorzatára történő dekompozícióinak számával . $n$ $n$ $(1\ponts n)$ $n-1$

A számozott csúcsokon lévő fák száma megegyezik a (megfelelően normalizált) fokpolinomok számával , amelyek adott kritikus értékkel rendelkeznek általános helyzetben. $n$ $n$ $n-1$
- Végül ez utóbbi a
Riemann-gömb elágazó burkolatai topológiai osztályozásának speciális esete - így a fák számának számlálása a burkolófelület esetének megfelelő Hurwitz-számok kiszámításának speciális esete. 0 nemzetségből .

A bizonyítékokról

A Cayley-képlet közvetlenül a Prufer-kód tulajdonságaiból következik , egy módja annak, hogy egyedileg kódoljunk egy n -csúcsot tartalmazó fát a csúcsszámok rendezett sorozatával . $n$ $n-2$

A Cayley-képlet is könnyen levezethető a mátrixfa tételből .

Az egyik bizonyítás a következő összefüggésen alapul ${\displaystyle a(x)=x\cdot e^{a(x)))$

az exponenciális generáló függvényhez

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}+\pontok

ahol a gyökeres fák számát jelöli az adott csúcson. A sorozatok megfordítására vonatkozó Lagrange-tétel szerint ebből az összefüggésből az következik, hogy . Ez utóbbi magában foglalja a Cayley-képletet, mivel minden feszítőfához pontosan megvan a lehetőség a gyökércsúcs kiválasztására. [3]

a_n

n

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

n

Változatok és általánosítások

A szétválasztott összetevőkből álló gráf összekapcsolásának módjai, amelyek mindegyike csúcsmérettel rendelkezik $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}$ Itt látható a gráf csúcsainak teljes száma. ${\displaystyle n=x_{1}+x_{2}+\pontok +x_{m))$ Ha minden komponens egy csúcsból áll , akkor , és a képlet megadja az eredeti Cayley-számot . $(x_{i}=1)$ $n=m$ $n^{{n-2}}$

A feszítőfák száma egy teljes bipartit gráfban a $K_{{m,n}}$ $T(K_{m,n})=m^{n-1}\cdot n^{m-1}.$

A mátrixfa tétel a gráf laplaci (Kirchhoff-mátrixa) determinánsaként egy gráf feszítőfáinak számát adja meg.

Jegyzetek

↑ Cayley A. Tétel a fákon. 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. Grafikonok felsorolása. - Világ, 1977.

Irodalom

Yu. M. Burman, természetesen jegyzetek " A polinomok kritikus értékei ": [1] , [2] , [3] , [4] .
M. E. Kazaryan, „ A gömb elágazó burkolatainak geometriája, topológiája és kombinatorikája ” kurzus jegyzetei .
A. Cayley. Tétel a fákról (neopr.) // Quart. J Math. - 1889. - T. 23 . - S. 376-378 .
T. Ekedahl, S. Lando, M. Shapiro, A. Vainshtein. Hurwitz-számok és Hodge-integrálok .