FAQ
© 2015 Staats- und Universitätsbibliothek
Hamburg, Carl von Ossietzky

Öffnungszeiten heute09.00 bis 24.00 Uhr alle Öffnungszeiten

Eingang zum Volltext in OPUS

Hinweis zum Urheberrecht

Dissertation zugänglich unter
URN: urn:nbn:de:gbv:18-61508
URL: http://ediss.sub.uni-hamburg.de/volltexte/2013/6150/


The tree-like connectivity structure of finite graphs and matroids

Die baumartige Zusammenhangsstruktur endlicher Graphen und Matroide

Hundertmark, Fabian

pdf-Format:
 Dokument 1.pdf (1.450 KB) 


SWD-Schlagwörter: Graphentheorie , Matroidtheorie , Dekomposition
Freie Schlagwörter (Deutsch): Zusammenhang , Baumstruktur
Freie Schlagwörter (Englisch): Graph Theory , Matroid Theory , Connectivity , Tree-decomposition
Basisklassifikation: 31.12
Institut: Mathematik
DDC-Sachgruppe: Mathematik
Dokumentart: Dissertation
Hauptberichter: Diestel, Reinhard (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 25.09.2012
Erstellungsjahr: 2013
Publikationsdatum: 25.04.2013
Kurzfassung auf Deutsch: In der vorliegenden Dissertation untersuchen wir die Zusammenhangsstruktur endlicher Graphen und Matroide. Wir zeigen, dass sich die unterscheid\-baren hochzusammenhängenden Teile eines Graphen oder Matroids als unterschiedliche Orientierungen seiner Teilungen, die wir als Profile bezeichnen, beschreiben lassen. Insbesondere können wir die maximalen k-untrennbaren Eckenmengen eines Graphen, seine k-Blöcke, durch Profile (der Ordnung k+1) beschreiben. Ferner zeigen wir, dass die Tangles der Ordnung k eines Graphen oder Matroids spezielle k-Profile sind. Als Hauptresultat dieser Arbeit zeigen wir, dass zu jedem Graphen oder Matroid und zu jeder natürlichen Zahl k eine kanonische, d.h. nur von der Struktur des Graphen oder Matroids abhängende, Baumzerlegung der Adhäsion kleiner k existiert, die alle k-Profile des Graphen oder Matroids unterscheidet. Anschaulich bedeutet dies, dass die hochzusammenhängenden Teile eines Graphen oder Matroids untereinander baumartig verbunden sind, also dass jeder Graph und jedes Matroid eine baumartige Zusammenhangsstruktur aufweist.

In Kapitel 2 zeigen wir zunächst, dass die Baumzerlegungen einer beliebigen endlichen Menge durch verschachtelte Systeme von Teilungen beschrieben werden können, und umgekehrt, dass jedes verschachtelte System von Teilungen einer Menge durch einen Baum, bzw. eine Baumzerlegung dieser Menge, beschrieben wird. Außerdem betrachten wir, unter welchen Bedingungen aus einem nicht verschachtelten System von Teilungen ein verschachteltes Teilsystem mit ähnlichen Trennungseigenschaften ausgewählt werden kann.

In Kapitel 3 beschäftigen wir uns mit den k-Blöcken eines Graphen. Wir zeigen, dass diese durch eine Baumzerlegung kleiner Adhäsion unterschieden werden können, und untersuchen, wie die Existenz von k-Blöcken in einem Graphen mit anderen Invarianten des Graphen zusammenhängt.

Im vierten Kapitel führen wir Profile ein und diskutieren, unter welchen Bedingungen eine Menge von Profilen durch ein verschachteltes System von Teilungen unterschieden werden kann. Wir diskutieren, wie der Zusammenhang eines Graphen oder Matroids durch eine Bewertung geeigneter Teilungen seiner Grundmenge beschrieben werden kann. In Kapitel 5 wenden wir schließlich die allgemeinen Resultate aus Kapitel 4 auf Graphen und Matroide an.

Zugriffsstatistik

keine Statistikdaten vorhanden
Legende