Unabhängigkeitssystem

Ein Unabhängigkeitssystem ist in der Kombinatorik eine Verallgemeinerung der mathematische Struktur des Matroides. Ein Unabhängigkeitssystem <math>(E,U)</math> besteht aus einer endlichen Grundmenge <math>E</math> und einem darüber definierten nicht leeren Mengensystem <math>U</math>, 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

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

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

1. ist äquivalent zu der Forderung, dass <math>\mathcal{U}</math> nicht leer ist.

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

Unabhängig, abhängig

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

Basis

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

Kreis

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

Rangfunktion

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

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

<math>0\le r(A) \le |A|</math>
Aus <math>A\subseteq B</math> folgt <math>r(A)\le r(B)</math>

Untere Rangfunktion

Die untere Rangfunktion (engl. lower rank) <math>\rho\colon \mathcal P(E)\to \mathbb N_0</math> ist definiert als <math>\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\}</math> für alle Teilmengen <math>F\subset E</math>.

Rangquotient

Der Rangquotient von <math>(E,\mathcal{U})</math> ist definiert als

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

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

Hüllenoperator

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

Für diesen gilt:

<math>A\subseteq s(A)</math> (Extensive Abbildung)
Aus <math>A\subseteq B</math> folgt <math>s(A)\subseteq s(B)</math> (Monotonie)
<math>s(A) = s(s(A))</math> (Idempotenz)

Eigenschaften

Jedes Unabhängigkeitssystem lässt sich als Durchschnitt endlich vieler Matroide darstellen.<ref>Beweisidee in Bernhardt Korte und Jens Vygen: Combinatorial Optimization. 4. Auflage. S. 323.</ref>

Beispiele

Sei <math>E</math> ein Vektorraum über einem endlichen Körper und <math>\mathcal{U}</math> die Menge aller linear unabhängigen Teilmengen von <math>E</math>. (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 <math>E</math> eine beliebige endliche Menge, <math>n</math> eine natürliche Zahl und <math>\mathcal{U}</math> die Menge aller höchstens <math>n</math>-elementigen Teilmengen von <math>E</math>.
Die Paarung in einem bipartiten Graph lässt sich als Durchschnitt zweier Matroide darstellen und ist somit ein Unabhängigkeitssystem.<ref>Korte und Vygen: Combinatorial Optimization 4. Auflage. S. 323.</ref>
Das Problem des Handlungsreisenden lässt sich als Durchschnitt dreier Matroide darstellen und ist somit auch ein Unabhängigkeitssystem.<ref>Erstmals erwähnt in Michael Held, Richard M. Karp: <templatestyles src="Webarchiv/styles.css" />The traveling-salesman problem and minimum spanning trees (Memento vom 21. September 2006 im Internet Archive). 1969, S. 24. (PDF; 1,02 MB)</ref><ref>Allgemeine Definition des Unabhängigkeitssystem und Beweis des dritten Matroid in Jon Lee: A First Course in Combinatorial Optimization. 2004. S. 89.</ref><ref>Beweis der ersten zwei Matroide in Korte und Vygen: Combinatorial Optimization. 4. Auflage. S. 307.</ref>

Literatur

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