Flows and colorings in oriented matroids

Nickel, Robert GND

Wir werden uns in dieser Arbeit mit einer Struktur beschäftigen, deren Stärke darin liegt, verschiedenste Gebiete der Mathematik zusammenzuführen wie Lineare Optimierung, affine/projektive Geometrie, Algebra, Verbandstheorie, Komplexitätstheorie, Transversalentheorie und Graphentheorie. Orientierte Matroide reduzieren die Eigenschaften von Punktkonfigurationen, Polyedern und (Pseudo-) Hyperebenenarrangements auf deren rein kombinatorischen Kern und wurden 1978 von Folkman und Lawrence [38] und Bland und Las Vergnas [12] mit der Motivation eingeführt, die praktisch belegte, theoretisch aber nie nachgewiesene gute Effizienz des Simplex-Algorithmus der linearen Optimierung zu beweisen. Außerdem weiß man von Optimierungsproblemen, denen eine Matroidstruktur zugrunde liegt, dass diese exakt mit einer „gierigen“ (greedy) Strategie gelöst werden können ([10]). Die nicht-orientierten Pendants, die Matroide, wurden bereits 1935 von Whitney [111] eingeführt, der die gemeinsamen Eigenschaften von minimal linear abhängigen Mengen von Vektoren und Kreisen in Graphen untersuchte. Weitere davon unabhängige Verweise findet man in Birkhoff [7], van der Waerden [107] und Nakasawa [84]. Wir konzentrieren uns in dieser Arbeit auf Konzepte der Graphentheorie und deren Verallgemeinerung auf orientierte Matroide. Sowohl aus theoretischer, als auch aus praktischer Sicht, liefert die Graphentheorie eine schier endlose Quelle von einfach darzustellenden Problemen, deren Lösung sich aber nicht selten als harte Nuss herausstellt. Das wahrscheinlich prominenteste Beispiel ist das Vier-Farben-Problem (Francis Guthrie um 1852, siehe Cayley [22]): Gegeben ist eine geographische Landkarte mit zusammenhängenden Ländern (also z. B. ohne Kolonien). Ist es immer möglich, deren Länder so einzufärben, dass man benachbarte Länder mit unterschiedlichen Farben versieht und höchstens vier Farben verwendet? Ein Graph besteht aus einer Menge von Knoten und einer Menge von Kanten, die einige Paare dieser Knoten miteinander verbinden. Identifiziert man Länder mit Knoten und Grenzen mit Kanten, so stellt sich das Vier-Farben-Problem wie folgt dar: Gegeben ist ein planarer Graph, d. h. ein Graph, der so in der Ebene gezeichnet werden kann, dass sich Kanten nur in ihren Endpunkten kreuzen. Gibt es eine Färbung der Knoten, so dass durch Kanten verbundene Knoten verschieden gefärbt sind und höchstens vier Farben benötigt werden? Bereits 1852 erstmals erwähnt, dauerte es fast anderthalb Jahrhunderte, bis ein weitestgehend akzeptierter Beweis dafür gefunden wurde, dass eine solche Färbung immer existiert (siehe Appel und Haken [4], Robertson, Sanders, Seymour und Thomas [89]). Bis heute füllt die Theorie der Graphenfärbung ganze Bücher und deren zahlreiche Anwendungen überschreiten bei weitem den Rahmen dieser Einleitung ([25]). Führt man in einem Graphen für jede Kante eine Richtung ein, so kann man durch Label an den Kanten Fluss zwischen den Knoten modellieren, die nun als Verzweigungspunkte in einem (Verkehrs-, Rohr- oder elektrischen) Netzwerk fungieren. Mit der Bedingung, dass alles, was in einen Knoten hineinfließt auch wieder herausfließen soll (Kirchhoff'sches Gesetz [72]), erhält man ein Modell für Rundflüsse. Wenn zusätzlich zwei der Knoten die Rolle von Quelle und Senke übernehmen und jede gerichtete Kante mit einer Maximalkapazität versehen wird, endet man in einem Modell für maximale Flüsse zwischen zwei Knoten mit Kapazitätsbeschränkung, was den Ausgangspunkt der Flusstheorie bildete (Ford und Fulkerson [39]). Im Falle eines planaren Graphen sind Rundflüsse und Knotenfärbungen „duale“ Objekte (Tutte [101]). Um diese Dualität für nicht-planare Graphen und allgemeinere Strukturen zu erhalten, benötigt man orientierte Matroide. Zwei verschiedene Verallgemeinerungen von Flüssen in Graphen auf orientierte Matroide finden sich in Veröffentlichungen der letzten Jahre (siehe Hochstättler und Nesetril [59] und Goddyn, Tarsi und Zhang [45]). Wir untersuchen Flüsse in orientierten Matroiden wie sie von Hochstättler und Nesetril [59] eingeführt wurden und diskutieren Fragestellungen, die beschränkt auf Graphen, zu prominenten Problemen zählen. Die ersten beiden Kapitel dienen der Einführung von Theorie und Notation, die für die Aussagen und Beweise der folgenden Kapitel von Bedeutung sind. Während Kapitel 1 den Grundlagen der Graphentheorie, Geometrie und Verbandstheorie gewidmet ist, geben wir in Kapitel 2 eine recht ausführliche Einführung in die Theorie der orientierten Matroide. Dabei legen wir besonderen Wert auf die zahlreichen Axiomensysteme, mit denen ein orientiertes Matroid definiert werden kann. Diese Grundlagen sind unerlässlich für Kapitel 3, wo wir wohlbekannte Aussagen zur Komposition und Dekomposition von (nicht-orientierten) Matroiden betrachten und deren Korrektheit im Kontext orientierter Matroide beweisen. Der Begriff der Flüsse und Koflüsse (duale Flüsse bzw. Färbungen) wird in Kapitel 4 basierend auf der Arbeit von Hochstättler und Nesetril [59] eingeführt. Wir untersuchen das sogenannte Flussgitter, die Menge aller Rundflüsse. Genauer gesagt bestimmen wir dieses exakt für orientierte Matroide, die uniform sind oder deren Rang höchstens drei ist. Bei der Betrachtung von Koflüssen zeigen wir, dass das orientierte Matroid eines vollständigen Graphen, bei dem jedes Paar von Knoten durch eine Kante verbunden ist, genau wie in der Graphentheorie auch im allgemeineren Kontext orientierter Matroide die einzige Worst-Case-Instanz darstellt. Nach einigen weiteren Resultaten für allgemeine orientierte Matroide beschließen wir das Ende des Kapitels mit Berechnungen auf der Datenbank aller kleinen orientierten Matroide von Finschi [37] und zusammenfassenden Abschnitten über den Ansatz von [45], gruppenwertige Flüsse und das Tutte-Polynom. Wie bereits erwähnt, bildet das Problem der maximalen Flüsse mit Kapazitätsbeschränkungen den Ausgangspunkt der Flusstheorie in Graphen ([39]). In Kapitel 5 werden wir eine neue Verallgemeinerung von maximalen Flüssen auf orientierte Matroide basierend auf dem Flussgitter präsentieren. Die aus der Graphentheorie bekannte Dualität von maximalen Flüssen und minimalen Schnitten verallgemeinern wir zu einer kompatiblen Aussage für orientierte Matroide und leiten notwendige sowie hinreichende Bedingungen mit Hilfe von Eigenschaften des Flussgitters her.

Vorschau

Zitieren

Zitierform:

Nickel, Robert: Flows and colorings in oriented matroids. Hagen 2012. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe