Spanning Tree e Minimum Spanning Tree

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:

1. Algoritmo di Prim
2. 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.