Metraipolis › archive › dc_ffceafcdb725

Copertura dei vertici — Wikipedia

Source: Wikipedia (it)
Original: https://it.wikipedia.org/wiki/Copertura_dei_vertici
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-07T15:37:28.551Z
SHA-256 of the archived text: 3c2073376365fad4236d264dc036c89e509d2f5b2595fbe75984c7ee3c668074
Stable URL of this page: https://metraipolis.com/documento/dc_ffceafcdb725

How to cite

Copertura dei vertici — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Copertura_dei_vertici (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_ffceafcdb725 (Metraipolis archive dc_ffceafcdb725, sha256 3c2073376365fad4236d264dc036c89e509d2f5b2595fbe75984c7ee3c668074)

BibTeX

@misc{dcffceafcdb725,
  title = {Copertura dei vertici — Wikipedia},
  howpublished = {Wikipedia (it)},
  url = {https://it.wikipedia.org/wiki/Copertura_dei_vertici},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_ffceafcdb725; sha256 3c2073376365fad4236d264dc036c89e509d2f5b2595fbe75984c7ee3c668074},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Copertura_dei_vertici. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In teoria dei grafi, si dice copertura dei vertici o copertura tramite vertici (in inglese vertex cover) o copertura per nodi, un sottoinsieme S {\displaystyle S} dei nodi di un grafo G = ( V , E ) {\displaystyle G=(V,E)} tale che tutti gli archi in E {\displaystyle E} abbiano almeno un estremo in S {\displaystyle S} . Il problema di determinare la più piccola copertura tramite vertici di un grafo (detto problema di copertura dei vertici) è un noto problema di ottimizzazione, studiato in teoria della complessità come esempio di problema NP-completo.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «ottimizzazione (matematica)»).
Fonte: Wikipedia in italiano, voce «Copertura dei vertici» — https://it.wikipedia.org/wiki/Copertura_dei_vertici
Wikidata Q11515519 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q11515519
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Copertura_dei_vertici?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 135230571, consultata il 2026-10-07T15:09:14.223Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: f7650741134eede7db498c5c5ac160cbc78c553a5da15d94cdd48904611c7885