Unabhängigkeitssystem
# 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:

* $\emptyset \in {\mathcal {U}}$ (Nicht zu verwechseln mit $\emptyset \subseteq {\mathcal {U}}$, was trivial wäre, da die leere Menge Teilmenge jeder Menge ist.)
* $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.
