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 (E,U) besteht aus einer endlichen Grundmenge E und einem darüber definierten nicht leeren Mengensystem U, 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]

Sei E eine beliebige endliche Grundmenge und \mathcal U ein System von Teilmengen von E (also \mathcal U\subseteq \mathcal{P} (E) ), dann ist das Paar (E,\mathcal{U}) ein Unabhängigkeitssystem, wenn die folgenden Bedingungen erfüllt sind:

  1. \emptyset \in \mathcal{U} (Nicht zu verwechseln mit \emptyset \subseteq \mathcal{U}, was trivial wäre, da die leere Menge Teilmenge jeder Menge ist.)
  2. A \subseteq B, B\in \mathcal{U} \Rightarrow A\in \mathcal{U} (\mathcal{U} ist nach unten \subseteq-abgeschlossen.)

1. ist äquivalent zu der Forderung dass \mathcal{U} nicht leer ist.

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

Unabhängig, abhängig[Bearbeiten]

Die Elemente aus \mathcal{U} nennt man unabhängig, die Teilmengen von E, die nicht in \mathcal{U} enthalten sind, nennt man abhängig.

Basis[Bearbeiten]

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

Kreis[Bearbeiten]

Ist eine abhängige Menge K\in \mathcal{P}(E) \setminus \mathcal{U} minimal (d.h. alle echten Teilmengen von K sind unabhängig), so bezeichnet man sie als Kreis (in Anlehnung an den Kreisbegriff aus der Graphentheorie).

Rangfunktion[Bearbeiten]

Die Rangfunktion r\colon
\mathcal P(E)\to \mathbb N_0 ist definiert als r(F)=\max\{|A|\mid A\in\mathcal U,\ A\subseteq F\} für alle Teilmengen F\subset E.

Für die so definierte Rangfunktion r\colon
\mathcal P(E)\to \mathbb N_0 gilt:

  • 0\le r(A) \le |A|
  • Aus A\subseteq B folgt r(A)\le r(B)

Untere Rangfunktion[Bearbeiten]

Die untere Rangfunktion (engl. lower rank) \rho\colon
\mathcal P(E)\to \mathbb N_0 ist definiert als \rho(F)=\min\{|A|\mid A\subseteq F, A\in \mathcal{U} \text{ und } A\cup \{x\}\not\in\mathcal{U} \ \forall x\in F\setminus A\} für alle Teilmengen F\subset E.

Rangquotient[Bearbeiten]

Der Rangquotient von (E,\mathcal{U}) ist definiert als

q(E,\mathcal{U}):= \min_{F\subseteq E} \frac{\rho(F)}{r(F)}.

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

Hüllenoperator[Bearbeiten]

Für eine Teilmenge A\subseteq E ist s(A) = \{x\in E\mid r(A\cup\{x\}) = r(A)\} der Hüllenoperator.

Für diesen gilt:

Eigenschaften[Bearbeiten]

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

Beispiele[Bearbeiten]

  • Sei E ein Vektorraum über einem endlichen Körper und \mathcal{U} die Menge aller linear unabhängigen Teilmengen von E. (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 E eine beliebige endliche Menge, n eine natürliche Zahl und \mathcal{U} die Menge aller höchstens n-elementigen Teilmengen von E.
  • 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]

  • 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]

  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.