Clique
En teoria de grafos, un clique (o «una clique», pronunciat /klik/), a voltes traduït des del anglés com a clan[nota 1] o caçola,[2] C, en un grafo no dirigit G = (V, I), és un conjunt de vèrtiços, C ⊆ V, tal que tot parell de vèrtiços distints són adjacents, és dir, existix una aresta que els conecta. Note's que per definició un clique és un conjunt de vèrtiços, no un subgrafo. Ya que en el subgrafo de G induït per C qualssevol dos vèrtiços són adjacents, dit subgrafo és un grafo complet.
El tamany d'un clique és el número de vèrtiços que conté.
El problema del clique (que rep com a entrada un grafo G i un sancer positiu k, i pregunta si existix un clan de tamany k en G), és NP-complet,[3] i és de fet un dels vintiun problemes NP-complets de Karp.
La noció dual a un clique és un conjunt independent, en el sentit de que cada clique correspon a un conjunt independent del grafo complement.
Notes
[editar | editar còdic]- ↑ (2015).Virtualis: Revista de cultura digital.6(11)
- ↑ (2013) «Glossari de térmens d'Anàlisis de Rets usats en la traducció de Wasserman-Faust», Anàlisis de rets socials: Métodos i aplicacions, Madrit: Centre d'Investigacions Sociològiques, p. 856. OCLC 871814053. ISBN 978-84-7476-631-8.
- ↑ Garey; Johnson, David S. (1979). Computers and intractability: a guide to the theory of NP-completeness, W. H. Freeman. ISBN 978-0-7167-1044-8.
Referències
[editar | editar còdic]
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Clique» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.
Erro en la cita: Existixen etiquetes <ref> per a un grup nomenat "nota", pero no es trobà una etiqueta <references group="nota"/>