Copertura degli spigoli

Da Wikipedia, l'enciclopedia libera.

Nella teoria dei grafi, una copertura degli spigoli di un grafo è un insieme di spigoli tale che ogni vertice del grafo è incidente ad almeno uno spigolo dell'insieme. Nell'informatica, il problema della copertura minima degli spigoli è il problema di trovare una copertura degli spigoli di dimensione minima. È un problema di ottimizzazione che appartiene alla classe dei problemi di copertura e può essere risolto nel tempo polinomiale.

Definizione[modifica | modifica wikitesto]

Formalmente, la copertura degli spigoli di un grafo G è un insieme di spigoli C tale che ogni vertice in G è incidente con almeno uno spigolo in C. Si dice che l'insieme C copre i vertici di G. La figura seguente mostra esempi di coperture degli spigoli in due grafi.

Edge-cover.svg

Una copertura minima degli spigoli è una copertura degli spigoli della dimensione più piccola possibile. Il numero delle coperture degli spigoli \rho(G) è la dimensione della copertura minima degli spigoli. La figura seguente mostra esempi di coperture minime degli spigoli.

Minimum-edge-cover.svg

Si noti che la figura a destra non è soltanto una copertura sugli spigoli, ma anche un accoppiamento. In particolare, esso è un accoppiamento perfetto: un accoppiamento M in cui ciascun vertice è incidente con esattamente un vertice in M. Un accoppiamento perfetto è sempre una copertura minima degli spigoli.

Esempi[modifica | modifica wikitesto]

  • L'insieme di tutti gli spigoli è una copertura degli spigoli, assumendo che non ci siano vertici di grado 0.

Algoritmi[modifica | modifica wikitesto]

Una copertura degli spigoli piccolissima può essere trovata nel tempo polinomiale trovando un accoppiamento massimo ed estendendolo "golosamente" (cioè mediante un "algoritmo goloso") così che tutti i vertici siano coperti.[1][2] Nella figura seguente, un accoppiamento massimo è segnato in rosso; gli spigoli supplementari che sono stati aggiunti per coprire i nodi non accoppiati sono segnati in blu. (La figura a destra mostra un grafo in cui un accopppiamento massimo è un accoppiamento perfetto; quindi copre già tutti i vertici e non sono stati necessari spigoli supplementari.)

Minimum-edge-cover-from-maximum-matching.svg

D'altro canto, il problema collegato di trovare una copertura dei vertici piccolissima è un problema NP-difficile.[1]

Note[modifica | modifica wikitesto]

  1. ^ a b Garey & Johnson (1979), p. 79, usa la copertura degli spigoli e la copertura dei vertici come esempio di una coppia di problemi simili, uno dei quali può essere risolto nel tempo polinomiale mentre l'altro è NP-difficile. Vedi anche p. 190.
  2. ^ Eugene L. Lawler, Combinatorial optimization: networks and matroids, Dover Publications, 2001, pp. 222–223, ISBN 978-0-486-41453-9.

Bibliografia[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

  • Copertura dei vertici
  • Copertura degli insiemi – il problema della copertura degli spigoli è un caso speciale del problema della copertura degli insiemi: gli elementi dell'universo sono i vertici, e ogni sottoinsieme copre esattamente due elementi.
Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica