The tree-like connectivity structure of finite graphs and matroids
Fabian Hundertmark · 2013
In der vorliegenden Dissertation untersuchen wir die Zusammenhangsstruktur endlicher Graphen und Matroide. Wir zeigen, dass sich die unterscheid\-baren hochzusammenhangenden Teile eines Graphen oder Matroids als unterschiedliche Orientierungen seiner Teilungen, die wir als Profile bezeichnen, beschreiben lassen. Insbesondere konnen wir die maximalen k-untrennbaren Eckenmengen eines Graphen, seine k-Blocke, 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 naturlichen Zahl k eine kanonische, d.h. nur von der Struktur des Graphen oder Matroids abhangende, Baumzerlegung der Adhasion kleiner k existiert, die alle k-Profile des Graphen oder Matroids unterscheidet. Anschaulich bedeutet dies, dass die hochzusammenhangenden 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 zunachst, dass die Baumzerlegungen einer beliebigen endlichen Menge durch verschachtelte Systeme von Teilungen beschrieben werden konnen, und umgekehrt, dass jedes verschachtelte System von Teilungen einer Menge durch einen Baum, bzw. eine Baumzerlegung dieser Menge, beschrieben wird. Auserdem betrachten wir, unter welchen Bedingungen aus einem nicht verschachtelten System von Teilungen ein verschachteltes Teilsystem mit ahnlichen Trennungseigenschaften ausgewahlt werden kann. In Kapitel 3 beschaftigen wir uns mit den k-Blocken eines Graphen. Wir zeigen, dass diese durch eine Baumzerlegung kleiner Adhasion unterschieden werden konnen, und untersuchen, wie die Existenz von k-Blocken in einem Graphen mit anderen Invarianten des Graphen zusammenhangt. Im vierten Kapitel fuhren 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 schlieslich die allgemeinen Resultate aus Kapitel 4 auf Graphen und Matroide an.