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.^[1]

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.^[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

↑ Beweisidee in Bernhardt Korte und Jens Vygen: Combinatorial Optimization. 4. Auflage. S. 323.
↑ Korte und Vygen: Combinatorial Optimization 4. Auflage. S. 323.
↑ 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)
↑ Allgemeine Definition des Unabhängigkeitssystem und Beweis des dritten Matroid in Jon Lee: A First Course in Combinatorial Optimization. 2004. S. 89.
↑ Beweis der ersten zwei Matroide in Korte und Vygen: Combinatorial Optimization. 4. Auflage. S. 307.

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

[1]

[2]

[3]

[4]

[5]