Wikipedista:LukasKub/Cayleyho vzorec

Všechny možné stromy na 2,3 a 4 označených vrcholech: $2^{2-2}=1$ strom se 2 vrcholy, $3^{3-2}=3$ stromy se 3 vrcholy a $4^{4-2}=16$ stromů se 4 vrcholy.

Cayleyho vzorec, pojmenován podle Arthura Cayleyho, uvádí, že pro každé kladné celé číslo $n$, je počet stromů na $n$ vrcholech $n^{n-2}$ .

Důkaz

Je známo několik důkazů Cayleyova vzorce. Jeden klasický důkaz vzorce používá Kirchhoffovu větu, vzorec pro počet koster v libovolném grafu pomocí determinantu matice daného grafu ve správné reprezentaci. Důkaz na základě Prüferových sekvencí převede strom na n vrcholech na sekvenci o n-2 číslech. Další převáděcí důkaz, od André Joyala, nachází transformaci mezi kostrami se dvěma odlišnými vrcholy a maximálními orientivanými pseudolesy . Důkaz počítáním dvěma způsoby od Jima Pitmana počítá počet různých sekvencí orientovaných hran, které lze přidat do prázdného grafu na n vrcholech, aby se z něj vytvořil zakořeněný strom.

Dějiny

Vzorec byl poprvé objeven Carlem Wilhelmem Borchardtem v roce 1860 a dokázán za pomocí determinantu . V krátké poznámce z roku 1889 Cayley rozšířil vzorec v několika směrech tím, že vzal v úvahu stupně vrcholů. Ačkoli odkazoval na Borchardtův původní článek, název „Cayleyův vzorec“ se stal v oboru standardem.

Další vlastnosti

Cayleyův vzorec také určuje počet zakořeněných lesů na n vrcholech, konkrétně (n + 1)^{n − 1} . Každý zakořeněný les lze přeměnit na strom s jedním vrcholem navíc, a to přidáním vrcholu, který se propojí všemi kořeny stromů v daném lese.

Reference

  [[Kategorie:Category:Teorie grafů]]