DAA - Max camarillas

En un gráfico no dirigido, un cliquees un subgráfico completo del gráfico dado. El sub-gráfico completo significa que todos los vértices de este sub-gráfico están conectados a todos los demás vértices de este sub-gráfico.

El problema de Max-Clique es el problema de cálculo de encontrar la camarilla máxima de la gráfica. Max clique se utiliza en muchos problemas del mundo real.

Consideremos una aplicación de redes sociales, donde los vértices representan el perfil de las personas y los bordes representan el conocimiento mutuo en un gráfico. En este gráfico, una camarilla representa un subconjunto de personas que se conocen entre sí.

Para encontrar una camarilla máxima, se pueden inspeccionar sistemáticamente todos los subconjuntos, pero este tipo de búsqueda de fuerza bruta consume demasiado tiempo para las redes que comprenden más de unas pocas docenas de vértices.

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

Análisis

El problema de Max-Clique es un algoritmo no determinista. En este algoritmo, primero intentamos determinar un conjunto dek vértices distintos y luego tratamos de probar si estos vértices forman un gráfico completo.

No existe un algoritmo determinista de tiempo polinomial para resolver este problema. Este problema es NP-Complete.

Ejemplo

Eche un vistazo al siguiente gráfico. Aquí, el sub-gráfico que contiene los vértices 2, 3, 4 y 6 forma un gráfico completo. Por tanto, este subgrafo es unclique. Como este es el subgráfico máximo completo del gráfico proporcionado, es un4-Clique.