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 dirigidoG = (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 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.
Note que este término tiene cierta ambigüedad, ya que en ocasiones se le llama «clan» a un tipo particular de cliques.[1]
Referencias
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 digital6 (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. ISBN978-84-7476-631-8. OCLC 871814053.
clique, teoría, grafos, clique, clique, pronunciado, klik, veces, traducido, desde, inglés, como, clan, nota, camarilla, grafo, dirigido, conjunto, vértices, todo, vértices, distintos, adyacentes, decir, existe, arista, conecta, otras, palabras, clique, subgra. En teoria de grafos un clique o una clique pronunciado klik a veces traducido desde el ingles como clan nota 1 o camarilla 2 C en un grafo no dirigido G V E es un conjunto de vertices C V tal que todo par de vertices distintos son adyacentes es decir existe una arista que los conecta En otras palabras un clique es un subgrafo en el que cada vertice esta conectado a todos los demas vertices del subgrafo Esto equivale a decir que el subgrafo de G inducido por C es un grafo completo El grafo completo K5 En un subgrafo como este los vertices forman un clique de tamano 5 El tamano de un clique es el numero de vertices que contiene El problema del clique que consiste en dado un grafo decidir si existe en el un clique con un tamano 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 Note que este termino tiene cierta ambiguedad ya que en ocasiones se le llama clan a un tipo particular de cliques 1 Referencias Editar Ramos Vidal I Ricaurte Quijano P 2015 Niveles de analisis y estrategias metodologicas en la ciencia de las redes Virtualis Revista de cultura digital 6 11 Wasserman Stanley Faust Katherine 2013 1994 Glosario de terminos de Analisis de Redes usados en la traduccion de Wasserman Faust Analisis de redes sociales Metodos y aplicaciones Madrid Centro de Investigaciones Sociologicas p 856 ISBN 978 84 7476 631 8 OCLC 871814053 Enlaces externos EditarWeisstein Eric W Clique En Weisstein Eric W ed MathWorld en ingles Wolfram Research Datos Q761631Obtenido de https es wikipedia org w index php title Clique amp oldid 132815368, wikipedia, wiki, leyendo, leer, libro, biblioteca,
