Clique

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
El grafo completo K5. En un subgrafo como éste, los vértices forman un clan de tamaño 5.

En teoría de grafos, un clan, también conocido como un clique (o «una clique», pronunciado /klik/), 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 clan 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.

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

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

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

Origen del nombre[editar]

El término proviene de la palabra inglesa y francesa clique, que define a un grupo de personas que comparten intereses en común. En esta analogía, las personas serían los vértices; las relaciones de interés, las aristas; y el hecho de que todas compartan un mismo interés, el grafo completo, es decir, el clan en sí.

Referencias[editar]