Gitterstrukturen bei Matroidproblemen
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.
Download: |
Download (483kB) | Preview |
---|---|
Editorial actions: | ![]() |
Item Type: | Thesis (PhD) |
---|---|
Citations: | No citation data. |
Uncontrolled Keywords: | lattice structures matroid problems |
Subjects: |
|
Divisions: | Mathematical Institute |
Related URLs: |
ZAIK Number: | zpr89-079 |
---|---|
Depositing User: | Archive Admin |
Date Deposited: | 02 Apr 2001 00:00 |
Last Modified: | 19 Dec 2011 09:46 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/79 |