Page 55 - 4386

а б

Рисунок 5.5

Рівнем вершини v називається довжина єдиного шляху від

кореня дерева до вершини v.

Висотою дерева називається довжина найдовшого шляху

від кореня дерева до кінцевих вершин.

Наприклад, для кореневого дерева, наведеного на рис. 5.5 а,

вершина v має рівень 2. Від кореня дерева до кінцевих вершин
3
максимальним є шлях довжиною 3 (v v v v ), отже, висота дерева
1 5 7 8
також рівна 3.

5.3 Центральні вершини в деревах

Центральні вершини графів за означенням мають

найменший ексцентриситет. Ексцентриситет вершини дерева

досягається на кінцевій вершині.

У довільному дереві T, центр складається з однієї вершини,

якщо D(T) – парне число, і з двох суміжних вершин, якщо

непарне.

Нехай маємо дерево T , для якого D(T )≥2. Якщо дерево T 2
1
1
одержується шляхом вилучення з T усіх кінцевих вершин, тоді:
1
1) ексцентриситет довільної вершини в T на 1 менший, ніж
2
у T ;
1
2) центри дерев збігаються;

54