Copertura degli spigoli
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 in 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.
Una copertura minima degli spigoli è una copertura degli spigoli della dimensione più piccola possibile. Il numero delle coperture degli spigoli è la dimensione della copertura minima degli spigoli. La figura seguente mostra esempi di coperture minime degli spigoli.
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.
- Il grafo bipartito completo Km,n ha numero di coperture degli spigoli max(m, n).
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 accoppiamento massimo è un accoppiamento perfetto; quindi copre già tutti i vertici e non sono stati necessari spigoli supplementari.)
D'altro canto, il problema collegato di trovare una copertura dei vertici piccolissima è un problema NP-difficile.[1]
Note
[modifica | modifica wikitesto]- ^ 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.
- ^ Eugene L. Lawler, Combinatorial optimization: networks and matroids, Dover Publications, 2001, pp. 222–223, ISBN 978-0-486-41453-9.
Bibliografia
[modifica | modifica wikitesto]- Michael R. Garey e David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, ISBN 0-7167-1045-5.
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.
Collegamenti esterni
[modifica | modifica wikitesto]- (EN) Eric W. Weisstein, Copertura degli spigoli, su MathWorld, Wolfram Research.
