Visualizza wikitesto di Copertura dei vertici

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

== Collegamenti esterni ==
* {{Collegamenti esterni}}

{{Portale|matematica}}

[[Categoria:Teoria dei grafi]]