Cayleys sats om antal träd

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 9 januari 2022; verifiering kräver 1 redigering .

Cayleys antal träd -sats är en sats som säger att antalet träd med numrerade hörn är . $n$ $n^{{n-2}}$

Historik

Teoremet är uppkallat efter Arthur Cayley , som bevisade det 1889. [1] Cayley själv medgav att samma påstående hade bevisats tidigare av Carl Borchard och i en likvärdig formulering ännu tidigare i ett papper från 1857 av James Joseph Sylvester . [2]

I sin uppsats bevisar Cayley i huvudsak ett mer allmänt uttalande. Om du öppnar parenteserna för uttrycket

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

då kommer koefficienten för formens monomial att vara lika med antalet träd vars grader av hörn är lika med graderna av variablerna för den givna termen: . $x_{1}^{d_{1}}\cdots x_{n}^{d_{n}}$ ${\displaystyle d_{1},\dots ,d_{n))$

Cayley utvecklar fallet och konstaterar att beviset är lätt att generalisera. $n=6$

Formuleringar

Två likvärdiga formuleringar:

Antalet olika träd på hörnen, numrerade från till är lika med . $n$ $ett$ $n$ $n^{{n-2}}$

Antalet spännande träd i hela grafen är . $K_n$ $n^{{n-2}}$

Relaterade uttalanden

Antalet träd på de numrerade hörnen visar sig också vara lika med antalet nedbrytningar av -cykeln till produkten av transponeringen . $n$ $n$ $(1\dots n)$ $n-1$

Antalet träd på numrerade hörn visar sig också vara lika med antalet (lämpligt normaliserade) gradpolynom med givna kritiska värden i allmän position. $n$ $n$ $n-1$
- Slutligen är det sistnämnda ett specialfall av den topologiska klassificeringen av grenade beläggningar av Riemann-sfären - att räkna antalet träd visar sig därför vara ett specialfall av att beräkna Hurwitz-talen som motsvarar fallet med en täckande yta av släktet 0.

Om bevis

Cayleys formel följer omedelbart av egenskaperna hos Prufer-koden , ett sätt att unikt koda ett n- vertexmärkt träd genom en ordnad sekvens av dess vertexnummer. $n$ $n-2$

Cayleys formel är också lätt härledd från matristrädsatsen .

Ett av bevisen bygger på följande relation ${\displaystyle a(x)=x\cdot e^{a(x)))$

till den exponentiella genererande funktionen

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

där anger antalet rotade träd vid de givna hörnen. Enligt Lagrangesatsen om inversion av serier följer det av denna relation att . Det senare antyder Cayleys formel eftersom det för varje spännande träd finns exakta sätt att välja en rotvertex. [3]

en

n

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

n

Variationer och generaliseringar

Antalet sätt att länka en graf som består av frånkopplade komponenter, var och en med en vertexstorlek, är $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}$ Här är det totala antalet grafens hörn. ${\displaystyle n=x_{1}+x_{2}+\dots +x_{m))$ Om varje komponent består av en vertex , då , och formeln ger det ursprungliga Cayley-talet . $(x_{i}=1)$ $n=m$ $n^{{n-2}}$

Antalet spännande träd i en komplett tvådelad graf är $K_{{m,n}}$ $T(K_{m,n})=m^{n-1}\cdot n^{m-1}.$

Matristrädsatsen ger ett uttryck för antalet spännande träd i en graf som determinant för grafens Laplacian (Kirchhoff-matris).

Anteckningar

↑ Cayley A. En sats om träd. Quart. 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. Uppräkning av grafer. - Världen, 1977.

Litteratur

Yu. M. Burman, kursanteckningar " Kritiska värden för polynom ": [1] , [2] , [3] , [4] .
M. E. Kazaryan, anteckningar om kursen " Geometri, topologi och kombinatorik av grenade täckningar av sfären ".
A. Cayley. En sats om träd (neopr.) // Quart. J Math. - 1889. - T. 23 . - S. 376-378 .
T. Ekedahl, S. Lando, M. Shapiro, A. Vainshtein. Hurwitz-tal och Hodge-integraler .