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). Das Finden einer Clique einer bestimmten Größe in einem Graphen ist ein NP-vollständiges Problem und somit auch in der Informationstechnik ein relevantes Forschungs- und Anwendungsgebiet.