Stabile Menge

Eine stabile Menge, unabhängige Menge oder Co-Clique ist in der Graphentheorie eine Teilmenge von Knoten eines Graphen, die zueinander nicht 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

Die neun blauen Knoten bilden eine maximale stabile Menge.

Stabile Menge

Sei <math>G=(V,E)</math> ein 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 benachbart sind, so nennt man <math>U</math> eine stabile bzw. unabhängige Menge des Graphen.<ref name="aigner2015">{{#invoke:Vorlage:Literatur|f}}</ref><ref name="krumke2012">{{#invoke:Vorlage:Literatur|f}}</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 Teilgraphen.

Äußerlich stabile Menge

Eine Teilmenge <math>D</math> von Knoten in einem gerichteten Graphen <math>G=(V,E)</math> heißt äußerlich stabil oder dominierend, wenn jeder Knoten aus <math>V \setminus D</math> einen positiven Nachbarn in <math>D</math> hat. Die 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 Cliquen im Komplementgraphen.

Stabile Mengen sind außerdem genau die Komplemente von 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 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 polynomiell äquivalent.

Das Stabilitätsproblem ist NP-vollständig, das zugehörige Optimierungs- und Suchproblem ist NP-äquivalent. Die NP-Schwere des Stabilitätsproblems lässt sich dabei leicht durch Reduktion des Cliquenproblems auf das Stabilitätsproblem zeigen, indem man den Komplementgraphen bildet.

In 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 perfekten Graphen in polynomieller Zeit berechnet werden können. Die Berechnung einer maximalen stabilen Menge gelingt bereits mit einem einfachen Greedy-Algorithmus.

Weblinks

[{{canonicalurl:Commons:Category:{{#if:Independent set (graph theory)|Independent set (graph theory)|Stabile Menge}}|uselang=de}} Commons: {{#if:Stabile Menge|Stabile Menge|{{#if:Independent set (graph theory)|Independent set (graph theory)|{{#invoke:WLink|getArticleBase}}}}}}]{{#switch:1

|X|x= |0|-= |S|s= – Sammlung von Bildern |1|= – Sammlung von Bildern{{#if:

    | {{#switch: {{#invoke:TemplUtl|faculty|1}}/{{#invoke:TemplUtl|faculty|1}}
        |1/=  und Videos
        |1/1=, Videos und Audiodateien
        |/1=  und Audiodateien}}
    | , Videos und Audiodateien
  }}

|#default= – }}{{#if: Independent set (graph theory)

   | {{#ifeq: {{#invoke:Str|left|independent set (graph theory)|9}} 
       | category:

| FEHLER: Ohne Category: angeben!}}}}

Vorlage:Wikidata-Registrierung

Einzelnachweise