Топ-100
Indietro

ⓘ 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 ..




Copertura degli spigoli
                                     

ⓘ 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 dellinsieme. Nellinformatica, 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.

                                     

1. 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 linsieme 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 ρ G {\displaystyle \rho G} è 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.

                                     

2. Algoritmi

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. 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.

Daltro canto, il problema collegato di trovare una copertura dei vertici piccolissima è un problema NP-difficile.

                                     
  • problema correlato della copertura degli spigoli delle cricche considera gli insiemi delle cricche che comprendono tutti gli spigoli di un dato grafo. Anch esso
  • complementare al vertex - cover è detto copertura degli spigoli o edge cover. In informatica, il problema di copertura tramite vertici è un problema NP - completo
  • abbinamento in inglese matching o insieme degli spigoli indipendenti in un grafo è un insieme bipartito di spigoli senza vertici comuni. Può trattarsi anche
  • alcuni esagoni di questa impossibile copertura con pentagoni. Se il numero di facce non varia, il numero di spigoli e di vertici diminuisce: per ogni pentagono
  • in un insieme indipendente massimo uguaglia il numero di spigoli in una copertura degli spigoli minima questo è il teorema di König. Un insieme indipendente
  • volta a spigolo o volta a quadro è, in architettura, una tipologia di copertura a volta. La volta a stella è, rispetto alle altre coperture a volta
  • 1 spigoli G è aciclico e possiede n 1 spigoli Si può definire albero un grafo connesso tale che eliminando uno qualsiasi dei suoi spigoli si perde
  • H, xy è uno spigolo di H se e solo se xy è uno spigolo di G. In altre parole, H è un sottografo indotto di G se ha esattamente gli spigoli che appaiono
  • rivestita completamente in marmo bianco dei Monti Pisani e su ciascuno degli otto spigoli reca impresso il nome del vento ad esso corrispondente Mezzodì, Iscilocho
  • abside polilobata. La copertura è a spigolo alla leccese nelle navate laterali mentre la navata centrale possiede una copertura a volta piana, realizzata
  • fatta defluire in prossimità degli spigoli oppure ogni 10 metri circa all interno dei tubi pluviali. Il diametro degli stessi varia dai 60 ai 120 mm