DRVA

DEFINITION

Дрво е сврзан неориентиран граф во кој нема прости циклуси.
Бидејќи нема прости циклуси, дрвото не може да има ниту повеќекратни ребра или
алки (лупи).

Генерално, графовите што не содржат прости циклуси се нарекуваат шуми.
Секоја сврзана компонента на која било шума е дрво.

FAMILY

Кореново дрво е дрво во кое што едно теме е означено како корен и секое ребро е насочено од коренот кон останатите темиња.

Ако v е теме на дрвото T кое не е корен,
родител на v е единственото теме u така што постои ориентирано ребро од u до v

Кога u е родител на v, v се нарекува дете на u.

Ако две (или повеќе) темиња имаат ист родител, тие се нарекуваат сестрински темиња

Теме кое нема деца се нарекува лист.

Темињата кои што имаат деца се викаат внатрешни темиња.

Претци на теме v кое не е корен се темињата на патот од коренот до v, исклучувајќи го самото теме v и вклучувајќи го коренот.

Потомци на темето v се оние темиња кои што го имаат v за свој предок.

TYPES OF TREES

Поддрво со корен a е подграфот на T кој што се состои од:

  • темето a
  • сите потомци на темето a
  • и сите ребра што се инцидентни со овие потомци.

m-арно дрво е кореново дрво во кое секое внатрешно теме нема повеќе од m деца

Целосно (полно) m-арно дрво е ако секое внатрешно
теме има точно m деца.

Подредено кореново дрво е ако децата на секое внатрешно теме се подредени.

Подредено бинарно дрво (лево и десно дете)

корен во левото дете - лево поддрво

Ниво на теме v во кореново дрво е должината на единствениот пат
од коренот до темето v.

Висина на кореново дрво е максимумот на нивоата на неговите темињата

TEOREMI

  1. Еден неориентиран граф е дрво ако и само ако постои единствен прост пат помеѓу кои било две негови темиња.
  1. Дрво со n темиња има n - 1 ребра.
  1. Целосно m-арно дрво со i внатрешни темиња има вкупно n = mi + 1 темиња.
  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) внатрешни темиња.
  1. Во m-арно дрво со висина h постојат најмногу m^h лисја.

5.1 Ако m-арно дрво со висина h има l лисја тогаш, h >=[log_m l].
Ако m-арно дрво со l лисја е целосно и балансирано, тогаш неговата висина е h = [log_m l].

Кореново m-арно дрво со висина h се нарекува балансирано ако сите лисја се на ниво h или h – 1.

Комплетно m-арно дрво е целосно m-арно дрво, кај кое што сите листови се на исто ниво.