Please enable JavaScript.
Coggle requires JavaScript to display documents.
DRVA (TYPES OF TREES (Подредено бинарно дрво (лево и десно дете) (корен во…
DRVA
TYPES OF TREES
Поддрво со корен a е подграфот на T кој што се состои од:
- темето a
- сите потомци на темето a
- и сите ребра што се инцидентни со овие потомци.
-
-
-
-
-
-
-
Комплетно m-арно дрво е целосно m-арно дрво, кај кое што сите листови се на исто ниво.
FAMILY
Кореново дрво е дрво во кое што едно теме е означено како корен и секое ребро е насочено од коренот кон останатите темиња.
Ако v е теме на дрвото T кое не е корен,
родител на v е единственото теме u така што постои ориентирано ребро од u до v
Кога u е родител на v, v се нарекува дете на u.
Ако две (или повеќе) темиња имаат ист родител, тие се нарекуваат сестрински темиња
-
-
Претци на теме v кое не е корен се темињата на патот од коренот до v, исклучувајќи го самото теме v и вклучувајќи го коренот.
-
TEOREMI
- Еден неориентиран граф е дрво ако и само ако постои единствен прост пат помеѓу кои било две негови темиња.
- Дрво со n темиња има n - 1 ребра.
- Целосно m-арно дрво со i внатрешни темиња има вкупно n = mi + 1 темиња.
- Целосно m-арно дрво со:
(i) n темиња има i = (n – 1)/m внатрешни темиња и l = [(m – 1)n + 1]/m лисја;
(ii) i внатрешни темиња има n = mi + 1 темиња и l = (m – 1)i + 1 лисја;
(iii) l лисја има n = (ml – 1)/(m – l) темиња и i = (l – 1)/(m – 1) внатрешни темиња.
- Во m-арно дрво со висина h постојат најмногу m^h лисја.
5.1 Ако m-арно дрво со висина h има l лисја тогаш, h >=[log_m l].
Ако m-арно дрво со l лисја е целосно и балансирано, тогаш неговата висина е h = [log_m l].
DEFINITION
Дрво е сврзан неориентиран граф во кој нема прости циклуси.
Бидејќи нема прости циклуси, дрвото не може да има ниту повеќекратни ребра или
алки (лупи).
Генерално, графовите што не содржат прости циклуси се нарекуваат шуми.
Секоја сврзана компонента на која било шума е дрво.