albero di copertura

In matematica, uno spanning tree è un sottografo di un grafo non orientato che include tutti i vertici del grafo non orientato. È uno strumento fondamentale utilizzato per risolvere problemi complessi in matematica come il problema della mappa a quattro colori e il problema del commesso viaggiatore. Di solito, un albero ricoprente formato ramificandosi da uno dei punti interni, motivo per cui viene descritto come un albero.

Spiegazione dettagliata

Per visualizzare un albero ricoprente, prima immagina un grafo non orientato: per esempio, una raccolta casuale di punti collegati da linee. I collegamenti devono essere non diretti; il che significa che puoi viaggiare in entrambe le direzioni sulle linee per andare da un punto all’altro. Ogni punto deve connettersi in qualche modo al resto e ogni punto può avere più connessioni.

Uno spanning tree per questo grafico è qualsiasi sottografo (un grafico che utilizza gli stessi punti) che tocca tutti i punti, ma non ha bisogno di condividere le stesse linee.