Knotenüberdeckungen, Cliquen und stabile Mengen

Stichpunkte

Allgemein
	[Bearbeiten]
Definitionen
	Sei G=(V
	E) ein ungerichteter Graph ohne Mehrfachkanten und U eine Teilmenge von V
	dass sie durch eine Kante miteinander verbunden sind
	wenn für je zwei beliebige verschiedene Knoten v und w aus U gilt
	Man bezeichnet U als Clique von G
	dass sie nicht benachbart sind
	Gilt hingegen stets für je zwei beliebige verschiedene Knoten v und w aus U
	so nennt 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
	so dass U zusammen mit v eine Clique bzw. stabile Menge ist
	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 nennt man U größte Clique bzw. größte stabile Menge
	die mehr Elemente als U enthält
	Gibt es in G keine Clique bzw. stabile Menge
	Die Anzahl Elemente einer größten Clique bzw. stabilen Menge nennt man Cliquenzahl bzw
	Stabilitäts- oder Unabhängigkeitszahl
	Die Anzahl Knoten einer kleinsten Knotenüberdeckung von G nennt man Knotenüberdeckungszahl von G
	Statt über Teilmengen von V definiert man Cliquen oder stabile Mengen auch 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 V1
	V2
	Vk
	...
	da es nicht auf die Richtung oder Vielfachheit der Kanten ankommt. [Bearbeiten]
	Gerichtete Graphen oder solche mit Mehrfachkanten sind nicht Gegenstand derartiger Betrachtungen
Probleme und Komplexität
	wird Cliquenproblem genannt
	Das Entscheidungsproblem zu einem Graphen G und einer natürlichen Zahl k zu entscheiden
	ob G eine Clique der Größe k enthält
	Das zugehörige Optimierungsproblem fragt nach der Cliquenzahl eines Graphen
	Das zugehörige Suchproblem fragt nach einer größten Clique
	Analog ist das Stabilitätsproblem über stabile Mengen definiert und das Knotenüberdeckungsproblem durch Knotenüberdeckungen
	Alle drei Probleme sind NP-vollständig
	Die zugehörigen Optimierungs und Suchprobleme sind NP-Äquivalent
	Die NP-Schwere des Stabilitätsproblems lässt sich dabei leicht durch Reduktion auf das Cliquenproblem zeigen
	indem man den Komplementgraphen bildet
	Die NP-Schwere des Knotenüberdeckungsproblems folgt aus dem Satz
	denn das Komplement einer kleinsten Knotenüberdeckung ist immer eine größte stabile Menge und umgekehrt
	dass die Stabilitätszahl eines Graphen immer der Anzahl Knoten eines Graphen abzüglich seiner Knotenüberdeckungszahl entspricht
	Für den Nachweis der NP-Schwere des Cliquenproblems existiert eine Reduktion auf 3-SAT
	König konnte jedoch schon 1931 zeigen
	dass in bipartiten Graphen die Knotenüberdeckungszahl der Paarungszahl entspricht
	gibt es aber einen polynomiellen Algorithmus
	Für das Problem eine größte Paarung zu finden
	In bipartiten Graphen lässt sich daher auch eine kleinste Knotenüberdeckung und eine größte stabile Menge in polynomieller Zeit berechnen
	wenn der Komplementgraph bipartit ist
	Eine größte Clique lässt sich entsprechend der obigen Reduktion in polynomieller Zeit berechnen
	dass Cliquenzahl
	Tatsächlich gilt sogar etwas stärker
	Stabilitätszahl und Knotenüberdeckungszahl in perfekten Graphen in polynomieller Zeit berechnet werden können
	Da die Farbzahl und die Cliquenzahl in solchen Graphen identisch sind
	ist auch ihre Farbzahl in polynomieller Zeit berechenbar.

Dieser Artikel basiert auf dem Artikel Knotenüberdeckungen, Cliquen und stabile Mengen aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.