Cliquen und stabile Mengen

Definitionen

Sei G =( V E ) ein ungerichteter Graph ohne Mehrfachkanten und U eine Teilmenge von V . Man bezeichnet U als Clique von G wenn für je zwei beliebige verschiedene Knoten v und w aus U gilt dass sie durch eine Kante miteinander verbunden sind. Gilt hingegen stets je zwei beliebige verschiedene Knoten v und w aus U dass sie nicht benachbart sind so man U eine stabile bzw. unabhängige Menge von G . Enthält jede Kante von E einen Knoten aus U so nennt man U eine Knotenüberdeckung von G .

Eine Clique bzw. stabile Menge U von G nennt man maximal wenn man keinen weiteren Knoten v aus V zu U hinzufügen kann so dass U zusammen mit v eine Clique bzw. stabile Menge ist. es in G keine Clique bzw. stabile Menge die Elemente als U enthält so nennt man U größte Clique bzw. größte stabile Menge . Die Anzahl Elemente einer größten Clique stabilen Menge nennt man Cliquenzahl bzw. Stabilitäts- oder Unabhängigkeitszahl . Die Anzahl Knoten einer kleinsten Knotenüberdeckung G nennt man Knotenüberdeckungszahl von G .

Statt über Teilmengen von V definiert man Cliquen oder stabile Mengen als spezielle Teilgraphen .

Als Cliquenüberdeckung von G der Größe k bezeichnet man eine Partition der Knotenmenge V ( G ) in k paarweise disjunkte Cliquen V ₁ V ₂ ... V _k .

Gerichtete Graphen oder solche mit Mehrfachkanten sind nicht Gegenstand derartiger Betrachtungen da nicht auf die Richtung oder Vielfachheit der ankommt.

Wichtige Aussagen und Sätze

Das so genannte Cliquenproblem also das Problem in einem Graphen größte Clique bzw. stabile Menge zu finden NP-schwer d. h. es gibt aus Sicht Komplexitätstheorie vermutlich keinen effizienten Algorithmus der das in angemessener Zeit löst. Durch Bildung des Komplementgraphen kann man leicht das eine Problem das andere überführen. Das Cliquenproblem lässt sich polynomial reduzieren auf 3-SAT .

Man kann leicht zeigen dass die eines Graphen immer der Anzahl Knoten eines abzüglich seiner Knotenüberdeckungszahl entspricht. Damit folgt unmittelbar es auch NP-schwer ist eine kleinste Knotenüberdeckung finden.

König konnte jedoch schon 1931 zeigen dass in bipartiten Graphen die Knotenüberdeckungszahl der Paarungszahl entspricht. Für das Problem eine größte Paarung zu finden gibt es aber einen polynomiellen Algorithmus . In bipartiten Graphen lässt sich daher eine kleinste Knotenüberdeckung und eine größte stabile in polynomieller Zeit berechnen. Eine größte Clique sich entsprechend der obigen Reduktion in polynomieller Zeit berechnen wenn der bipartit ist.

Bücher zum Thema Cliquen und stabile Mengen

Dieser Artikel von Wikipedia unterliegt der GNU FDL.