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 ${\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

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

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\leq r(A)\leq |A|$
• Aus $A\subseteq B$ folgt $r(A)\leq 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 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

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)$ (Extensive Abbildung)
• Aus $A\subseteq B$ folgt $s(A)\subseteq s(B)$ (Monotonie)
• $s(A)=s(s(A))$ (Idempotenz)

Eigenschaften

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

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.
• Das Problem des Handlungsreisenden lässt sich als Durchschnitt dreier Matroide darstellen und ist somit auch ein Unabhängigkeitssystem.

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.