Cliques Máximos

Cliques Máximos
En un grafo no dirigido un Clique es un subconjunto de vértices dado que por cada dos hay una conexión entre estos vértices además cada vértice es adyacente a otros dos. Encomputación los cliques han sido estudiados para encontrar si hay un clique, dada una distancia en un grafo (Problema del clique). Un máximo clique es aquel que no se puede extender añadiendo más vértices.Reportar el máximo clique de un grafo
En los problemas donde los grafos son la forma más fácil y natural de modelar objetos y sus interacciones, surge el problema de reportar cliques. Aplicaciones deesto se pueden dar en diseño de redes, ciencias sociales y biológicas.
La salida de los algoritmos de enumeración del máximo clique pueden crecer exponencialmente. Los algoritmos generales noorientados a grafos específicos se dividen en dos, los greedy (algoritmos de Bron-Kerbosch), también se puede recurrir a algoritmos de salida sensitiva como Tsukiyama et al o multiplicación de matrices.
Enla publicación de Tsukiyama et al, los resultados de la sensibilidad son probados limitando el tiempo del primer clique al tiempo requerido para añadir otro.
Esta comprobado que todos los máximoscliques de n vértices de un grafo pueden enumerarse usando un espacio n2, con un retardo de O(M(n)) con M(n) el costo de multiplicar dos nxn matrices.
No
Si
Si
No
Fin
i>0 && i<=k
R,P, X
P=Φ && X= Φ vacios?
R Máximo clique
X = X Unión { ui }

P = P – { ui }
Rnew = R Unión { ui }
Pnew = P Intersección N[ ui ]
Xnew = X Intersección N[ui ]

Bron-Kerbosch V1Inicio

Algoritmo Bron-Kerbosch Versión 1

Es un algoritmo recursivo, basado en el backtracking, busca los cliques máximos dado un grafo. u es un nodo, y N(u) el vecindario. Dados tres conjuntos, R, Py X, encuentra el clique máximo que incluye todos los vértices en R, algunos en P y ninguno en X. En las llamadas recursivas P y X están restringidos a los vértices que se forman cuando se añade un...