DAA - Max Cliquen

In einem ungerichteten Diagramm a cliqueist ein vollständiger Untergraph des gegebenen Graphen. Vollständiger Untergraph bedeutet, dass alle Scheitelpunkte dieses Untergraphen mit allen anderen Scheitelpunkten dieses Untergraphen verbunden sind.

Das Max-Clique-Problem ist das Rechenproblem beim Finden der maximalen Clique des Graphen. Max Clique wird in vielen realen Problemen eingesetzt.

Betrachten wir eine Social-Networking-Anwendung, bei der Eckpunkte das Profil von Personen und die Kanten die gegenseitige Bekanntschaft in einem Diagramm darstellen. In diesem Diagramm repräsentiert eine Clique eine Untergruppe von Personen, die sich alle kennen.

Um eine maximale Clique zu finden, kann man systematisch alle Teilmengen untersuchen, aber diese Art der Brute-Force-Suche ist für Netzwerke mit mehr als ein paar Dutzend Eckpunkten zu zeitaufwändig.

Algorithm: Max-Clique (G, n, k) 
S := Φ 
for i = 1 to k do 
   t := choice (1…n)  
   if t Є S then 
      return failure 
   S := S ∪ t  
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do 
   if (i, j) is not a edge of the graph then  
      return failure 
return success

Analyse

Das Max-Clique-Problem ist ein nicht deterministischer Algorithmus. In diesem Algorithmus versuchen wir zunächst, eine Menge von zu bestimmenk verschiedene Scheitelpunkte und dann versuchen wir zu testen, ob diese Scheitelpunkte einen vollständigen Graphen bilden.

Es gibt keinen zeitdeterministischen Polynomalgorithmus, um dieses Problem zu lösen. Dieses Problem ist NP-vollständig.

Beispiel

Schauen Sie sich die folgende Grafik an. Hier bildet der Untergraph mit den Eckpunkten 2, 3, 4 und 6 einen vollständigen Graphen. Daher ist dieser Untergraph aclique. Da dies das maximal vollständige Unterdiagramm des bereitgestellten Diagramms ist, ist es a4-Clique.