In matematica, uno spanning tree è un sottografo di un grafo non orientato che include tutti i vertici del grafico 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, uno spanning tree si forma ramificando da uno dei punti interni, motivo per cui è descritto come un albero.

Spiegazione dettagliata

Per visualizzare uno spanning tree, prima immagine un grafo non orientato: ad esempio, una raccolta casuale di punti collegati da linee. Le connessioni devono essere dirette; il che significa che puoi viaggiare in entrambe le direzioni sulle linee per spostarti da un punto all'altro. Ogni punto deve essere collegato al resto in qualche modo e ogni punto può avere più connessioni.

Uno spanning tree per questo grafico è un sottografo (un grafico che usa gli stessi punti) che tocca tutti i punti, sebbene non abbia bisogno di condividere tutte le stesse linee.

Grafico, termini di rete, protocollo Spanning Tree