Unabhängigkeitssystem

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

Sei E eine beliebige endliche Grundmenge und $\mathcal U$ ein System von Teilmengen von E (also $E\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

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

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

Ist eine abhängige Menge $K\in \mathcal{P}(E) \quad \mathcal{U}$ minimal, so bezeichnet man sie als Kreis (in Anlehnung an den Kreisbegriff aus der Graphentheorie).

Rangfunktion

Die Rangfunktion $r\colon \mathcal P(E)\to \mathbb N_0$ ist definiert als $r(F)=\max\{|A|\mid A\in 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

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 B, B\in \mathcal{U} \text{ und } B\cup \{x\}\not\in\mathcal{U} \ \forall x\in A\setminus B\}$ für alle Teilmengen $F\subset E$.

Rangquotient

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

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:

• $A\subseteq s(A)$
• Aus $A\subseteq B$ folgt $s(A)\subseteq s(B)$
• s(A) = s(s(A))

Eigenschaften

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

Beispiele

• 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

• 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

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