ALBERO DI COPERTURA - TUTORIAL DS

In questo articolo discuteremo dello spanning tree e dello spanning tree minimo. Ma prima di passare direttamente allo spanning tree, vediamo prima una breve descrizione del grafico e delle sue tipologie.

Grafico

Un grafico può essere definito come un gruppo di vertici e spigoli per connettere questi vertici. I tipi di grafici sono indicati come segue:

Grafico non orientato:Un grafo non orientato è un grafo in cui tutti gli spigoli non puntano in alcuna direzione particolare, cioè non sono unidirezionali; sono bidirezionali. Può anche essere definito come un grafo con un insieme di vertici V e un insieme di spigoli E, ciascun spigolo collega due vertici diversi.Grafico connesso:Un grafo connesso è un grafo in cui esiste sempre un percorso da un vertice a qualsiasi altro vertice. Un grafo è connesso se possiamo raggiungere qualsiasi vertice da qualsiasi altro vertice seguendo i bordi in entrambe le direzioni.Grafico diretto:I grafi diretti sono anche conosciuti come digrafi. Un grafo è un grafo diretto (o digrafo) se tutti gli spigoli presenti tra eventuali vertici o nodi del grafo sono diretti o hanno una direzione definita.

Passiamo ora all'argomento spanning tree.

Cos'è uno spanning tree?

Uno spanning tree può essere definito come il sottografo di un grafo connesso non orientato. Include tutti i vertici insieme al minor numero possibile di spigoli. Se manca un vertice, non è uno spanning tree. Uno spanning tree è un sottoinsieme del grafico che non ha cicli e inoltre non può essere disconnesso.

Uno spanning tree è costituito da (n-1) bordi, dove 'n' è il numero di vertici (o nodi). Ai bordi dello spanning tree possono essere assegnati o meno pesi. Tutti i possibili spanning tree creati dal grafo dato G avrebbero lo stesso numero di vertici, ma il numero di archi nello spanning tree sarebbe uguale al numero di vertici nel grafo dato meno 1.

Un grafo completo non orientato può avere N^n-2 numero di alberi spanning dove N è il numero di vertici nel grafico. Supponiamo, se n = 5 , sarebbe il numero massimo di spanning tree possibili 5^5-2= 125.

Applicazioni dello spanning tree

Fondamentalmente, uno spanning tree viene utilizzato per trovare un percorso minimo per connettere tutti i nodi del grafico. Alcune delle applicazioni comuni dello spanning tree sono elencate come segue:

Analisi di gruppo
Pianificazione della rete civile
Protocollo di routing della rete di computer

Ora comprendiamo lo spanning tree con l'aiuto di un esempio.

Esempio di albero di copertura

Supponiamo che il grafico sia:

Come discusso in precedenza, uno spanning tree contiene lo stesso numero di vertici del grafico, il numero di vertici nel grafico sopra è 5; pertanto, lo spanning tree conterrà 5 vertici. Gli spigoli nello spanning tree saranno uguali al numero di vertici nel grafico meno 1. Quindi, ci saranno 4 spigoli nello spanning tree.

Alcuni dei possibili spanning tree che verranno creati dal grafico sopra sono forniti come segue:

Proprietà dello spanning tree

Alcune delle proprietà dello spanning tree sono date come segue:

Possono esserci più alberi di copertura di un grafo connesso G.
Uno spanning tree non ha cicli o loop.
Un albero di copertura lo è minimamente connesso, quindi rimuovere un bordo dall'albero renderà il grafico disconnesso.
Un albero di copertura lo è massimamente aciclico, quindi aggiungendo un bordo all'albero creerai un ciclo.
Può esserci un massimo N^n-2 numero di spanning tree che possono essere creati da un grafo completo.
Un albero di copertura ha n-1 bordi, dove 'n' è il numero di nodi.
Se il grafo è un grafo completo, allora lo spanning tree può essere costruito rimuovendo i bordi massimi (e-n+1), dove 'e' è il numero di bordi e 'n' è il numero di vertici.

Quindi, uno spanning tree è un sottoinsieme del grafo connesso G e non esiste uno spanning tree di un grafo disconnesso.

Albero di copertura minimo

Un albero di copertura minimo può essere definito come l'albero di copertura in cui la somma dei pesi degli archi è minima. Il peso dello spanning tree è la somma dei pesi dati ai bordi dello spanning tree. Nel mondo reale, questo peso può essere considerato come la distanza, il carico di traffico, la congestione o qualsiasi valore casuale.

Esempio di albero di copertura minimo

Comprendiamo l'albero di copertura minimo con l'aiuto di un esempio.

La somma dei bordi del grafico sopra è 16. Ora, alcuni dei possibili spanning tree creati dal grafico sopra sono:

Quindi, lo spanning tree minimo selezionato dagli spanning tree sopra per il dato grafico ponderato è:

Applicazioni dell'albero di copertura minimo

Le applicazioni dello spanning tree minimo sono date come segue:

L'albero di copertura minimo può essere utilizzato per progettare reti di approvvigionamento idrico, reti di telecomunicazioni e reti elettriche.
Può essere utilizzato per trovare percorsi nella mappa.

Algoritmi per l'albero di copertura minimo

Un albero di copertura minimo può essere trovato da un grafico ponderato utilizzando gli algoritmi indicati di seguito:

Algoritmo di Prim
Algoritmo di Kruskal

Vediamo una breve descrizione di entrambi gli algoritmi sopra elencati.

Algoritmo di Prim - È un algoritmo avido che inizia con uno spanning tree vuoto. Viene utilizzato per trovare l'albero di copertura minimo dal grafico. Questo algoritmo trova il sottoinsieme di archi che include ogni vertice del grafico in modo tale che la somma dei pesi degli archi possa essere minimizzata.

quante città ci sono negli stati uniti d'america

Per saperne di più sull'algoritmo di Prim, puoi fare clic sul collegamento seguente: https://www.javatpoint.com/prim-algoritmo

L'algoritmo di Kruskal - Questo algoritmo viene utilizzato anche per trovare l'albero di copertura minimo per un grafico pesato connesso. Anche l'algoritmo di Kruskal segue un approccio greedy, che trova una soluzione ottimale in ogni fase invece di concentrarsi su un ottimo globale.

Per saperne di più sull'algoritmo di Prim, puoi fare clic sul collegamento seguente: https://www.javatpoint.com/kruskal-algoritmo

Quindi, questo è tutto sull'articolo. Spero che l'articolo ti sia utile e informativo. Qui abbiamo discusso lo spanning tree e lo spanning tree minimo insieme alle loro proprietà, esempi e applicazioni.