Strom (graf)

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie
StromALes.JPG

Strom alebo stromový graf je grafické vyjadrenie členenia určitej množiny na jej podmnožiny (napr. súbory na podsúbory, strojárenský 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žnice. 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[upraviť | upraviť zdroj]

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.

Tree structures (graph theory).svg

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.

Pozri aj[upraviť | upraviť zdroj]