Copertura dei vertici

Questa voce sull'argomento teoria dei grafi è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

In teoria dei grafi, si dice copertura dei vertici o copertura tramite vertici (in inglese vertex cover) o copertura per nodi, un sottoinsieme ${\displaystyle S}$ dei nodi di un grafo ${\displaystyle G=(V,E)}$ tale che tutti gli archi in ${\displaystyle E}$ abbiano almeno un estremo in ${\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.

• (EN) Eric W. Weisstein, Copertura dei vertici, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica