Ferienakademie 1999
Kurs 2: Bäume - Algorithmik und Kombinatorik

Marc Wagner
Cayleys Formel - Drei Beweise durch geschicktes Zählen

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 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.

Marc Wagner
Kombinatorischer Beweis des Matrix-Tree-Theorems mittels Involutionsprinzip

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 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 von der Anzahl der Bäume und Knoten hergeleitet und damit ein weiters mal Cayleys Formel bewiesen.