E104 - Institut für Diskrete Mathematik und Geometrie
-
Date (published):
2022
-
Number of Pages:
100
-
Keywords:
matrix tree theorem; hypergraphs; semirings; spanning trees
en
Abstract:
Das Ziel dieser Masterarbeit ist es, einen tieferen Einblick in verschiedene Aspekte des Matrix-Baum-Theorems zu vermitteln. Es wird eine Einführung in G. R. Kirchhoffs Matrix-Baum-Theorem geboten, wofür verschiedene Beweise präsentiert werden: der heute kanonische Beweis via die Cauchy-Binet Formel, G. R. Kirchhoffs ursprünglicher Zugang aus 1847, ein weiterer via das Inklusion-Exklusion Prinzip, ein sehr ähnlicher Beweis mit einer sogenannten Vorzeichen-umkehrenden Involution, um Subgraphen mit Zyklen zu entfernen, eine weitere Methode via Löschen und Zusammenziehen von Kanten, und ein probabilistischer Beweis mit Irrfahrten. Das Kapitel schließt mit Erwähnungen weiterer ähnlicher Sätze, unter anderem dem Matrix-Baum-Theorem auf Kanten, dem Matrix-Baum-Theorem mit der vorzeichenlosen Laplace’schen Matrix, und dem Markov-Ketten-Baum-Satz. Die zuvor vorgestellten Methoden werden dann benutzt, um das Matrix-Baum-Theorem auf Semiringen und für Hypergraphen zu beweisen. Um diese Verallgemeinerungen zu beschreiben, werden die symmetrische Erweiterung, Bideterminanten, arboreale Hypergraphen, Hyperbäume und die Pfaff’sche Determinante definiert.
de
The goal of this thesis is to provide a deeper insight into the inner workings of the matrix tree theorem. For this it introduces G. R. Kirchhoff’s matrix tree theorem and shows different approaches to prove it: the nowadays canonical proof via the Cauchy–Binet formula, G. R. Kirchhoff’s original approach used in 1847, one employing the inclusion–exclusion principle, a similar one applying a sign-reversing involution to remove subgraphs containing cycles, another using deletion–contraction via induction, and a probabilistic proof via random walks. The chapter closes with mentions of similar theorems, including the matrix tree theorem on edges, the matrix tree theorem using the signless Laplacian, and the Markov chain tree theorem. The previously presented methods are then applied to prove the matrix tree theorem on semirings and for hypergraphs. To formulate these generalisations, the symmetric extension of semirings, bideterminants, arboreal hypergraphs, hypertrees, and the Pfaffian are defined.
en
Additional information:
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers