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 nel tempo polinomiale.
Definizione
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 abbinamento. In particolare, esso è un abbinamento perfetto: un abbinamento M in cui ciascun vertice è incidente con esattamente un vertice in M. Un abbinamento perfetto è sempre una copertura minima degli spigoli.
Esempi
- 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).
Note
Bibliografia
- (EN) Eric W. Weisstein, Edge Cover, in MathWorld, Wolfram Research.
- 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
- 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.
