<div class="csl-bib-body">
<div class="csl-entry">Holzer, F. (2022). <i>Matrix tree theorems</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2022.99062</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2022.99062
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/20424
-
dc.description
Abweichender Titel nach Übersetzung der Verfasserin/des Verfassers
-
dc.description.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
dc.description.abstract
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
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
matrix tree theorem
en
dc.subject
hypergraphs
en
dc.subject
semirings
en
dc.subject
spanning trees
en
dc.title
Matrix tree theorems
en
dc.title.alternative
Matrix-Baum Theoreme
de
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2022.99062
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Fabian Holzer
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E104 - Institut für Diskrete Mathematik und Geometrie
-
dc.type.qualificationlevel
Diploma
-
dc.identifier.libraryid
AC16556012
-
dc.description.numberOfPages
100
-
dc.thesistype
Diplomarbeit
de
dc.thesistype
Diploma Thesis
en
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
item.languageiso639-1
en
-
item.fulltext
with Fulltext
-
item.openaccessfulltext
Open Access
-
item.mimetype
application/pdf
-
item.openairetype
master thesis
-
item.grantfulltext
open
-
item.openairecristype
http://purl.org/coar/resource_type/c_bdcc
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E104 - Institut für Diskrete Mathematik und Geometrie