Clique (Graphentheorie)
Eine Clique bezeichnet in der Graphentheorie
eine Teilmenge von Knoten in einem ungerichteten Graphen, bei der jedes
Knotenpaar durch eine Kante verbunden ist. Zu entscheiden, ob ein Graph eine
Clique einer bestimmten Mindestgröße enthält, wird Cliquenproblem genannt
und gilt, wie das Finden von größten Cliquen, als algorithmisch schwierig (NP-vollständig).
Definitionen
Sei 
ein ungerichteter
Graph
ohne Mehrfachkanten und 
eine Teilmenge von 
.
Eine Clique ist eine Teilmenge
von ,
die einen vollständigen
Teilgraphen induziert. Ist
eine Clique, so gilt also für den Teilgraph 
,
wobei 
alle Kanten
aus 
enthält, die zwei Knoten in
verbinden, dass je zwei beliebige verschiedene Knoten 
und 
aus
durch eine Kante miteinander verbunden sind.
Eine Clique
von 
nennt man maximal, wenn man keinen weiteren Knoten
aus
zu
hinzufügen kann, so dass
zusammen mit
eine Clique ist. Gibt es in
keine Clique, die mehr Elemente als
enthält, so nennt man
größte Clique. Die Anzahl der Elemente einer größten Clique nennt man
Cliquenzahl.
Als Cliquenüberdeckung von
der Größe 
bezeichnet man eine Partition
der Knotenmenge 
in
paarweise disjunkte Cliquen 
.
Aus den Cliquen eines Graphen ergibt sich dessen Cliquen-Graph.
Gerichtete Graphen oder solche mit Mehrfachkanten sind nicht Gegenstand derartiger Betrachtungen, da es nicht auf die Richtung oder Vielfachheit der Kanten ankommt.
Eigenschaften
Zu jeder Clique eines Graphen gibt es eine stabile Menge im Komplementgraphen.
Probleme und Komplexität
Das Entscheidungsproblem zu
einem Graphen
und einer natürlichen Zahl
zu entscheiden, ob
eine Clique der Größe mindestens
enthält, wird Cliquenproblem
(CLIQUE) genannt. Das zugehörige Optimierungsproblem
fragt nach der Cliquenzahl eines Graphen. Das zugehörige Suchproblem fragt nach
einer größten Clique. Diese drei Probleme sind polynomiell äquivalent.
Das Cliquenproblem ist eines von Karps 21 NP-vollständigen Problemen. Die zugehörigen Optimierungs- und Suchprobleme sind NP-äquivalent. Für den Nachweis der NP-Schwere des Cliquenproblems existiert eine Reduktion von 3-SAT auf das Cliquenproblem.
Eine größte Clique lässt sich jedoch in polynomieller Zeit berechnen, wenn der Komplementgraph bipartit ist. Tatsächlich gilt sogar etwas stärker, dass die Cliquenzahl in perfekten Graphen in polynomieller Zeit berechnet werden kann. Da die chromatische Zahl und die Cliquenzahl in solchen Graphen identisch sind, ist auch ihre chromatische Zahl in polynomieller Zeit berechenbar. Die Berechnung einer maximalen Clique gelingt bereits mit einem einfachen Greedy-Algorithmus.
Software
Algorithmen zum Finden und Manipulieren von Cliquen sind in der freien Python-Bibliothek NetworkX implementiert.
Wikipedia.de
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 04.11. 2020