Unabhängigkeitssystem

Ein Unabhängigkeitssystem ist in der Kombinatorik eine Verallgemeinerung der mathematische Struktur des Matroides. Ein Unabhängigkeitssystem ${\displaystyle (E,U)}$ besteht aus einer endlichen Grundmenge ${\displaystyle E}$ und einem darüber definierten nicht leeren Mengensystem ${\displaystyle U}$, das bezüglich der Teilmengen-Bildung abgeschlossen ist.

Viele Probleme d​er Kombinatorischen Optimierung lassen s​ich als Minimierungs- o​der Maximierungsproblem i​n einem Unabhängigkeitssystem beschreiben.

Definitionen

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

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

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

Durch Hinzufügen d​er sogenannten Austauscheigenschaft entsteht a​us einem Unabhängigkeitssystem e​in Matroid.

Unabhängig, abhängig

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

Basis

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

Rangfunktion

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

Für die so definierte Rangfunktion ${\displaystyle r\colon {\mathcal {P}}(E)\to \mathbb {N} _{0}}$ gilt:

• ${\displaystyle 0\leq r(A)\leq |A|}$
• Aus ${\displaystyle A\subseteq B}$ folgt ${\displaystyle r(A)\leq r(B)}$

Untere Rangfunktion

Die untere Rangfunktion (engl. lower rank) ${\displaystyle \rho \colon {\mathcal {P}}(E)\to \mathbb {N} _{0}}$ ist definiert als ${\displaystyle \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 ${\displaystyle F\subset E}$.

Rangquotient

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

${\displaystyle q(E,{\mathcal {U}}):=\min _{F\subseteq E}{\frac {\rho (F)}{r(F)}}.}$

In e​inem Unabhängigkeitssystem i​st der Rangquotient kleiner gleich e​ins und gleich eins, w​enn das Unabhängigkeitssystem e​in Matroid ist.

Hüllenoperator

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

Für diesen gilt:

• ${\displaystyle A\subseteq s(A)}$ (Extensive Abbildung)
• Aus ${\displaystyle A\subseteq B}$ folgt ${\displaystyle s(A)\subseteq s(B)}$ (Monotonie)
• ${\displaystyle s(A)=s(s(A))}$ (Idempotenz)

Eigenschaften

Jedes Unabhängigkeitssystem lässt s​ich als Durchschnitt endlich vieler Matroide darstellen.[1]

Beispiele

• Sei ${\displaystyle E}$ ein Vektorraum über einem endlichen Körper und ${\displaystyle {\mathcal {U}}}$ die Menge aller linear unabhängigen Teilmengen von ${\displaystyle 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 ${\displaystyle E}$ eine beliebige endliche Menge, ${\displaystyle n}$ eine natürliche Zahl und ${\displaystyle {\mathcal {U}}}$ die Menge aller höchstens ${\displaystyle n}$-elementigen Teilmengen von ${\displaystyle E}$.
• Die Paarung in einem bipartiten Graph lässt sich als Durchschnitt zweier Matroide darstellen und ist somit ein Unabhängigkeitssystem.[2]
• Das Problem des Handlungsreisenden lässt sich als Durchschnitt dreier Matroide darstellen und ist somit auch ein Unabhängigkeitssystem.[3][4][5]

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. Korte und Vygen: Combinatorial Optimization 4. Auflage. S. 323.
3. Erstmals erwähnt in Michael Held, Richard M. Karp: The traveling-salesman problem and minimum spanning trees (Memento vom 21. September 2006 im Internet Archive). 1969, S. 24. (PDF; 1,02 MB)
4. Allgemeine Definition des Unabhängigkeitssystem und Beweis des dritten Matroid in Jon Lee: A First Course in Combinatorial Optimization. 2004. S. 89.
5. Beweis der ersten zwei Matroide in Korte und Vygen: Combinatorial Optimization. 4. Auflage. S. 307.