Una copertura è un insieme di vertici che tocca almeno un estremo di ogni arco; per verificarla basta scorrere tutti gli archi.
Qui il complemento di S è l'insieme dei vertici che non hai scelto, T=V∖S, mentre il grafo e i suoi archi restano invariati. Sul cammino A-B-C-D, S={A,C} è indipendente e T={B,D} copre tutti e tre gli archi.
Se S è indipendente, nessun arco ha entrambi gli estremi in S: almeno uno sta in T, che dunque lo copre. Viceversa, se T copre tutti gli archi, non può esserci un arco con entrambi gli estremi in S. Su n vertici, scegliere K vertici indipendenti equivale quindi a trovare una copertura di n−K vertici.
Complemento e collegamenti