Formulação do Problema
Um clique em un grafo não orientado G=(V,E) é um subconjuntodo conjunto de vértices C subconjunto de V, tal que para cada par de vértices u e v de C, existe uma aresta {u,v} que pertence a E.
Clique Maximal
Um clique maximal é um clique que não é subconjunto de outro clique, ou seja, é um subconjunto c de V que é clique em G e que não exista um outro subconjunto C+{v} subconjunto de V que também seja clique em G, para c que pertence a V.
Em outras palabras o problema de hallar uma clique maior em G pertence a clase NP dificil; tem muitas aplicações praticas tais como as redes sociais.
No hay comentarios:
Publicar un comentario