Unabhängigkeitssystem

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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.

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

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).

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 .

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)

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

  • 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.[2]
  • Das Problem des Handlungsreisenden lässt sich als Durchschnitt dreier Matroide darstellen und ist somit auch ein Unabhängigkeitssystem.[3][4][5]
  • 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. Korte und Vygen: Combinatorial Optimization 4. Auflage. S. 323.
  3. Erstmals erwähnt in Michael Held, Richard M. Karp: The traveling-salesman problem and minimum spanning trees (Memento vom 21. September 2006 im Internet Archive). 1969, S. 24. (PDF; 1,02 MB)
  4. Allgemeine Definition des Unabhängigkeitssystem und Beweis des dritten Matroid in Jon Lee: A First Course in Combinatorial Optimization. 2004. S. 89.
  5. Beweis der ersten zwei Matroide in Korte und Vygen: Combinatorial Optimization. 4. Auflage. S. 307.