Strom (teória grafov)

thumb|right

**Strom** alebo **stromový graf** je grafické vyjadrenie členenia určitej množiny na jej podmnožiny (napr. súbory na podsúbory, strojársky výrobok na podskupiny a súčiastky a pod.). Graf okrem členenia znázorňuje aj postupnosť členenia alebo zlučovania. Spojenie jednotlivých vetiev stromu ukazuje zlúčenie (delenie), pričom dĺžkou vetví môže vyjadriť hladinu, na ktorej sa podskupiny zlučujú (delia).

**Strom** je neprázdny súvislý graf, ktorý neobsahuje kružnicu (cyklus). Na označenie stromov, ako špeciálnych grafov, sa používa označenie T = (V, H). Písmeno T je z anglickej terminológie (tree – strom).

**Les** je jednoduchý graf bez kružníc, ktorého komponentami sú stromy.

Strom, ktorý má každej hrane priradený jeden z dvoch možných smerov, sa nazýva orientovaný strom.

## Matematická teória stromovej štruktúry
Strom možno definovať:
** *G* je strom.
** Každé dva vrcholy z *G* sú spojené práve jednou cestou (jednoznačnosť cesty).
** *G* je súvislý a po odobraní ľubovoľnej hrany sa stane nesúvislým (minimálna súvislosť).
** *G* neobsahuje kružnicu, ale po pridaní ľubovoľnej hrany vznikne v *G* kružnica (maximálny graf bez kružníc*) .
** *G* je súvislý a <math>\left | V \right | = \left | E \right |+ 1</math>, kde *V* je [[množina]] vrcholov a *E* množina hrán grafu *G*.

* *'Veta 1.1.** Strom s viac ako jedným vrcholom obsahuje vrchol stupňa 1.

**Dôkaz:** Súvislý graf s viac ako jedným vrcholom nemôže mať vrchol stupňa 0. Preto ak pre strom **T** a v ňom ľubovoľný vrchol **v** zostrojíme čo najdlhší sled **S** v **T** začínajúci vo **v**: **S** začne ľubovoľnou hranou vychádzajúcou z **v**. V každom ďalšom vrchole **u**, do ktorého sa dostaneme a má stupeň väčší ako 1, môže potom pokračovať sled **S** ďalšou novou hranou. Pokiaľ by sa v slede **S** zopakoval niektorý vrchol, získali by sme kružnicu. Preto sled **S** musí skončiť v nejakom vrchole stupňa 1 v **T**. 

[[Súbor:Tree structures (graph theory).svg|left|thumb]]
Na obrázkoch sú diagramy troch stromov. Prvý z nich má práve dva vrcholy stupňa 1 a všetky ostatné vrcholy majú stupeň 2. Taký strom sa nazýva **had**. Druhý zo stromov je **hviezda**. Hviezda je strom, ktorý má práve jeden vrchol stupňa aspoň 3 a všetky ostatné vrcholy majú stupeň 1. Tretí zo stromov na obrázku je typ **rozhodovacieho** stromu (prípadne genealogického stromu).

* **Veta 1.2.** Strom na n vrcholoch ma presne n – 1 hrán pre n ≥ 1.

**Dôkaz:** Toto tvrdenie sa dá dokázať indukciou podľa n. Strom s jedným vrcholom má n – 1 = 0 hrán. Nech **T** je strom na n > 1 vrcholoch. Podľa Vety 1.1. má **T** vrchol **v** stupňa 1. Označme **T` = T – v** graf vzniknutý z **T** odobratím vrcholu **v**. Potom **T`** je tiež súvislý bez kružníc, taktiež strom na n – 1 vrcholoch. Podľa indukčného predpokladu **T`** má n – 1 – 1 hrán, a preto **T** má n – 1 – 1 + 1 = n – 1 hrán.
* **Veta 1.3.** Medzi každými dvoma vrcholmi stromu vedie práve jedna cesta.

**Dôkaz:** Nech strom **T** je súvislý podľa definície, medzi ľubovoľnými dvoma vrcholmi **u**, **v** vedie nejaká cesta. Pokiaľ by existovali dve rôzne cesty **P1**, **P2** medzi **u**, **v**, tak by sme vzali ich symetrický rozdiel, podgraf **H** = **P1** <math>\vartriangle</math> **P2** s neprázdnou množinou hrán, kde **H** má zrejme všetky stupne párne. Na druhej strane sa však podgraf stromu musí opäť skladať z komponentov stromov, a teda obsahovať vrchol stupňa 1 podľa vety 1.1., spor. Preto cesta medzi **u** a **v** je len jedna.

* **Veta 1.4.** Pridaním jednej novej hrany do stromu vznikne práve jedna kružnica.

**Dôkaz:** Nech medzi vrcholmi **u**, **v** v strome **T** nie je hrana. Pridaním hrany **e = uv** vznikne práve jedna kružnica z **e** a jedinej cesty medzi **u**, **v** v **T** podľa vety 1.3.

* **Veta 1.5.** Strom je minimálny súvislý graf na daných vrcholoch.

**Dôkaz:** Strom je súvislý podľa definície. Pokiaľ by ale vypustením hrany **e = uv** zo stromu **T** vznikol opäť súvislý graf, potom by medzi **u**, **v** v **T** existovali dve cesty (dohromady kružnice) – hrana **e** a iná cesta v **T – e**. To je v spore s vetou 1.3. Naopak, pokiaľ by súvislý graf mal kružnicu, zostal by súvislý i po vypustení niektorej hrany tej kružnice. Potom každý minimálny súvislý graf (na daných vrcholoch) je stromom. Teda strom je práve minimálnym súvislým grafom na daných vrcholoch. 
* **Veta 1.6.** Nech **T = (V,H)** je strom. Ak jeho priemer je číslo párne, tak stredom stromu je jediný vrchol a **P(T) = 2r(T)**. Ak jeho priemer je číslo nepárne, tak stredom sú dva susedné vrcholy a **P(T) = 2r(T) - 1**.

== Vlastnosti stromov ==
Človek si ani nemusí uvedomovať ako môže aplikovať „Stromy“ aj vo vlastnom živote a ako mu môžu mnohokrát pomôcť pri práci. Ako príklad poslúži [[rodokmeň]] nejakého človeka. Ak by sme chceli zistiť rodokmeň nejakého príbuzného alebo známeho človeka, musíme požiadať o jeho vyhotovenie. Vyhotovia nám ho pomocou tabuliek. Každý rodokmeň začína u človeka, ktorý „vytvoril“ rod a končí u človeka/ ľudí pri ktorom/-ých daný rod zanikol. Každý človek má takýto rodokmeň. Zamyslime sa nad príkladom, kedy by sme chceli zistiť rodokmeň významnej osobnosti Slovenska, [[Ľudovít_Štúr|Ľudovíta Štúra]]. V tomto prípade pri vytvorení takéhoto rodokmeňa nám pomáhajú stromy. Čo to stromy vlastne sú?

== Teória ==
[[Súbor:Arthur Cayley.jpg|thumb|right|[[Arthur Cayley]]]]
Graf, ktorý neobsahuje kružnice, nazývame **acyklický**. Súvislý acyklický graf nazývame **strom**. Nesúvislý graf, ktorého každý komponent je strom, nazývame **les**. Prvýkrát boli stromy použité už anglickým matematikom Arthurom Cayleym v r. 1857 na spočítanie druhov istého typu chemických zlúčenín – alkánov.  Alkány sa inak volajú nasýtené uhľovodíky a majú sumárnu formulu CnH2n+2 . V grafovom modeli je každý atóm uhlíka reprezentovaný vrcholom stupňa 4 a každý vodíkový atóm vrcholom stupňa 1. V grafe reprezentujúcom alkány je teda je 3n+2 vrcholov, a keďže počet hrán je polovicou sumy stupňov vrcholov, ich počet je (4n+2n+2)/2=3n+1 hrán. Neizomorfné stromy o n vrcholoch stupňa 4 a o 2n+2 vrcholoch stupňa 1 reprezentujú rozdielne izoméry CnH2n+2

Od Cayleyho doby boli stromy použité na riešenie problémov v množstve disciplín. V bežnom živote sa s použitím stromov môžeme stretnúť od genealógie – stromu príbuznosti u rodokmeňa, klasifikačného stromu živočíchov a rastlín, stromu športového turnaja až po organizačnú štruktúru hierarchie podniku, kde vrcholy sú jednotlivé organizačné jednotky a hrany predstavujú vzťahy nadriadenosti-podriadenosti medzi nimi. Najobyčajnejším využitím stromov v počítači je štruktúra adresárov. Stromy  sa ale nepoužívajú iba na opis štruktúr, ale predovšetkým ako pomôcka na manipulácie s informáciou.

Je to napríklad: 
* rozmiestňovanie prvkov v databázach 
* efektívne kódy na ukladanie a prenos informácií 
* rozhodovacie stromy 
* modely hier na určenie vyhrávajúcej stratégie 
* nájdenie najlacnejšieho prepojenia uzlov komunikačnej siete 
* prehľadávanie stromov (napríklad riešenie problému rozmiestnenia dám na šachovnici, aby sa neohrozovali). 
 
Nesúvislý graf bez cyklov (skladá sa zo stromov) voláme **les**. 

**Veta:** Neorientovaný graf je stromom iba vtedy, ak existuje práve jedna cesta medzi ľubovoľnou dvojicou jeho vrcholov. 
 
''Dôkaz'': Predpokladajme, že T je strom. Potom T je súvislý graf bez kružníc. Nech x a y sú dva vrcholy z T. Pretože  T je súvislý, medzi  x a y existuje cesta. Táto cesta musí byť jediná, pretože keby existovali 2 rôzne cesty, dala by sa zobrať cesta z  x do y a naspäť z y do  x, a z rozdielnych hrán týchto ciest by sa dala zostaviť kružnica. To je v spore s predpokladom, že T je súvislý graf bez kružníc. 

Teraz predpokladajme, že existuje práve jedna cesta medzi  ľubovoľnými dvoma vrcholmi grafu. Potom je graf súvislý a  neobsahuje kružnicu. Aby sme to ukázali, predpokladajme, že existuje kružnica obsahujúca body x a y. Potom by medzi x a  y existovali dve cesty, pretože kružnica obsahujúca body x a  y sa dá rozdeliť na cestu z x do y a na druhú cestu z y do x. Z toho vyplýva, že graf s práve jednou cestou medzi ľubovoľnou dvojicou jeho vrcholov je strom. 
 
V mnohých aplikáciách sa využíva strom so špeciálne vyznačeným vrcholom volaným  **koreň**. Taký strom sa volá  **koreňový**  (alebo  zakorenený) **strom**  (rooted tree).  Keď máme vybratý takýto koreň, môžeme priradiť každej hrane orientáciu smerom od koreňa. Výberom koreňa môžeme z jedného stromu vytvoriť dva rôzne koreňové stromy,  Koreňové stromy preberajú ďalšiu terminológiu tak z genealógie, ako z biológie, 
Predpokladajme, že T je koreňový strom a v je jeho vrchol rôzny od koreňa. **Predchodca** (alebo  rodič – parent) vrcholu  v je práve jeden vrchol  u, kde (u,  v) je orientovaná hrana na ceste z koreňa do vrcholu v. Vrchol v sa volá **nasledovník** (syn, dieťa - child) vrcholu u. **Predok** (ancestor) vrcholu v je okrem koreňa tiež každý vrchol na ceste od koreňa k danému vrcholu  v, s výnimkou samotného vrcholu  v. **Potomok** (descendant) vrcholu  v je ľubovoľný vrchol, ktorý má vrchol v ako predka. Vrchol stromu je volaný **list**, keď nemá žiadne deti. Vrcholy, ktoré majú deti, sa volajú  **vnútorné vrcholy**. Keď b je vrchol stromu,  **podstrom** s koreňom  b je podgraf stromu zostavený z vrcholu  b, všetkých jeho potomkov a všetkých hrán incidentných s potomkami, napr. na obr. 3 u druhého grafu by to bol podstrom určený vrcholovou množinou {b,e,c,d}.

**Úroveň vrcholu** je dĺžka cesty od vrcholu ku koreňu.  **Hĺbka stromu** (height, teda výška) je maximálna úroveň vrcholov. Koreňový strom sa volá  **n-árny** strom keď každý vrchol má maximálne n detí. Koreňový strom sa volá **plne n-árny strom**, keď každý vnútorný vrchol má práve n detí. Pre n=2 sa n-árny strom volá **binárny strom**, pre n=3 sa n-árny strom volá **ternárny** strom. 

**Usporiadaný koreňový strom** je koreňový strom, kde deti každého vnútorného vrcholu sú usporiadané, kreslia sa poporiadku zľava doprava. V binárnom strome sa vrchol naľavo volá **ľavý nasledovník**, vrchol napravo **pravý nasledovník**. Napríklad u obrázku č. 4 je vrchol e ľavý nasledovník a vrchol d pravý nasledovník vrcholu b.

**Veta:** Strom o n vrcholoch má n-1 hrán. 
 
''Dôkaz:'' Použijeme matematickú indukciu. Keď n=1, strom o jednom vrcholu nemá hranu, veta platí. 
Induktívny krok: Predpokladajme, že veta platí pre k vrcholov, kde k je kladné celé číslo. 
Predpokladajme, že strom  T má  k +1 vrcholov, a že  v je list a w je rodič vrcholu  v. 
Odstránením vrcholu v a hrany {v,w} z T vytvoríme strom T’. Podľa indukčnej hypotézy strom T’ má k -1 hrán. Preto strom T musí mať k hrán, pridaním hrany{v,w}zvýšime k -1 o 1. 

**Veta:** Plne m-nárny strom s i vnútornými vrcholmi má n=m×i +1 vrcholov. Koreňový plne m-nárny strom hĺbky h je vyvážený, keď všetky jeho listy sú na úrovni h alebo h-1.  
 
**Veta:** V m-nárnom strome  hĺbky h je maximálne mh listov.  
 
**Veta:*' Keď m-nárny strom  hĺbky h má l listov, potom h≥|logml|. Rovnosť platí pre plne m-nárny vyvážený strom.  
 
*Príklad:'' Predpokladajme, že správu o novom víruse rozpošle každý príjemca o minútu po prijatí 10 kamarátom, a nikto nedostane správu dvakrát. Za ako dlho presiahne počet príjemcov množstvo ľudí na Slovensku?   

|Log105000000|=7 minút

## Záver
V závere si ukážeme presný príklad ako náš hľadaný rodokmeň bude vyzerať ak požiadame o jeho vytvorenie.
 
Na obrázku môžeme vidieť ako jednoducho a priehľadne sa môžeme orientovať v našom hľadanom rodokmeni. Vidíme začiatok, na ktorého čele stojí osoba, ktorej rodokmeň sme hľadali (koreň) a na konci sú uvedené osoby, ktoré tento rodokmeň ukončujú (listy/ potomkovia). Zistili sme aj presný počet ľudí v tomto rodokmeni, sú v ňom uvedené dátumy ich narodenia a úmrtia a aj ich mená. Samozrejme, rodokmeň si môžeme doplniť o informácie aké len my chceme. 
Ani by sme mnohokrát netušili, že aj v takomto prípade, akým je vytvorenie rodokmeňa je hlavným faktorom pre jeho vytvorenie „STROM“.

## Pozri aj
* Strom (dátová štruktúra)
* Binárny strom (teória grafov)
* Halda (dátová štruktúra)

## Literatúra
* 
* 
* FRONČEK, Dalibor. Úvod do teorie grafů. Ediční středisko FPF SU v Opavě. 1999
* Bučko M. – Klešč, M.: Diskrétna matematika, Elfa, Košice, 1999.

## Externé odkazy
* Prednášky z teórie grafov


Kategória:Diskrétna matematika
Kategória:Teória grafov