ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

Дифференциальные уравнения второго порядка (модель рынка с прогнозируемыми ценами) - В простых моделях рынка спрос и предложение обычно полагают зависящими только от текущей цены на товар.

Основні означення та властивості

12 3 4 5

Дерева та їх застосування

Конспект лекцій

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

для студентів напряму

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

Львів – 2012

Поняття дерева широко застосовують у багатьох розділах математики й інформатики. Наприклад, дерева використовують як інструмент обчислень, зручний спосіб збереження даних, їх сортування чи пошуку.

Основні означення та властивості

Деревом називають зв'язний граф без простих циклів. Граф, який не містить простих циклів і складається з k компонент, називають лісом із k дерев.

Приклад 1.1.На рис. 1.1 зображено приклади дерев. Граф, зображений на рис. 1.2 — не дерево, бо він незв'язний.

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

Зауваження.З означення випливає, що дерева й ліси являють собою прості графи.

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

(І) граф T —дерево;

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

(III) граф Т зв’язний і має (n-1) ребро;(IV) граф Т зв'язний, але вилучення довільного ребра робить його незв'язним;

(V) довільні дві вершини графа Т з'єднані точно одним простим шляхом;

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

Доведення(математичною індукцією). У разі n=1 твердження тривіальні; припустимо, що п ≥ 2.

(I) → (II). За означенням T не містить простих циклів. Отже, вилучивши довільне ребро, ми одержимо два графи, кожний з яких являє собою дерево з меншою, ніж у Т, кількістю вершин. За припущенням індукції кількість ребер у кожному з отриманих дерев на 1 менша за кількість вершин. Звідси випливає, що граф Т має (n-1) ребро.

(II) → (III). Припустимо, що граф Т незв'язний. Тоді кожна його компонента являє собою зв'язний граф без простих циклів, тобто дерево. Звідси випливає, що кількість вершин у кожній компоненті на одиницю більша від кількості ребер. Отже, загальна кількість вершин графа Т більша за кількість ребер принаймні на 2. Але це суперечить тому, що граф T має (n-1) ребро.

(III) → (IV). Вилучимо довільне ребро, отримаємо граф з n вершинами та (n-2) ребрами. Припущення про зв'язність такого графа суперечить теоремі про оцінку (знизу) кількості ребер звичайного графа (теорема 3.6).

(IV) → (V). Оскільки граф Т зв'язний, то кожну пару його вершин з'єднано принаймні одним простим шляхом (теорема 3.4). Якщо якусь пару вершин з'єднано двома простими шляхами, вони замикаються в простий цикл. Але це суперечить тому, що вилучення довільного ребра робить граф Т незв'язним.

(V) →(VI). Припустимо, що граф Т містить простий цикл. Тоді довільні дві вершини цього циклу з'єднано принаймні двома простими шляхами, що суперечить твердженню (V). Додавши тепер до графа Т ребро e, одержимо єдиний простий цикл, бо інцидентні ребру є вершини вже з'єднано в графі Т точно одним простим шляхом.

(VI) → (І). Припустимо, що граф Т незв'язний. Тоді додавання будь-якого ребра, що з'єднує вершину однієї компоненти з вершиною іншої, не зумовлює утворення простого циклу, що суперечить твердженню (VI).

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

У багатьох застосуваннях певну вершину дерева означають як корінь. Тоді можна природно приписати напрямок кожному ребру. Оскільки існує єдиний простий шлях від кореня до кожної вершини графа, то можна орієнтувати кожне ребро в напрямку від кореня. Отже, дерево разом із виділеним коренем утворює орієнтований граф, який називають кореневим деревом. Різні способи вибору кореня дають змогу утворити різні кореневі дерева.

Приклад 1.2. На рис. 1.3, а зображено дерево, а на рис. 1.3, б, в — кореневі дерева з коренями відповідно у вершинах а та с.

Рис. 1.3. Кореневі дерева

Нехай Т — кореневе дерево. Якщо v — його вершина, відмінна від кореня, то її батьком називають єдину вершину и таку, що є орієнтоване ребро (и, v). Якщо и — батько, то v — син. Аналогічно за генеалогічною термінологією можна означити інших предків і нащадків вершини V. Вершини дерева, які не мають синів, називають листками. Вершини, які мають синів, називають внутрішніми. Нехай а — вершина дерева. Тоді піддеревом із коренем а називають підграф, що містить а та всі вершини — нащадки вершини а, а також інцидентні їм ребра. Кореневе дерево називають т-арним, якщо кожна його внутрішня вершина має не більше ніж т синів. Дерево називають повним т-арним, якщо кожна його внутрішня вершина має точно т синів. У разі т=2 дерево називають бінарним. Кореневе дерево, у якому сини кожної внутрішньої вершини впорядковано, називають упорядкованим. Таке дерево зображають так, щоб сини кожної вершини були розміщені зліва направо.

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

Приклад 1.3. У дереві, зображеному на рис. 1.4, Л і П — відповідно ліве та праве піддерева у вершині с.

Рис. 1.4. Зображення піддерев

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

Доведення.Кожна вершина, окрім кореня, — син внутрішньої вершини. Оскільки кожна з і внутрішніх вершин має т синів, то всього є, якщо не враховувати корінь, ті вершин, а з урахуванням кореня їх ті+1.

Рівнем вершини v в кореневому дереві називають довжину простого шляху від кореня до цієї вершини (цей шлях, очевидно, єдиний). Рівень кореня вважають нульовим. Висотою кореневого дерева називають максимальний із рівнів його вершин. Інакше кажучи, висота кореневого дерева — це довжина найдовшого простого шляху від кореня до будь-якої вершини. Повне m-арне дерево, у якого всі листки на одному рівні, називають завершеним.

Кореневе m-арне дерево з висотою h називають збалансованим [52], якщо всі його листки на рівнях h або h- 1.

Приклад 1.4. На рис. 1.5 зображено збалансоване бінарне дерево, яке має висоту 4: усі його листки на рівнях 3 та 4.

Pис. 1.5. Збалансоване дерево.

ТЕОРЕМА 4.3.Нехай m-арне дерево має висоту h. Тоді в ньому не більше ніж т^k листків.

Доведення.Застосуємо математичну індукцію за h. У разі h = 1 твердження очевидне. Припустимо, що воно справджується для всіх m-арних дерев із меншою висотою, ніж А. Нехай Т — m-арне дерево з висотою h. Тоді його листки — це листки піддерев, отриманих із Т вилученням ребер, що з'єднують корінь дерева Т з кожною вершиною рівня 1 (рис. 1.6).

Рис. 1.6 Доведення теореми

Кожне з цих піддерев має не більшу висоту, ніж h-1. За індуктивною гіпотезою всі вони мають не більше ніж т^k^-1 листків. Позаяк таких піддерев не більше ніж т, то загальна кількість листків у дереві T не перевищує тm^k^-1 = m^k.

Наслідок.Якщо m-арне дерево з висотою h має l листків, то h ≥ [log_ml]. Якщо m-арне дерево повне та збалансоване, то h = [log_ml]. Нагадаємо, що [x]— це найменше ціле число, яке більше чи дорівнює х.

Доведення.За теоремою 1.3 l ≤ m^h. Прологарифмуємо цю нерівність за основою m: 1оg_ml ≤ h. Оскільки h — ціле, то h ≥ [log_ml]. Тепер припустимо, що дерево повне та збалансоване. Вилучимо всі листки на рівні h (разом з інцидентними їм ребрами). Одержимо завершене m-арне дерево висотою h-1. Воно має m^hлистків (див. задачу 12). Отже, m^h^-1 < 1 ≤ m^h. Звідси випливає, що h- 1 < log_ml ≤ h, тобто h = [log_ml].

12 3 4 5