Orientované stromy: Rozdiel medzi revíziami
d wikilinky |
Použil som matematický mód, kde to bolo vhodné v sekcii Binárne stromy. |
||
Riadok 22: | Riadok 22: | ||
== Binárny strom == |
== Binárny strom == |
||
Binárnym stromom nazývame koreňový strom |
Binárnym stromom nazývame koreňový strom <math> T_v </math>, v ktorom každý vrchol má vonkajší stupeň 0 alebo 2. Hĺbkou h1(<math> T_v </math>) binárneho stromu (<math> T_v </math>) = (V, H) nazývame excentricitu jeho koreňa, t. j. |
||
<math> |
<math> h_1 (T_v) = max_{u \in V} d(v, u)</math>. |
||
Kompletným binárnym stromom hĺbky k nazývame strom ( |
Kompletným binárnym stromom hĺbky k nazývame strom (<math> T_v </math>), v ktorom je d(v, u) = k pre každý jeho list u. |
||
Riadok 38: | Riadok 38: | ||
=== Vonkajšia a vnútorná dĺžka binárneho stromu === |
=== Vonkajšia a vnútorná dĺžka binárneho stromu === |
||
'''Definícia.''' Nech |
'''Definícia.''' Nech <math> T_v =(V,H) </math> 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 |
||
<math>E(T_v) = \sum_{u\in v} d(v, u)</math> pre <math>u \in v_e</math> |
<math>E(T_v) = \sum_{u\in v} d(v, u)</math> pre <math>u \in v_e</math> |
Aktuálna revízia z 16:26, 21. december 2017
Tento článok alebo jeho časť si vyžaduje úpravu, aby zodpovedal vyššiemu štandardu kvality. Prosím, pozrite si stránky pomocníka, odporúčanie pre encyklopedický štýl a článok vhodne upravte. |
Orientovaný strom[upraviť | upraviť zdroj]
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[upraviť | upraviť zdroj]
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[upraviť | upraviť zdroj]
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[upraviť | upraviť zdroj]
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[upraviť | upraviť zdroj]
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[upraviť | upraviť zdroj]
Binárnym stromom nazývame koreňový strom , v ktorom každý vrchol má vonkajší stupeň 0 alebo 2. Hĺbkou h1() binárneho stromu () = (V, H) nazývame excentricitu jeho koreňa, t. j. .
Kompletným binárnym stromom hĺbky k nazývame strom (), v ktorom je d(v, u) = k pre každý jeho list u.
Vety o binárnych stromoch[upraviť | upraviť zdroj]
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[upraviť | upraviť zdroj]
Definícia. Nech 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[upraviť | upraviť zdroj]
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[upraviť | upraviť zdroj]
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.