Sep 1999
Kombinatorischer Beweis des Matrix-Tree-Theorems mittels Involutionsprinzip
Talk given at "Ferienakademie 1999", 19 September-1 October 1999, Sarntal, Italy
download: Kirchhoff.ps.gz, Kirchhoff.pdf (handout, 10 pages)
abstract:
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 Determinanten 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 weiteres Mal Cayleys Formel bewiesen.