Una copertura è un insieme di vertici che tocca almeno un estremo di ogni arco. Per verificarla, basta scorrere tutti gli archi.
Qui «complemento di S» significa i vertici che non hai scelto: T=V∖S. 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.
Perché funziona? Se S è indipendente, nessun arco ha entrambi gli estremi in S: almeno uno sta in T, dunque T 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 a una copertura di n−K vertici.
Complemento e collegamenti