Struttura dei dati e algoritmi - Spanning Tree

Uno spanning tree è un sottoinsieme del grafico G, che ha tutti i vertici coperti con il minimo numero possibile di bordi. Quindi, uno spanning tree non ha cicli e non può essere disconnesso.

Con questa definizione, possiamo trarre una conclusione che ogni grafico G connesso e non orientato ha almeno uno spanning tree. Un grafo disconnesso non ha alcun albero spanning, poiché non può essere esteso a tutti i suoi vertici.

Abbiamo trovato tre alberi che si estendono su un grafico completo. Un grafo non orientato completo può avere il massimonn-2 numero di alberi spanning, dove nè il numero di nodi. Nell'esempio sopra indicato,n is 3, quindi 33−2 = 3 gli alberi spanning sono possibili.

Proprietà generali dello Spanning Tree

Ora comprendiamo che un grafo può avere più di uno spanning tree. Di seguito sono riportate alcune proprietà dello spanning tree connesso al grafico G -

  • Un grafo G connesso può avere più di uno spanning tree.

  • Tutti i possibili spanning tree del grafo G hanno lo stesso numero di archi e vertici.

  • Lo spanning tree non ha alcun ciclo (loop).

  • La rimozione di un bordo dallo spanning tree renderà il grafo scollegato, cioè lo spanning tree lo è minimally connected.

  • L'aggiunta di un bordo allo spanning tree creerà un circuito o loop, ovvero lo spanning tree lo è maximally acyclic.

Proprietà matematiche dello Spanning Tree

  • Lo spanning tree ha n-1 bordi, dove n è il numero di nodi (vertici).

  • Da un grafico completo, rimuovendo il massimo e - n + 1 bordi, possiamo costruire uno spanning tree.

  • Un grafico completo può avere il massimo nn-2 numero di alberi spanning.

Quindi, possiamo concludere che gli spanning tree sono un sottoinsieme del grafico G connesso e i grafi scollegati non hanno lo spanning tree.

Applicazione di Spanning Tree

Lo spanning tree è fondamentalmente utilizzato per trovare un percorso minimo per connettere tutti i nodi in un grafico. Le applicazioni comuni degli spanning tree sono:

  • Civil Network Planning

  • Computer Network Routing Protocol

  • Cluster Analysis

Cerchiamo di capirlo attraverso un piccolo esempio. Considera la rete cittadina come un enorme grafico e ora prevede di distribuire le linee telefoniche in modo tale che in linee minime possiamo connetterci a tutti i nodi della città. È qui che entra in scena lo spanning tree.

Albero di copertura minimo (MST)

In un grafico ponderato, uno spanning tree minimo è uno spanning tree che ha un peso minimo rispetto a tutti gli altri spanning tree dello stesso grafico. Nelle situazioni del mondo reale, questo peso può essere misurato come distanza, congestione, carico del traffico o qualsiasi valore arbitrario indicato ai bordi.

Algoritmo minimo di spanning-tree

Impareremo qui due importanti algoritmi di spanning tree:

Entrambi sono algoritmi avidi.