Cayley-Formel

Die Cayley-Formel (benannt nach Arthur Cayley), manchmal auch Satz von Cayley genannt, ist ein Satz aus der abzählenden Kombinatorik. Er besagt, dass es verschiedene bezeichnete Bäume mit Knoten gibt.

Alle bezeichneten Bäume der Größen 2,3 und 4.
Alle 16 aufspannenden Bäume des vollständigen Graphen mit 4 Knoten.

Formulierungen

  • Es gibt verschiedene bezeichnete Bäume mit Knoten.
  • Der bezeichnete vollständige Graph mit Knoten hat verschiedene aufspannende Bäume.

Beweise

Für die Cayley-Formel gibt es unzählige Beweise, einige davon werden von vielen Mathematikern als besonders schön angesehen. Das spiegelt sich unter anderem in der Tatsache, dass der Cayley-Formel ein Kapitel in Das Buch der Beweise gewidmet ist. Dort werden vier verschiedene Beweise präsentiert:

  1. mittels einer Bijektion von der Menge aller Bäume in eine einfacher zu zählende Menge (siehe Prüfer-Code),
  2. unter Verwendung des Satzes von Kirchhoff,
  3. mittels Rekursion,
  4. durch doppeltes Abzählen.

Geschichte

Die Formel wurde zuerst von Carl Wilhelm Borchardt (1860) publiziert. 1889 erweiterte Cayley die Formel und formulierte sie in der Graphenterminologie, weshalb sie seitdem mit seinem Namen verbunden wird.

Auch erwähnenswert ist, d​ass James Joseph Sylvester s​chon (1857) e​in äquivalentes Resultat publizierte.

Literatur

  • Martin Aigner, Günter M. Ziegler: Das Buch der Beweise. Springer-Verlag, 2010, Kapitel 30 – Cayleys Formel für die Anzahl der Bäume, S. 227–233.
  • Borchardt, C.W.: Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung. In: Math. Abh. der Akademie der Wissenschaften zu Berlin. 1860, S. 1–20.
  • A. Cayley: A theorem on trees. In: Quart. J. Math. 23, 1889, S. 376–378.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.