In questo tutorial imparerai lo spanning tree e lo spanning tree minimo con l'aiuto di esempi e figure.
Prima di conoscere gli spanning tree, dobbiamo comprendere due grafici: grafici non orientati e grafici connessi.
Un grafico non orientato è un grafico in cui i bordi non puntano in alcuna direzione (cioè i bordi sono bidirezionali).
Grafico non diretto
Un grafo connesso è un grafo in cui c'è sempre un percorso da un vertice a qualsiasi altro vertice.
Grafico connesso
Spanning tree
Uno spanning tree è un sottografo di un grafo connesso non orientato, che include tutti i vertici del grafo con un numero minimo possibile di bordi. Se un vertice viene perso, non è uno spanning tree.
Ai bordi possono o non possono essere assegnati pesi.
Il numero totale di spanning tree con nvertici che possono essere creati da un grafo completo è uguale a .n(n-2)
Se lo abbiamo n = 4, il numero massimo di possibili spanning tree è uguale a . Pertanto, 16 spanning tree possono essere formati da un grafo completo con 4 vertici.44-2 = 16
Esempio di uno spanning tree
Comprendiamo lo spanning tree con gli esempi di seguito:
Lascia che il grafico originale sia:
Grafico normale
Alcuni dei possibili spanning tree che possono essere creati dal grafico sopra sono:
Uno spanning tree 
Uno spanning tree 
Uno spanning tree 
Uno spanning tree 
Uno spanning tree 
Uno spanning tree
Spanning Tree minimo
Uno spanning tree minimo è uno spanning tree in cui la somma del peso dei bordi è la più minima possibile.
Esempio di uno spanning tree
Comprendiamo la definizione di cui sopra con l'aiuto dell'esempio seguente.
Il grafico iniziale è:
Grafico ponderato
I possibili spanning tree dal grafico sopra sono:
Spanning tree minimo - 1 
Spanning tree minimo - 2 
Spanning tree 
minimo - 3 Spanning tree minimo - 4
L'albero di copertura minimo dagli alberi di copertura sopra è:
Albero di copertura minimo
Lo spanning tree minimo da un grafico si trova utilizzando i seguenti algoritmi:
- Algoritmo di Prim
- Algoritmo di Kruskal
Applicazioni Spanning Tree
- Protocollo di routing di rete di computer
- Analisi di gruppo
- Pianificazione della rete civile
Applicazioni minime di spanning tree
- Per trovare i percorsi nella mappa
- Progettare reti come reti di telecomunicazione, reti di approvvigionamento idrico e reti elettriche.
