Top Qs
Línea de tiempo
Chat
Contexto

Clique

De Wikipedia, la enciclopedia libre

Clique
Remove ads

En teoría de grafos, un clique (o «una clique», pronunciado /klik/), a veces traducido desde el inglés como clan[nota 1] o camarilla,[2] C, en un grafo no dirigido G = (V, E) es un conjunto de vértices, CV, tal que todo par de vértices distintos son adyacentes, es decir, existe una arista que los conecta. En otras palabras, un clique es un subgrafo en el que cada vértice está conectado a todos los demás vértices del subgrafo. Esto equivale a decir que el subgrafo de G inducido por C es un grafo completo.

Thumb
El grafo completo K5. En un subgrafo como este, los vértices forman un clique de tamaño 5.

El tamaño de un clique es el número de vértices que contiene.

El problema del clique (que consiste en, dado un grafo, decidir si existe en él un clique con un tamaño particular), es NP-completo.

Lo opuesto de un clique es un conjunto independiente, en el sentido de que cada clique corresponde a un conjunto independiente del grafo complemento.

Remove ads

Notas

  1. Nótese que este término tiene cierta ambigüedad, ya que en ocasiones se le llama «clan» a un tipo particular de cliques.[1]

Referencias

Enlaces externos

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads