Copertura dei vertici
Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Edge cover)
In teoria dei grafi, si dice copertura dei vertici o copertura tramite vertici (in inglese edge cover) un sottoinsieme S dei nodi di un grafo G=(V,E) tale che tutti gli archi in E abbiano almeno un estremo in 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.
 Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica |
