1. Čo je to strom a les?

Strom

• V teórii grafov a strom je neorientovaný, súvislý a acyklický graf . Inými slovami, súvislý graf, ktorý neobsahuje ani jeden cyklus, sa nazýva strom.
• Strom predstavuje hierarchickú štruktúru v grafickej podobe.
• Prvky stromov sa nazývajú ich uzly a okraje stromu sa nazývajú vetvy.
• Strom s n vrcholmi má (n-1) hrán.
• Stromy poskytujú mnoho užitočných aplikácií jednoduchých ako rodokmeň až po zložité ako stromy v dátových štruktúrach informatiky.
• A list v strome je vrchol stupňa 1 alebo akýkoľvek vrchol bez potomkov sa nazýva list.

Príklad

Vo vyššie uvedenom príklade sú všetky stromy s menej ako 6 vrcholmi.

les

V teórii grafov a les je neorientovaný, nesúvislý, acyklický graf . Inými slovami, nesúvislá zbierka stromov je známa ako les. Každá zložka lesa je strom.

rekha vek

Príklad

Vyššie uvedený graf vyzerá ako dva podgrafy, ale ide o jeden oddelený graf. Vo vyššie uvedenom grafe nie sú žiadne cykly. Preto je to les.

2. Vlastnosti stromov

1. Každý strom, ktorý má aspoň dva vrcholy, by mal mať aspoň dva listy.
2. Stromy majú mnoho charakteristík:
   Nech T je graf s n vrcholmi, potom sú nasledujúce výroky ekvivalentné:
   • T je strom.
   • T neobsahuje žiadne cykly a má n-1 hrán.
   • T je spojené a má (n -1) hranu.
   • T je súvislý graf a každá hrana je rezná hrana.
   • Akékoľvek dva vrcholy grafu T sú spojené práve jednou cestou.
   • T neobsahuje žiadne cykly a pre každú novú hranu e má graf T+ e práve jeden cyklus.
3. Každá hrana stromu je zrezaná.
4. Pridanie jednej hrany do stromu definuje presne jeden cyklus.
5. Každý pripojený graf obsahuje kostru.
6. Každý strom má aspoň dva vrcholy druhého stupňa.

3. Spanning Tree

A kostra v súvislom grafe G je podgraf H grafu G, ktorý zahŕňa všetky vrcholy G a je tiež stromom.

Príklad

Zvážte nasledujúci graf G:

Z vyššie uvedeného grafu G môžeme implementovať nasledujúce tri kostry H:

Metódy na nájdenie kostry

Kostra môžeme nájsť systematicky pomocou jednej z dvoch metód:

príklad triedy java

1. Metóda výrubu
2. Metóda výstavby

1. Metóda rúbania

• Začnite vyberať ľubovoľný cyklus v grafe G.
• Odstráňte jeden z okrajov cyklu.
• Tento postup opakujte, kým nezostanú žiadne cykly.

Príklad

• Zoberme si graf G,

• Ak odstránime hranu ac, ktorá zničí cyklus a-d-c-a vo vyššie uvedenom grafe, dostaneme nasledujúci graf:

• Odstráňte hranu cb, ktorá zničí cyklus a-d-c-b-a z vyššie uvedeného grafu, potom dostaneme nasledujúci graf:

• Ak odstránime hranu ec, ktorá zničí cyklus d-e-c-d z vyššie uvedeného grafu, dostaneme nasledujúci kostru:

2. Stavebná metóda

• Vyberte hrany grafu G jeden po druhom. Takým spôsobom, že nevznikajú žiadne cykly.
• Tento postup opakujte, kým nezahrniete všetky vrcholy.

Príklad

Zvážte nasledujúci graf G,

• Vyberte okraj ab ,

• Vyberte okraj z ,

• Potom vyberte okraj ec ,

• Ďalej vyberte okraj cb , potom nakoniec dostaneme nasledujúci kostrový strom:

Poradie obvodu

Počet hrán, ktoré musíme z G odstrániť, aby sme získali kostru.

Kostra G = m- (n-1) , ktorý sa nazýva obvodová hodnosť z G.

 Where, m = No. of edges. n = No. of vertices. 

Príklad

Vo vyššie uvedenom grafe sú hrany m = 7 a vrcholy n = 5

Potom je poradie obvodu,

 G = m - (n - 1) = 7 - (5 - 1) = 3