imported>Thomas Dresler: Commonscat mit Helferlein hinzugefügt

2025-09-28T20:59:13Z

Commonscat mit Helferlein hinzugefügt

Neue Seite

Eine '''stabile Menge''', '''unabhängige Menge''' oder '''Co-Clique''' ist in der [[Graphentheorie]] eine Teilmenge von Knoten eines Graphen, die zueinander nicht [[Nachbarschaft (Graphentheorie)|adjazent]] sind. Zu entscheiden, ob ein Graph eine stabile Menge einer bestimmten Mindestgröße enthält, wird '''Stabilitätsproblem''' genannt und gilt, wie das Finden einer größten stabilen Menge, als algorithmisch schwierig.

== Definitionen ==
[[Datei:Independent set graph.svg|miniatur|Die neun blauen Knoten bilden eine maximale stabile Menge.]]

=== Stabile Menge ===
Sei <math>G=(V,E)</math> ein [[Ungerichteter Graph|ungerichteter]] [[Graph ohne Mehrfachkanten]] und <math>U</math> eine [[Teilmenge]] von <math>V</math>. Gilt für je zwei beliebige verschiedene Knoten <math>v</math> und <math>w</math> aus <math>U</math>, dass sie nicht [[Nachbarschaft (Graphentheorie)|benachbart]] sind, so nennt man <math>U</math> eine ''stabile'' bzw. ''unabhängige Menge'' des Graphen.<ref name="aigner2015">{{Literatur |Autor=Martin Aigner |Titel=Graphentheorie – Eine Einführung aus dem 4-Farben Problem |Verlag=Springer |Auflage=2. Auflage |Datum=2015 |ISBN=978-3-658-10323-1 |DOI=10.1007/978-3-658-10323-1 |Seiten=82–83 |Kommentar=verwendet die Bezeichnungen „unabhängig“ und „Unabhängigkeitszahl“}}</ref><ref name="krumke2012">{{Literatur |Autor=Sven Oliver Krumke, Hartmut Noltemeier |Titel=Graphentheoretische Konzepte und Algorithmen |Reihe=Leitfäden der Informatik |Auflage=3 |Datum=2012 |Verlag=Springer |ISBN=9783834822642 |Seiten=57 |Kommentar=indiziert „stabile Menge“ bzw. „Stabilitätszahl“ als synonym zu „unabhängige Menge“ bzw. „Unabhängigkeitszahl“, definiert „maximale Menge“}}</ref>

=== Maximale stabile Menge ===
Eine stabile Menge <math>U</math> von <math>G</math> nennt man ''maximal'', wenn man keinen weiteren Knoten <math>v</math> aus <math>V \setminus U</math> zu <math>U</math> hinzufügen kann, so dass <math>U</math> zusammen mit <math>v</math> eine stabile Menge ist.<ref name="krumke2012"/>

Gibt es in <math>G</math> keine stabile Menge, die mehr Elemente als <math>U</math> enthält, so nennt man <math>U</math> ''größte stabile Menge''. Die Anzahl der Elemente einer größten stabilen Menge nennt man ''Stabilitäts-'' oder ''Unabhängigkeitszahl''.<ref name="aigner2015"/><ref name="krumke2012"/> Statt über Teilmengen von <math>V</math> definiert man stabile Mengen auch als spezielle [[Teilgraph]]en.

=== Äußerlich stabile Menge ===
Eine Teilmenge <math>D</math> von Knoten in einem [[Gerichteter Graph|gerichteten Graphen]] <math>G=(V,E)</math> heißt ''äußerlich stabil'' oder ''dominierend'', wenn jeder Knoten aus <math>V \setminus D</math> einen [[Nachbarschaft (Graphentheorie)|positiven Nachbarn]] in <math>D</math> hat. Die [[Mächtigkeit (Mathematik)|Mächtigkeit]] einer kleinsten dominierenden Menge heißt ''Dominationszahl'' <math>\gamma (G)</math> des Graphen <math>G</math>. Eine Menge von Knoten eines gerichteten Graphen heißt ''Kern'' des Graphen, wenn sie zugleich stabil und dominierend ist.

== Eigenschaften ==
Stabile Mengen eines Graphen sind genau die [[Clique (Graphentheorie)|Cliquen]] im [[Komplementgraph|Komplementgraphen]].

Stabile Mengen sind außerdem genau die [[Komplement (Mengenlehre)|Komplemente]] von [[Knotenüberdeckung|Knotenüberdeckungen]]: Eine Menge enthält zu jeder Kante höchstens einen Knoten genau dann, wenn ihr Komplement zu jeder Kante mindestens einen Knoten enthält.

Insbesondere sind maximale stabile Mengen eines Graphen einerseits maximale Cliquen im Komplementgraphen, andererseits die Komplemente minimaler Knotenüberdeckungen im originalen Graphen.

== Probleme und Komplexität ==

Das [[Entscheidbar|Entscheidungsproblem]], zu einem Graphen ''G'' und einer natürlichen Zahl ''k'' zu entscheiden, ob ''G'' eine stabile Menge der Größe mindestens ''k'' enthält, wird ''Stabilitätsproblem'' genannt. Das zugehörige [[Optimierungsproblem]] fragt nach der Stabilitätszahl eines Graphen. Das zugehörige [[Suchproblem]] fragt nach einer größten stabilen Menge. Diese drei Probleme sind [[Polynomialzeitreduktion|polynomiell äquivalent]].

Das Stabilitätsproblem ist [[NP-Vollständigkeit|NP-vollständig]], das zugehörige Optimierungs- und Suchproblem ist [[NP-Äquivalenz|NP-äquivalent]]. Die [[NP-Schwere]] des Stabilitätsproblems lässt sich dabei leicht durch [[Reduktion (Theoretische Informatik)|Reduktion]] des [[Cliquenproblem]]s auf das Stabilitätsproblem zeigen, indem man den [[Komplementgraph]]en bildet.

In [[Bipartiter Graph|bipartiten]] Graphen lässt sich eine größte stabile Menge in polynomieller Zeit berechnen.
Tatsächlich gilt sogar etwas stärker, dass die Stabilitätszahl in [[Perfekter Graph|perfekten Graphen]] in polynomieller Zeit berechnet werden können.
Die Berechnung einer maximalen stabilen Menge gelingt bereits mit einem einfachen [[Greedy-Algorithmus]].

== Weblinks ==
{{Commonscat|Independent set (graph theory)|Stabile Menge}}

== Einzelnachweise ==
<references />

[[Kategorie:Grundbegriff (Graphentheorie)]]
[[Kategorie:Komplexitätstheorie]]

Stabile Menge - Versionsgeschichte

imported>Thomas Dresler: Commonscat mit Helferlein hinzugefügt