Rieder, Jörg (1989) Gitterstrukturen bei Matroidproblemen. PhD thesis.

Abstract

In der vorliegenden Arbeit untersuchen wir Gitter, die von Matroidstrukturen und 2-Matroidschnitten, zwei Grundstrukturen zahlreicher Optimierungsprobleme, erzeugt werden. Im ersten Kapitel stellen wir die notwendigen Grundlagen über Gitter, Graphen und Matroide zur Verfügung. Anschließend charakterisieren wir im zweiten Kapitel die Gitter der Matroidbasen, wobei wir lediglich die Matroidaxiome benötigen. Daneben zeigen wir die Dualität der von den Kreisen graphischer und cographischer Matroide generierten Gitter und geben einige Beispiele für weitere Kreisgitter von Matroiden. Im dritten Kapitel beschäftigen wir uns dann mit dem Schnitt zweier Matroide M und N. Wir diskutieren eine Rangbedingung, die einerseits garantiert, daß M und N gemeinsame Basen besitzen, und die andererseits eine Dekomposition des betrachteten Problems verhindert. Die direkte Verallgemeinerung des von Lovász untersuchten bipartiten Matchings auf den Schnitt zweier Partitionsmatroide (bzw. das hierzu äquivalente Problem der f-Faktoren in bipartiten Graphen) erlaubt eine schöne Beschreibung des zugehörigen Gitters. Hier ist das von den gemeinsamen Basen von M und N aufgespannte Gitter genau der Schnitt der beiden Gitter der Basen von M bzw. N, eine im allgemeinen für Gitter ungewöhnliche Eigenschaft. Dieses Ergebnis bleibt auch dann gültig, wenn M ein beliebiges Matroid ist, falls N nur zwei Komponenten besitzt. Erst ab drei Partitionsklassen bei N wird das von den gemeinsamen Basen von M und N erzeugte Gitter, wie auch im allgemeinen Fall, zusätzlich von Eigenschaften des Schnittproblems bestimmt, die nicht auf ein Matroid alleine zurückzuführen sind. Ein Beispiel hierfür ist der starke Zusammenhang von gerichteten Graphen beim Schnitt des graphischen mit dem Endpunktpartitions-Matroid. Im abschließenden Kapitel geben wir eine kommentierende Kurzzusammenfassung der Ergebnisse und stellen noch einige weiterführende Probleme vor.

Actions:

Download:	Postscript - Accepted Version Download (483kB) | Preview
Editorial actions:	View Item (Login required)