Detailansicht
Charakterisierung Pfaff’scher Graphen mittels verbotener Teilgraphen
Thomas Glatz
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Betreuer*in
Ilse Fischer
DOI
10.25365/thesis.11585
URN
urn:nbn:at:at-ubw:1-30384.46653.197470-9
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Pfaff’sche Graphen sind genau jene, auf die man Kasteleyns Methode zum Abzählen perfekter Matchings anwenden kann, womit dieses Problem in polynomieller Zeit lösbar ist.
Diese Arbeit soll darlegen, für welche Klassen von Graphen eine einfache und schöne Charakterisierung Pfaff’scher Graphen existiert. Das Problem ergibt sich aus der unhandlichen und nur umständlich zu überprüfenden Definition. Dabei wird insbesondere die Charakterisierung mittels verbotener Teilgraphen im Mittelpunkt stehen. Die Idee ist, eine Liste von (möglichst wenigen) Graphen anzugeben, deren “nicht-enthalten-Sein” als sogenannter „Matching Minor” eine notwendige und hinreichende Bedingung dafür darstellt, dass es sich um einen Pfaff’schen Graphen handelt.
Abstract
(Englisch)
Pfaffian graphs are exactly those, on which one can apply Kasteleyns method of counting perfect matchings, which implies the polynomial-time-solvability of our problem. This paper shall demonstrate for which classes of graphs there exists a facile
characterisation of Pfaffian graphs. The difficulties here originate in the unhandy definition, whose requirements are hard to check. Thereby, the characterisation in terms of forbidden subgraphs will be the central issue of our studies. The idea is to state a list of (preferably few) graphs, so that for a given graph, containing one of the graphs in the list
as a so-called matching minor is equivalent with beeing non-Pfaffian.
Schlagwörter
Schlagwörter
(Deutsch)
Pfaff'sche Graphen Abzählen perfekter Matchings
Autor*innen
Thomas Glatz
Haupttitel (Deutsch)
Charakterisierung Pfaff’scher Graphen mittels verbotener Teilgraphen
Paralleltitel (Englisch)
Characterizing Pfaffian graphs in terms of forbidden subgraphs
Publikationsjahr
2010
Umfangsangabe
65 S. : graph. Darst.
Sprache
Deutsch
Beurteiler*in
Ilse Fischer
Klassifikation
31 Mathematik > 31.12 Kombinatorik, Graphentheorie
AC Nummer
AC08317089
Utheses ID
10455
Studienkennzahl
UA | 405 | | |