Problema de la clique

En complejidad computacional, el problema de Clique o problema de la liga de amigos es un problema NP-completo según la Teoría de la complejidad computacional.

Definición

Dado un grafo G=(N,A), decimos que G tiene un clique de tamaño k si existe un subgrafo G' = (N',A') de G tal que N' es subconjunto de N, |N'|=k y A'=N'×N', vale decir, todos sus vértices están conectados entre ellos. En el grafo de la derecha, los vértices 1, 2 y 5 forman un clique porque cada uno tiene un arco que le une a los otros. En cambio, los vértices 2, 3 y 4 no, dado que 2 y 4 no son adyacentes.


6n-graf-clique.svg

El problema de clique es un problema de decisión para determinar cuándo un grafo contiene un clique de al menos un tamaño k. Una vez que tenemos k o más vértices que forman un clique, es trivial verificar que lo son, por eso es un problema NP. El correspondiente problema de optimización, consiste en encontrar un clique de tamaño máximo en un grafo (un subgrafo completo de tamaño máximo). Este problema se puede enunciar como un problema de decisión si la pregunta que se hace es saber si existe un clique de tamaño k en el grafo.


Other Languages