Metraipolis › archive › dc_1620989d0f4e
Cricca (teoria dei grafi) — Wikipedia
- Source
- Wikipedia (it)
- Original
- https://it.wikipedia.org/wiki/Cricca_(teoria_dei_grafi)
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-06T09:24:01.431Z
- SHA-256 of the archived text
0cf79f43139a12a928289af16d6f949188223da9d9c2bb59b70b641980ecd671- Stable URL of this page
https://metraipolis.com/documento/dc_1620989d0f4e
How to cite
Cricca (teoria dei grafi) — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Cricca_(teoria_dei_grafi) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_1620989d0f4e (Metraipolis archive dc_1620989d0f4e, sha256 0cf79f43139a12a928289af16d6f949188223da9d9c2bb59b70b641980ecd671)
BibTeX
@misc{dc1620989d0f4e,
title = {Cricca (teoria dei grafi) — Wikipedia},
howpublished = {Wikipedia (it)},
url = {https://it.wikipedia.org/wiki/Cricca_(teoria_dei_grafi)},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_1620989d0f4e; sha256 0cf79f43139a12a928289af16d6f949188223da9d9c2bb59b70b641980ecd671},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Cricca_(teoria_dei_grafi). Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In teoria dei grafi, una cricca (o clique) è un insieme V di vertici in un grafo non orientato G, tale che, per ogni coppia di vertici in V, esiste un arco che li collega. In modo equivalente, si potrebbe dire che il sottografo indotto da V è un grafo completo. La dimensione di una cricca è definita come il numero di vertici che contiene. Alcuni autori chiamano cricca ogni sottografo completo che sia di dimensione massima. Il problema di trovare, se esiste, una cricca di una dimensione fissata all'interno di un grafo è detto problema della cricca, ed è NP-completo. Il concetto complementare a quello di cricca è l'insieme indipendente, nel senso che a ogni cricca corrisponde un insieme indipendente nel grafo complemento. Sebbene lo studio dei sottografi completi risalga almeno alla riformulazione della teoria dei grafi con la teoria di Ramsey da parte di Erdős & Szekeres (1935), il termine "cricca" viene da Luce & Perry (1949), che utilizzarono sottografi completi nelle reti sociali per modellare le cricche (in inglese cliques) di persone, vale a dire gruppi ristretti di persone che si conoscono tutte fra di loro. Le cricche hanno molte applicazioni nelle scienze e particolarmente in bioinformatica. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoria dei grafi»). Fonte: Wikipedia in italiano, voce «Cricca (teoria dei grafi)» — https://it.wikipedia.org/wiki/Cricca_(teoria_dei_grafi) Wikidata Q761631 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q761631 Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Cricca_(teoria_dei_grafi)?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 148136630, consultata il 2026-10-06T08:23:25.822Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: a8435cee6e3642be3de4b2ec1321bd1e25ecb140bf93d91f9441ac6b93ddbf43