Spanning Tree a Minimum Spanning Tree

V tomto výukovém programu se na příkladech a obrázcích dozvíte o kostře a minimálním kostře.

Než se seznámíme s rozložením stromů, musíme porozumět dvěma grafům: neorientovaným grafům a připojeným grafům.

Neorientovaný graf je graf, ve kterém jsou okraje neukazují v žádném směru (tj. Okraje jsou obousměrně).

Neusměrněný graf

Spojitý graf je graf, ve kterém je vždy cesta od vrcholu k jiným vrcholu.

Propojený graf

Překlenující strom

Rozpínací strom je dílčím grafem neorientovaného připojeného grafu, který zahrnuje všechny vrcholy grafu s minimálním možným počtem hran. Pokud je vrchol vynechán, pak nejde o kostru.

Okraje mohou, ale nemusí mít přiřazené váhy.

Celkový počet překlenujících stromů s nvrcholy, které lze vytvořit z úplného grafu, se rovná .n(n-2)

Pokud máme n = 4, je maximální počet možných kosterních stromů roven . Z kompletního grafu se 4 vrcholy lze tedy vytvořit 16 koster.44-2 = 16

Příklad Spanning Tree

Pojďme pochopit kostru s příklady níže:

Nechť je původní graf:

Normální graf

Některé z možných koster, které lze vytvořit z výše uvedeného grafu, jsou:

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

Minimum Spanning Tree

Minimální kostra je kostra, ve které je součet hmotnosti hran co nejmenší.

Příklad Spanning Tree

Rozumíme výše uvedené definici pomocí níže uvedeného příkladu.

Počáteční graf je:

Vážený graf

Možné kostry z výše uvedeného grafu jsou:

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

Minimální kostra z výše uvedených stromů je:

Minimální kostra

Minimální rozpětí stromu z grafu se zjistí pomocí následujících algoritmů:

1. Primův algoritmus
2. Kruskalův algoritmus

Spanning Tree Applications

• Směrovací protokol počítačové sítě
• Shluková analýza
• Civilní plánování sítě

Minimum Spanning Tree Applications

• Vyhledání cest na mapě
• Navrhovat sítě jako telekomunikační sítě, vodovodní sítě a elektrické sítě.