Основні означення

ВСТУП В ТЕОРІЮ ДЕРЕВ

МЕТОДИЧНІ ВКАЗІВКИ

до виконання практичних робіт

з дисципліни „Комп’ютерна дискретна математика”

для студентів спеціальності

6. 050103 „Програмна інженерія”

Львів – 2015

Теорія графів.: Методичні вказівки до виконання практичних робіт із дисципліни „Комп’ютерна дискретна математика” для студентів спеціальності „Програмна інженерія” / Укл.: П.В. Сердюк, О.О. Нитребич, Н.А. Крупко – Львів: Видавництво Національного університету „Львівська політехніка”, 2015. –?? с.

Укладачі П.В. Сердюк, кандидат техн. наук, доц.

Н.А. Крупко, асист. кафедри ПЗ

О.О. Нитребич, асист. кафедри ПЗ

Відповідальний за випуск Федасюк Д.В., д-р тех. наук, проф.

Рецензенти, канд. тех. наук, доц.

, канд. фіз.-мат. наук, доц.

Мета роботи: Ознайомитись на практиці із основними поняттями теорії дерев.

Теоретичні відомості

Термін «дерево» як особливого різновиду графів ввів у 1857 р. англійський математик Артур Келі (1821-1895). З того часу це поняття широко застосовують у багатьох розділах математики й інформатики. Наприклад, дерева використовують як інструмент обчислень, зручний спосіб збереження даних на комп’ютері, їх сортування чи пошуку.

Основні означення

Означення 1.1. Дерево – це зв’язний граф без простих циклів.

Означення 1.2. Ліс – це незв’язний граф без простих циклів.

На рис. 1.1, а наведено приклад дерева, а на рис. 1.1, б – приклад лісу, що складається із трьох дерев.

а)	б)
Рис. 1.1. Приклад а) дерева; б) лісу

ТЕОРЕМА 1.1. Нехай граф G має n вершин. Тоді такі твердження еквівалентні:

1) граф G – дерево;

2) граф G не містить простих циклів і має (n –1) ребро;

3) граф G зв’язний і має (n –1) ребро;

4) граф G зв’язний, але вилучення довільного ребра робить його незв’язним;

5) довільні дві вершини графу G з’єднані точно одним простим маршрутом;

6) граф G не містить простих циклів, але додавши до нього нове ребро ми отримаємо точно один простий цикл.

Наслідок із теореми 1.1. Ліс із k дерев, який містить n вершин, має (п-k)ребер.

Приклад 1.1. Скільки ребер має дерево, що складається зі 100 вершин?

Відповідь: Кількість ребер дорівнює 100-1 = 99.

Приклад 1.2. Скільки ребер має ліс, що складається із 3 дерев та містить 100 вершин?

Відповідь: Кількість ребер дорівнює 100-3 = 97.

У багатьох випадках у дереві виділяють певну вершину, яка знаходиться у верхній частині дерева, та називається коренем дерева. Після цього можна кожному ребру дерева задати напрямок від кореня, адже існує єдиний простий шлях від вершини дерева до кожного його ребра. Завдяки цьому дерево стає орієнтованим графом або кореневим деревом. Вершину v орієнтованого дерева називають нащадком вершини u, якщо існує шлях з u в v. В цьому випадку вершину u називають предком вершини v, а якщо довжина шляху з u в v дорівнює 1, то вершину v називають сином вершини u, яка при цьому називається батьком вершини v. Вершина, що не має нащадків називається листком. Вершини, що не є листками, називаються внутрішніми.

Означення 1.3. У кореневому дереві рівень вершини v – це довжина шляху від кореня дерева до цієї вершини.

Означення 1.4. Висота орієнтованого дерева– це довжина найдовшого шляху від кореня до листа.

На рис. 1.2 зображено приклад кореневого дерева, висотою 3.

Рис. 1.2. Приклад дерева

Означення 1.5. Кореневе дерево називається m -арним, якщо кожна його внутрішня вершина має не більше ніж т синів.

Означення 1.6. Кореневе дерево називається повним m -арним, якщо кожна його внутрішня вершина має точно т синів. У випадку т = 2 дерево називається бінарним.

На рис. 1.3 зображено приклади m -арних дерев.

а)	б)	в)
Рис. 1.3. Приклади m -арних дерев а) 3-арного; б) повного 3-арного; в) бінарного

ТЕОРЕМА 1.2. Повне m -арне дерево з i внутрішніми вершинами містить n = m·i +1 всього вершин.

Приклад 1.3. Скільки всього вершин має бінарне дерево з 10 внутрішніми вершинами?

Відповідь: m =2, тоді за теоремою 1.2 n = 2·10 +1=21 вершина.

Приклад 1.4. Скільки листків має бінарне дерево з 10 внутрішніми вершинами?

Відповідь: m =2, тоді за теоремою 1.2 n = 2·10 +1=21 вершина. Усі вершини є сумою внутрішніх вершин та листків, отже l = n - і =21-10=11.

Приклад 1.5. Скільки внутрішніх вершин має бінарне дерево з 11листками?

Відповідь: Усі вершини є сумою внутрішніх вершин та листків, отже n = l + і= 11 +і. Отже, за теоремою 1.2 отримаємо 11 +і= 2 ·i +1; i =10.p

Означення 1.7. Збалансованим називається m -арне дерево з висотою h, у якого усі листки на рівнях h або h -1.

Означення 1.8. Завершеним називається повне m -арне дерево, у якого усі листки на одному рівні.

На рис.1.3. наведено приклади збалансованого (рис.1.3, а) та завершеного (рис.1.3, б) дерев.

а)	б)
Рис. 1.3. Приклад а) збалансованого; б) завершеного дерева

Примітка! З рисунку 1.3, б очевидно, що якщо на кожному рівні завершеного дерева міститься m^r вершин, де r – рівень вершин; у завершеному m -арному дереві всього є m^h листків, де h – висота дерева; у завершеному m -арному дереві є усіх вершин; у завершеному m -арному дереві є внутрішніх вершин.

Приклад 1.6. Скільки листків має завершене 5-арне дерево висотою 3?

Відповідь: m =5, h =3, отже, кількість листків l = 5³ =125.p

Приклад 1.6. Скільки внутрішніх вершин має завершене 5-арне дерево висотою 4?

Відповідь: m =5, h =4, отже, кількість внутрішніх листків і = 5⁰ + 5¹ + 5² + 5³ =156.p

Означення 1.9. Кореневе дерево, у якому сини кожної внутрішньої вершини впорядковано, називають упорядкованим.

Таке дерево зображають так, щоб сини кожної вершини були розміщені зліва направо. Якщо внутрішня вершина впорядкованого бінарного дерева має двох синів, то першого називають лівим, а другого – правим. Піддерево з коренем у вершині, яка являє собою лівого сина вершини v, називають лівим піддеревом у цій вершині. Якщо корінь піддерева — правий син вершини v, то таке піддерево називають правим піддеревом у цій вершині (рис 1.4).

Рис.1.4. Упорядковане дерево