Unabhängigkeitssystem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein Unabhängigkeitssystem ist in der Kombinatorik eine Verallgemeinerung der mathematische Struktur des Matroides. Ein Unabhängigkeitssystem besteht aus einer endlichen Grundmenge und einem darüber definierten nicht leeren Mengensystem , das bezüglich der Teilmengen-Bildung abgeschlossen ist.

Viele Probleme der Kombinatorischen Optimierung lassen sich als Minimierungs- oder Maximierungsproblem in einem Unabhängigkeitssystem beschreiben.

Definitionen[Bearbeiten | Quelltext bearbeiten]

Sei eine beliebige endliche Grundmenge und ein System von Teilmengen von (also ), dann ist das Paar ein Unabhängigkeitssystem, wenn die folgenden Bedingungen erfüllt sind:

  1. (Nicht zu verwechseln mit , was trivial wäre, da die leere Menge Teilmenge jeder Menge ist.)
  2. ( ist nach unten -abgeschlossen.)

1. ist äquivalent zu der Forderung dass nicht leer ist.

Durch Hinzufügen der sogenannten Austauscheigenschaft entsteht aus einem Unabhängigkeitssystem ein Matroid.

Unabhängig, abhängig[Bearbeiten | Quelltext bearbeiten]

Die Elemente aus nennt man unabhängig, die Teilmengen von , die nicht in enthalten sind, nennt man abhängig.

Basis[Bearbeiten | Quelltext bearbeiten]

Ist eine unabhängige Menge maximal, so bezeichnet man sie als Basis (in Anlehnung an den analogen Begriff im Zusammenhang mit linearer Unabhängigkeit).

Kreis[Bearbeiten | Quelltext bearbeiten]

Ist eine abhängige Menge minimal (d.h. alle echten Teilmengen von sind unabhängig), so bezeichnet man sie als Kreis (in Anlehnung an den Kreisbegriff aus der Graphentheorie).

Rangfunktion[Bearbeiten | Quelltext bearbeiten]

Die Rangfunktion ist definiert als für alle Teilmengen .

Für die so definierte Rangfunktion gilt:

  • Aus folgt

Untere Rangfunktion[Bearbeiten | Quelltext bearbeiten]

Die untere Rangfunktion (engl. lower rank) ist definiert als für alle Teilmengen .

Rangquotient[Bearbeiten | Quelltext bearbeiten]

Der Rangquotient von ist definiert als

In einem Unabhängigkeitssystem ist der Rangquotient kleiner gleich eins und gleich eins, wenn das Unabhängigkeitssystem ein Matroid ist.

Hüllenoperator[Bearbeiten | Quelltext bearbeiten]

Für eine Teilmenge ist der Hüllenoperator.

Für diesen gilt:

  • (Extensive Abbildung)
  • Aus folgt (Monotonie)
  • (Idempotenz)

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Jedes Unabhängigkeitssystem lässt sich als Durchschnitt endlich vieler Matroide darstellen.[1][2]

Beispiele[Bearbeiten | Quelltext bearbeiten]

  • Sei ein Vektorraum über einem endlichen Körper und die Menge aller linear unabhängigen Teilmengen von . (Dieses Beispiel motiviert die Bezeichnung. Man kann dieses Beispiel auch auf nichtendliche Körper verallgemeinern, allerdings gelten dann viele der hier gemachten Aussagen über Unabhängigkeitssysteme nicht mehr.)
  • Sei eine beliebige endliche Menge, eine natürliche Zahl und die Menge aller höchstens -elementigen Teilmengen von .
  • Die Paarung in einem bipartiten Graph lässt sich als Durchschnitt zweier Matroide darstellen und ist somit ein Unabhängigkeitssystem.[3]
  • Das Problem des Handlungsreisenden lässt sich als Durchschnitt dreier Matroide darstellen und ist somit auch ein Unabhängigkeitssystem.[4][5][6]

Literatur[Bearbeiten | Quelltext bearbeiten]

  • James Oxley: Matroid Theory. Oxford Mathematics, 1992, ISBN 0-19-920250-8.
  • Bernhardt Korte, Jens Vygen: Combinatorial Optimization. Theory and Algorithms. 4. Auflage. Springer, 2007, ISBN 978-3-540-71843-7.
  • Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization. Algorithms and Complexity. Prentice Hall, 1982, ISBN 0-13-152462-3.
  • Jon Lee: A First Course in Combinatorial Optimization. Cambridge Texts in Applied Mathematics, 2004, ISBN 0-521-01012-8.
  • Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 2. Auflage. Vieweg-Teubner, 2009, ISBN 978-3-8348-0629-1.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Beweisidee in Bernhardt Korte und Jens Vygen: Combinatorial Optimization. 4. Auflage. S. 323.
  2. Ausführlicher Beweis mithilfe des Rangquotienten in Du, Ding-zhu: Design and Analysis of Computer Algorithms (Vorlesungsmitschriften 2008 (ppt; 373 kB)). S. 24.
  3. Korte und Vygen: Combinatorial Optimization 4. Auflage. S. 323.
  4. Erstmals erwähnt in Michael Held, Richard M. Karp: The traveling-salesman problem and minimum spanning trees. (pdf). 1969, S. 24.
  5. Allgemeine Definition des Unabhängigkeitssystem und Beweis des dritten Matroid in Jon Lee: A First Course in Combinatorial Optimization. 2004. S. 89.
  6. Beweis der ersten zwei Matroide in Korte und Vygen: Combinatorial Optimization. 4. Auflage. S. 307.