Quelltext der Seite Unabhängigkeitssystem

Ein '''Unabhängigkeitssystem''' ist in der [[Kombinatorik]] eine Verallgemeinerung der [[mathematische Struktur]] des [[Matroid]]es. Ein ''Unabhängigkeitssystem'' <math>(E,U)</math> besteht aus einer endlichen Grundmenge <math>E</math> und einem darüber definierten nicht leeren [[Mengensystem]] <math>U</math>, das bezüglich der [[Teilmenge]]n-Bildung [[Mengensystem#Stabilität|abgeschlossen]] ist.

Viele Probleme der [[Kombinatorische Optimierung|Kombinatorischen Optimierung]] lassen sich als Minimierungs- oder Maximierungsproblem in einem Unabhängigkeitssystem beschreiben.

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

# <math>\emptyset \in \mathcal{U}</math> (Nicht zu verwechseln mit <math>\emptyset \subseteq \mathcal{U}</math>, was trivial wäre, da die leere Menge Teilmenge jeder Menge ist.)
# <math>A \subseteq B, B\in \mathcal{U} \Rightarrow A\in \mathcal{U}</math> (<math>\mathcal{U}</math> ist nach unten <math>\subseteq</math>-abgeschlossen.)

1. ist äquivalent zu der Forderung, dass <math>\mathcal{U}</math> nicht leer ist.

Durch Hinzufügen der sogenannten ''[[Matroid#Unabhängigkeitsaxiome|Austauscheigenschaft]]'' entsteht aus einem Unabhängigkeitssystem ein [[Matroid]].

=== Unabhängig, abhängig ===
Die Elemente aus <math>\mathcal{U}</math> nennt man unabhängig; die Teilmengen von <math>E</math>, die nicht in <math>\mathcal{U}</math> enthalten sind, nennt man abhängig.

=== Basis ===
Ist eine unabhängige Menge <math>B\in \mathcal{U}</math> maximal, so bezeichnet man sie als ''Basis'' (in Anlehnung an den analogen Begriff im Zusammenhang mit [[Lineare Unabhängigkeit|linearer Unabhängigkeit]]).

=== Kreis ===
Ist eine abhängige Menge <math>K\in \mathcal{P}(E) \setminus \mathcal{U}</math> minimal (d.&nbsp;h. alle echten Teilmengen von <math>K</math> sind unabhängig), so bezeichnet man sie als ''Kreis'' (in Anlehnung an den [[Kreis (Graphentheorie)|Kreisbegriff]] aus der Graphentheorie).

=== Rangfunktion ===
Die Rangfunktion <math>r\colon
\mathcal P(E)\to \mathbb N_0</math> ist definiert als <math>r(F)=\max\{|A|\mid A\in\mathcal U,\ A\subseteq F\}</math> für alle Teilmengen <math>F\subset E</math>.

Für die so definierte Rangfunktion <math>r\colon
\mathcal P(E)\to \mathbb N_0</math> gilt:

* <math>0\le r(A) \le |A|</math>
* Aus <math>A\subseteq B</math> folgt <math>r(A)\le r(B)</math>

=== Untere Rangfunktion ===
Die untere Rangfunktion (engl. lower rank) <math>\rho\colon
\mathcal P(E)\to \mathbb N_0</math> ist definiert als <math>\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\}</math> für alle Teilmengen <math>F\subset E</math>.

=== Rangquotient ===
Der Rangquotient von <math>(E,\mathcal{U})</math> ist definiert als

:<math>q(E,\mathcal{U}):= \min_{F\subseteq E} \frac{\rho(F)}{r(F)}.</math>

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 <math>A\subseteq E</math> ist <math>s(A) = \{x\in E\mid r(A\cup\{x\}) = r(A)\}</math> der [[Hüllenoperator]].

Für diesen gilt:

* <math>A\subseteq s(A)</math> ([[Extensive Abbildung]])
* Aus <math>A\subseteq B</math> folgt <math>s(A)\subseteq s(B)</math> ([[Monotone Abbildung|Monotonie]])
* <math>s(A) = s(s(A))</math> ([[Idempotenz]])

== Eigenschaften ==
Jedes Unabhängigkeitssystem lässt sich als Durchschnitt endlich vieler Matroide darstellen.<ref>Beweisidee in Bernhardt Korte und Jens Vygen: ''Combinatorial Optimization.'' 4. Auflage. S. 323.</ref>

== Beispiele ==
* Sei <math>E</math> ein Vektorraum über einem endlichen Körper und <math>\mathcal{U}</math> die Menge aller linear unabhängigen Teilmengen von <math>E</math>. (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 <math>E</math> eine beliebige endliche Menge, <math>n</math> eine natürliche Zahl und <math>\mathcal{U}</math> die Menge aller höchstens <math>n</math>-elementigen Teilmengen von <math>E</math>.
* Die [[Paarung (Graphentheorie)|Paarung]] in einem [[Bipartiter Graph|bipartiten Graph]] lässt sich als Durchschnitt zweier Matroide darstellen und ist somit ein Unabhängigkeitssystem.<ref>Korte und Vygen: ''Combinatorial Optimization'' 4. Auflage. S. 323.</ref>
* Das [[Problem des Handlungsreisenden]] lässt sich als Durchschnitt dreier Matroide darstellen und ist somit auch ein Unabhängigkeitssystem.<ref>Erstmals erwähnt in Michael Held, [[Richard M. Karp]]: ''{{Webarchiv | url=http://www.cse.wustl.edu/~chen/7102/Karp-TSP.pdf | wayback=20060921030923 | text=The traveling-salesman problem and minimum spanning trees}}.'' 1969, S. 24. (PDF; 1,02&nbsp;MB)</ref><ref>Allgemeine Definition des Unabhängigkeitssystem und Beweis des dritten Matroid in Jon Lee: ''A First Course in Combinatorial Optimization''. 2004. S. 89.</ref><ref>Beweis der ersten zwei Matroide in Korte und Vygen: ''Combinatorial Optimization.'' 4. Auflage. S. 307.</ref>

== 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 ==
<references />

{{SORTIERUNG:Unabhangigkeitssystem}}
[[Kategorie:Mengensystem]]
[[Kategorie:Mengenlehre]]