Orientované stromy: Rozdiel medzi revíziami

z Wikipédie, slobodnej encyklopédie
Smazaný obsah Přidaný obsah
Hefo (diskusia | príspevky)
d na upravu, chybaju tu nejake definicie ako napr, co su predkovia a potomkovia...
d wikilinky
Riadok 2: Riadok 2:


== Orientovaný strom ==
== Orientovaný strom ==
'''Definícia:''' Nech T = (V, H) je [[Strom_(graf)|strom]]. Ak každej [[Hrana_(teória_grafov)|hrane]] stromu T priradíme práve jednu z dvoch možných orientácií, tak dostaneme orientovaný strom T.
'''Definícia:''' Nech T = (V, H) je [[Strom (teória grafov)|strom]]. Ak každej [[Hrana_(teória_grafov)|hrane]] stromu T priradíme práve jednu z dvoch možných orientácií, tak dostaneme orientovaný strom T.




== Koreňový strom a koreň stromu==
== Koreňový strom a koreň stromu==
Nech Tv je orientovaný strom s aspoň dvoma vrcholmi, v ktorom z [[Vrchol_(teória_grafov)|vrcholu]] „v“ existuje dráha do každého z ostatných vrcholov. Potom Tv nazývame koreňovým stromom a vrchol „v“ koreňom stromu.
Nech Tv je orientovaný strom s aspoň dvoma vrcholmi, v ktorom z [[Vrchol (teória grafov)|vrcholu]] „v“ existuje dráha do každého z ostatných vrcholov. Potom Tv nazývame koreňovým stromom a vrchol „v“ koreňom stromu.





Verzia z 10:59, 16. júl 2016

Orientovaný strom

Definícia: Nech T = (V, H) je strom. Ak každej hrane stromu T priradíme práve jednu z dvoch možných orientácií, tak dostaneme orientovaný strom T.


Koreňový strom a koreň stromu

Nech Tv je orientovaný strom s aspoň dvoma vrcholmi, v ktorom z vrcholu „v“ existuje dráha do každého z ostatných vrcholov. Potom Tv nazývame koreňovým stromom a vrchol „v“ koreňom stromu.


Podstrom stromu

Ak T je orientovaný koreňový strom a „u“ je nejaký vrchol stromu T, potom podgraf T, ktorý vznikne tak, že zo stromu T vynecháme všetky vrcholy, do ktorých nevedie orientovaná cesta z vrcholu „u“ sa nazýva podstrom stromu T s koreňom „u“.


n-árny strom

Orientovaný koreňový strom sa nazýva n-árny strom, ak každý vnútorný vrchol tohoto stromu má práve n potomkov, inými slovami, každý vrchol n-árneho stromu má výstupný stupeň 0 alebo n. Špeciálne, n-árny strom s n = 2, sa nazýva binárny strom.


Koreňová kostra digrafu

Nech G je digraf, ktorý vznikol orientáciou grafu (multigrafu) G. Nech K je kostra grafu (multigrafu) G. Potom digraf K, ktorý vznikol orientáciou grafu K, sa nazýva orientovanou kostrou digrafu G.


Binárny strom

Binárnym stromom nazývame koreňový strom Tv, v ktorom každý vrchol má vonkajší stupeň 0 alebo 2. Hĺbkou h1(Tv) binárneho stromu (Tv) = (V, H) nazývame excentricitu jeho koreňa, t. j. .

Kompletným binárnym stromom hĺbky k nazývame strom (Tv), v ktorom je d(v, u) = k pre každý jeho list u.


Vety o binárnych stromoch

Veta 1. Pre ľubovoľné prirodzené číslo n > 1 existuje binárny strom s práve n listami (koncovými vrcholmi).

Veta 2. Binárny strom s n listami obsahuje n-1 vnútorných vrcholov (t. j. vrcholov, ktoré nie sú listami) a 2(n-1) hrán.

Veta 3. Nech E je vonkajšia a I vnútorná dĺžka binárneho stromu s n listami. Potom .


Vonkajšia a vnútorná dĺžka binárneho stromu

Definícia. Nech Tv=(V,H) je binárny strom. Vonkajšou dĺžkou E(Tv), resp. vnútornou dĺžkou I(Tv) binárneho stromu Tv nazývame čísla určené vzťahmi

pre

pre

kde ve je množina listov a vi je množina vnútorných vrcholov binárneho stromu Tv.


B-strom

B-stromom nazývame orientovaný koreňový strom, v ktorom každý vrchol má vonkajší stupeň 0, 1 alebo 2 a ktorého hrany sú ohodnotené číslami 0 a 1 tak, že žiadne dve hrany vychádzajúce z toho istého vrcholu nemajú rovnaké ohodnotenie.


Perfektne vyvážený B-strom

Podmienku minimálnosti spĺňajú B-stromy, v ktorých pre každý vnútorný vrchol sa počet vrcholov jeho ľavom a pravom podstrome líši najviac o 1. Nazývame ich perfektne vyvážené B-stromy.


Odkazy

Strom_(graf)
Binárny strom