Clique
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, C ⊆ V, 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.
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 que cada clique corresponde a un conjunto independiente del grafo complemento.
Notas editar
Referencias editar
- ↑ Ramos-Vidal, I.; Ricaurte Quijano, P. (2015). «Niveles de análisis y estrategias metodológicas en la ciencia de las redes». Virtualis: Revista de cultura digital 6 (11).
- ↑ Wasserman, Stanley; Faust, Katherine (2013) [1994]. «Glosario de términos de Análisis de Redes usados en la traducción de Wasserman-Faust». Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. p. 856. ISBN 978-84-7476-631-8. OCLC 871814053.
Enlaces externos editar
- Weisstein, Eric W. «Clique». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
Datos: Q761631
