The tree-like connectivity structure of finite graphs and matroids

Abstract

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.