Volltextdatei(en) vorhanden
Titel: The tree-like connectivity structure of finite graphs and matroids
Sonstige Titel: Die baumartige Zusammenhangsstruktur endlicher Graphen und Matroide
Sprache: Englisch
Autor*in: Hundertmark, Fabian
Schlagwörter: Zusammenhang; Baumstruktur; Graph Theory; Matroid Theory; Connectivity; Tree-decomposition
GND-Schlagwörter: GraphentheorieGND
Matroidtheorie
Dekomposition
Erscheinungsdatum: 2013
Tag der mündlichen Prüfung: 2012-09-25
Zusammenfassung: 
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.
URL: https://ediss.sub.uni-hamburg.de/handle/ediss/4887
URN: urn:nbn:de:gbv:18-61508
Dokumenttyp: Dissertation
Betreuer*in: Diestel, Reinhard (Prof. Dr.)
Enthalten in den Sammlungen:Elektronische Dissertationen und Habilitationen

Dateien zu dieser Ressource:
Datei Beschreibung Prüfsumme GrößeFormat  
Dissertation.pdf429e8f5245cfcf46017cb8db96c580d11.45 MBAdobe PDFÖffnen/Anzeigen
Zur Langanzeige

Diese Publikation steht in elektronischer Form im Internet bereit und kann gelesen werden. Über den freien Zugang hinaus wurden durch die Urheberin / den Urheber keine weiteren Rechte eingeräumt. Nutzungshandlungen (wie zum Beispiel der Download, das Bearbeiten, das Weiterverbreiten) sind daher nur im Rahmen der gesetzlichen Erlaubnisse des Urheberrechtsgesetzes (UrhG) erlaubt. Dies gilt für die Publikation sowie für ihre einzelnen Bestandteile, soweit nichts Anderes ausgewiesen ist.

Info

Seitenansichten

165
Letzte Woche
Letzten Monat
geprüft am 27.03.2024

Download(s)

29
Letzte Woche
Letzten Monat
geprüft am 27.03.2024
Werkzeuge

Google ScholarTM

Prüfe