|
Cayleys Formel ist eine der bekanntesten Formeln in der Kombinatorik. Sie
liefert die Anzahl der Labeled Trees (nummerierte Bäume) in Abhängigkeit von
der Anzahl der Knoten. Das zentrale Thema dieses Vortrags ist jedoch weniger
die Formel selbst, sondern vielmehr deren Beweis. Die drei hier gezeigten
Beweise basieren alle auf rekursiven Zählargumenten, denen jedoch völlig
Beweise basieren alle auf rekursiven Zählargumenten, denen jedoch völlig
unterschiedliche Ansätze zugrunde liegen. Es soll dadurch vor allem
demonstriert werden, auf wie viele verschiedene Arten ein derartiges
kombinatorisches Problem bearbeitet werden kann. In diesem Zusammenhang soll
auf zwei weitere Vorträge im Rahmen dieser Ferienakademie hingewiesen werden,
"Bijektion und Codierung" und "Algebraischer Beweis der Cayley
Formel", in denen weitere Beweise von Cayleys Formel präsentiert werden,
denen jedoch in Form von Bijektionen beziehunsweise algebraischen Hilfsmitteln
ganz andere Ansätze zugrunde liegen.
|
|
Kirchhoffs berühmtes Matrix-Tree-Theorem liefert die Anzahl der Spanning Trees
Kirchhoffs berühmtes Matrix-Tree-Theorem liefert die Anzahl der Spanning Trees
(spannende Bäume) in einem zusammenhängenden Graphen mit Hilfe der Determinante
einer speziellen Matrix. Mittlerweile kennt man eine ganze Reihe von Varianten
des Matrix-Tree-Theorems, die unter Zuhilfenahme von Determinaten Aussagen über
des Matrix-Tree-Theorems, die unter Zuhilfenahme von Determinaten Aussagen über
Bäume und Wälder treffen. Eine relativ vielseitig einsetzbare Variante wird im
ersten Teil dieses Vortrags auf kombinatorischem Weg durch eine geschickte
Involution bewiesen. Der zweite Teil des Vortrags beschäftigt sich dann mit
Anwendungen des vorgestellten Matrix-Tree-Theorems. Unter anderem wird eine
Formel für die Anzahl der Planted Forests (gewurzelte Wälder) in Abhängigkeit
Formel für die Anzahl der Planted Forests (gewurzelte Wälder) in Abhängigkeit
von der Anzahl der Bäume und Knoten hergeleitet und damit ein weiters mal
Cayleys Formel bewiesen.
|