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. Nótese que por definición un clique es un conjunto de vértices, no un subgrafo. Ya que en el subgrafo de G inducido por C cualesquiera dos vértices son adyacentes, dicho subgrafo es un grafo completo.
El tamaño de un clique es el número de vértices que contiene.
El problema del clique (que recibe como entrada un grafo G y un entero positivo k, y pregunta si existe un clan de tamaño k en G), es NP-completo,[3] y es de hecho uno de los veintiún problemas NP-completos de Karp.
La noción dual a un clique es un conjunto independiente, en el sentido de 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.
- ↑ Garey, Michael R.; Johnson, David S. (1979). Computers and intractability: a guide to the theory of NP-completeness. A Series of books in the mathematical sciences. W. H. Freeman. ISBN 978-0-7167-1044-8. Consultado el 10 de enero de 2026.
Enlaces externos
[editar]- Weisstein, Eric W. «Clique». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
| Control de autoridades |
|
|---|
Datos: Q761631