DAA - Max Cliques

Dans un graphe non orienté, un cliqueest un sous-graphique complet du graphique donné. Sous-graphe complet signifie que tous les sommets de ce sous-graphe sont connectés à tous les autres sommets de ce sous-graphe.

Le problème Max-Clique est le problème de calcul de trouver la clique maximale du graphe. Max clique est utilisé dans de nombreux problèmes du monde réel.

Considérons une application de réseautage social, où les sommets représentent le profil des personnes et les arêtes représentent une connaissance mutuelle dans un graphique. Dans ce graphique, une clique représente un sous-ensemble de personnes qui se connaissent toutes.

Pour trouver une clique maximale, on peut systématiquement inspecter tous les sous-ensembles, mais ce type de recherche par force brute est trop long pour les réseaux comportant plus de quelques dizaines de sommets.

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

Une analyse

Le problème Max-Clique est un algorithme non déterministe. Dans cet algorithme, nous essayons d'abord de déterminer un ensemble dek des sommets distincts puis nous essayons de tester si ces sommets forment un graphe complet.

Il n'y a pas d'algorithme déterministe polynomial pour résoudre ce problème. Ce problème est NP-Complete.

Exemple

Jetez un œil au graphique suivant. Ici, le sous-graphe contenant les sommets 2, 3, 4 et 6 forme un graphe complet. Par conséquent, ce sous-graphique est unclique. Comme il s'agit du sous-graphique complet maximum du graphique fourni, c'est un4-Clique.