Strom (teória grafov)

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 $\left|V\right|=\left|E\right|+1$ , 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.

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 $\vartriangle$ 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í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

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

Literatúra

KVASNIČKA, Vladimír; POSPÍCHAL, Jiří. Algebra a diskrétna matematika. [s.l.] : STU, 2008. ISBN 9788022729345.
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