Spanning Tree a Minimum Spanning Tree

V tomto výučbe sa na príkladoch a obrázkoch dozviete viac o spanning tree a minimálnom spanning tree.

Predtým, ako sa dozvieme viac o stromoch, ktoré potrebujete, musíme pochopiť dva grafy: neorientované grafy a spojené grafy.

Neorientovaný graf je graf, v ktorom sú okraje neukazujú v žiadnom smere (tj. Okraje sú obojsmerne).

Neusmernený graf

Spojitý graf je graf, v ktorom je vždy cesta od vrcholu k iným vrcholu.

Prepojený graf

Rozprestierajúci sa strom

Spanning tree je podgrafom neorientovaného pripojeného grafu, ktorý obsahuje všetky vrcholy grafu s minimálnym možným počtom hrán. Ak vrchol chýba, potom nejde o spanning tree.

Na okrajoch môžu, ale nemusia mať priradené závažia.

Celkový počet rozpätých stromov s nvrcholmi, ktoré je možné vytvoriť z úplného grafu, sa rovná .n(n-2)

Ak máme n = 4, maximálny počet možných spanovacích stromov sa rovná . Z kompletného grafu so 4 vrcholmi teda možno vytvoriť 16 spanovacích stromov.44-2 = 16

Ukážka klenutého stromu

Poďme pochopiť kostru s príkladmi uvedenými nižšie:

Nech je pôvodný graf:

Normálny graf

Niektoré z možných stromov, ktoré je možné vytvoriť z vyššie uvedeného grafu, sú:

Spanning tree a spanning tree a spanning tree A spanning tree A spanning tree A spanning tree

Minimálny rozpätie stromu

Minimálny kostra je kostra, v ktorej je súčet hmotnosti hrán čo najmenší.

Ukážka klenutého stromu

Pochopme vyššie uvedenú definíciu pomocou nižšie uvedeného príkladu.

Počiatočný graf je:

Vážený graf

Možné kostry z vyššie uvedeného grafu sú:

Minimum spanning tree - 1 Minimum spanning tree - 2 Minimum spanning tree - 3 Minimum spanning tree - 4

Minimálny kostra z vyššie uvedených kostier je:

Minimálny kostra

Minimálny rozpätie stromu z grafu sa zistí pomocou nasledujúcich algoritmov:

1. Primov algoritmus
2. Kruskalov algoritmus

Aplikácia Spanning Tree

• Smerovací protokol počítačovej siete
• Klastrová analýza
• Civilné sieťové plánovanie

Minimálne aplikácie Spanning Tree

• Vyhľadanie ciest na mape
• Navrhovať siete ako telekomunikačné siete, vodovodné siete a elektrické siete.