Кореневе дерево. Упорядковане кореневе дерево, m-арне дерево, повне m-арне дерево.

Розглянемо кореневе дерево. У багатьох застосуваннях певну вершину дерева визначають як корінь. Дерево разом з виділеним коренем утворює орієнтований граф, який називають кореневим деревом. Вершини дерева, які не мають синів називають листками. Вершини, які мають синів, називають внутрішніми. Кореневе дерево називають m-арним, якщо кожна внутрішня вершина має не більше m синів. Дерево називають повним m-арним, якщо кожна внутрішня вершина має точно m синів. У разі m=2 дерево називають бінарним. Упорядковане кореневе дерево – це кореневе дерево, в якому сини кожної внутрішньої вершини впорядковані.

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

3. Властивості повного m-арного дерева. Рівень вершини і висота кореневого дерева. Збалансоване дерево.

Т-ма. Повне m-арне дерево з і внутрішніми вершинами містить n=m*i+1вершин.

Д-ня. Кожна вершина, за винятком кореня, є сином внутрішньої вершини. Оскільки кожна з і внутрішніх вершин має m синів, то всього є, якщо не враховувати корінь, m*i вершин. Враховуючи ще корінь, одержимо, що всього вершин n=m*i+1.

Рівнем вершини v у кореневому дереві називають довжину простого шляху від кореня до цієї вершини. Висотою кореневого дерева називають максимальний з рівнів його вершин. Завершеним m-арним деревом називають таке повне m-арне дерево, у якого все листя має 1 рівень.

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

Д-ня. (Мат. Індукція по h). У разі h=1 твердження очевидне. Припустимо, що твердження є правильним для всіх m-арих дерев з висотою меншою, ніж h. Нехай Т – m-арне дерево з висотою h. Листки дерева Т – це листки піддерев, які отримують з Т вилученням ребер, що з’єднують корінь дерева Т з кожною вершиною рівня 1. Кожне з цих дерев має висоту не більшу ніж h-1. За індуктивною гіпотезою кожне з цих дерев має не більше, ніж m^h-1 листків. Оскільки таких піддерев є не більше ніж m, то загальна к-сть листків у дереві Т не перевищує m*m^h-1=m^h.

Збалансоване дерево – це такий різновид бінарного дерева пошуку, яке автоматично підтримує свою висоту, тобто к-сть рівнів вершин під коренем, мінімальною.

4. Обхід бінарних дерев (три способи).

Існує 3 принципи впорядкування вершин, які природно випливають із структури дерева. Як і саму деревовидну структуру, їх зручно описати за допомогою рекурсії.

Обхід бінарного дерева передбачає відвідування усіх вершин бінарного дерева, при цьому кожна з вершин відвідується тільки один раз.

Існують три види таких обходів, кожний з яких визначається рекурсивно:

• прямий порядок (англ. preorder) наступної послідовності:

1. відвідати корінь

2. відвідати ліве піддерево

3. відвідати праве піддерево

Тобто, в такому порядку обходу кожна вершина відвідується до того, як будуть відвідані її діти.

• зворотний порядок (англ. postorder) наступної послідовності:

1. відвідати ліве піддерево

2. відвідати праве піддерево

3. відвідати корінь

Тобто, в такому порядку кожна вершина відвідується лише після того, як будуть відвідані її діти.

• Внутрішній порядок (англ. inorder) наступної послідовності:

1. відвідати ліве піддерево

2. відвідати корінь

3. відвідати праве піддерево

В такому порядку кожна вершина відвідується між відвіданням лівої та правої дитини. Такий порядок особливо часто застосовується в бінарних деревах пошуку, тому що дає можливість обходу вершин у порядку збільшення їхніх порядкових номерів.

Для цього бінарного дерева,

• Прямий порядок: 2, 7, 2, 6, 5, 11, 5, 9, 4
• Зворотній порядок: 2, 5, 11, 6, 7, 4, 9, 5, 2
• Центрований (центральний) порядок: 2, 7, 5, 6, 11, 2, 5, 4, 9

6.Інфіксна форма запису.

Надзвичайно поширене застосування в інформатиці обходу дерев – це співставлення виразам (арифметичним, логічним тощо) дерев, та побудова на цій основі різних форм запису виразів.

Суть справи зручно пояснити на прикладі. Розглянемо арифметичний вираз: (a+b/c)*(d-e*f). Зобразимо його у вигляді дерева. Обійдемо це дерево, виписуючи символи у вершинах у тому порядку, в якому вони зустрічаються при заданому способі обходу. У разі обходу у внутрішньому порядку – інфіксний запис (поки що без дужок, необхідний для визначення порядку операцій): a+b/c*d-e*f. Без дужок інфіксна форма запису неоднозначна: один запис може відповідати різним деревам. Щоб уникнути неоднозначності інфіксної форми, використовують круглі дужки кожного разу, коли зустрічають операцію. Повністю «одужкований» вираз отриманий у разі обходу дерева у внутрішньому порядку, називають інфіксною формою запису. Інфіксна форма запису є незручною. На практиці використовують префіксну та постфіксну форми запису, оскільки вони однозначно відповідають виразу і не використовують дужок.

7. Префіксна форма запису виразів (прямий польський запис).

На практиці використовується префіксна і постфіксна форми запису оскільки вони однозначно відповідають виразу і не використовують дужок. (польські записи). Прямий польський запис відповідає обходу дерева зверху вниз (префіксна). 1) Вівідати корінь. 2) відвідати праве піддерево. 3) відвідати ліве піддерево.

Правило обчислення значення виразу у прямому польському записі:

Для обчислення значення виразу в прямому польському записі його читають справа наліво і знаходять 2 операнди разом із знаком операції, який їм передує. Ці операнди та знак операції вилучають із запису, виконують операцію, а її результат записують на місце вилучених символів.

Розглянемо арифметичний вираз: (a+b/c)*(d-e*f). Зобразимо його у вигляді дерева. Обійдемо це дерево, виписуючи символи у вершинах у тому порядку, в якому вони зустрічаються при заданому способі обходу. У разі обходу в прямому польському записі: *+a/bc-d*ef.

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

8. Постфіксна форма запису виразів. (обернений польський запис).

На практиці використовують префіксну та постфіксну форму запису, оскільки вони однозначно відповідають виразу і не використовують дужок. (польські записи). Обернений польський запис відповідає обходу дерева знизу вверх (постфіксна). 1) Відвідати ліве піддерево, 2) Відвідати праве піддерево, 3) Відвідати корінь.

Розглянемо арифметичний вираз: (a+b/c)*(d-e*f). Зобразимо його у вигляді дерева. Обійдемо це дерево, виписуючи символи у вершинах у тому порядку, в якому вони зустрічаються при заданому способі обходу. У разу обходу в зворотньому порядку – постфіксний або обернений польський запис: abc/+def*-*.

Для обчислення значення виразу в зворотньому польському записі його читають зліва направо і виділяють два операнди разом із знаком операції після них. Ці операнди та знак операції вилучають із запису, виконують операцію, а її результат записують на місце вилучення символів.

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

9. Бінарне дерево пошуку.

Бінарне дерево забезпечуєдуже зручний метод організації даних, у разі використання якого будь-які конкретні дані можна легко знайти або виявити їхню відсутність. Єдиною вимогою є введення для даних деякого лінійного порядку. Цим порядком може бути, наприклад, алфавітний чи числовий порядок. У бінарному дереві пошуку кожній вершині присвоєне значення, яке називають ключем. Ключ – це елемент деякої лінійно впорядкованої множини: будь-які два елементи цієї множини можна порівняти. В алгоритмі побудови бінарного дерева пошуку використовують його рекурсивну властивість, яку описують так. Кожна вершина розбиває дерево на 2 піддерева. Ліве піддерево містить лише ключі, менші від ключа цієї вершини, а праве – ключі, більші від ключа вершини. Ця властивість повторюється рекурсивно для кожної вершини.

Алгоритм додавання об’єктів в дерево:

Крок 1. Почати з кореня: присвоїти кореню перший об’єкт списку як ключ.

Крок 2. Якщо об’єкт < від ключа у вершині, то перейти до лівого сина.

Крок 3. Якщо об’єкт > від ключа у вершині, то перейти до правого сина.

Крок 4. Повторювати кроки 2 та 3 доки не досягнемо вершини, яка не визначена.

Крок 5. Якщо вершина, яка досягнута, не визначена, то визначити (додати) вершину з новим об’єктом як ключем.

Алгоритм пошуку елемента в дереві:

Крок 1. Почати з кореня.

Крок 2. Якщо об’єкт < від ключа у вершині, то перейти до лівого сина.

Крок 3. Якщо об’єкт > від ключа у вершині, то перейти до правого сина.

Крок 4. Якщо об’єкт = ключу у вершині, то об’єкт знайдено. Виконати потрібні дії і вийти.

Крок 5. Повторювати кроки 2, 3, 4 доки не досягнемо вершини, яка не визначена.

Крок 6. Якщо досягнута вершина не визначена, то даний об’єкт не зберігається у дереві. Виконати потрібні дії і вийти.

10. Дерево прийняття рішень.

Кореневі дерева можна використовувати для розв’язування задач прийняття рішень. Для цього використовують дерева прийняття рішень, або дерева рішень. Кожному листку такого дерева поставлено у відповідність рішення зі скінченної множини відомих рішень, а кожній внутрішній вершині v – перевірку умови P(v). Прийняття рішень за допомогою такого дерева полягає в побудові простого шляху від кореня до листка. У процесі побудови шляху виконують перевірку умов у внутрішніх вершинах дерева. Значення умови P(v) у вершині v визначає ребро, яке буде додано в шлях після вершини v. Кінцева вершина побудованого шляху вказує прийняте рішення. У багатьох практичних задачах потрібно приймати рішення відносно досліджуваних об’єктів віднесенням їх до певних класів, тобто наданням цим об’єктам класифікаційних ознак. Якщо ці класифікації наперед відомі, то задачі називають задачами класифікації.

Система прийняття рішень – це інформаційна система вигляду D=(W, A {d}), де d не належить А – атрибут прийняття рішень. Цей атрибут може набувати декількох значень, однак найчастіше використовують значення {0, 1} або {Yes, No}. Систему прийняття рішень можна зобразити у таблиці, у якої останній стовпчик позначено атрибутом прийняття рішень. Таку таблиці називають таблицею прийняття рішень.

11. Алгоритм бектрекінг. Приклади: пошук гамільтонових циклів у графі, задача про n ферзів та інші задачі.

Основна ідея методу полягає в тому, що розв’язок будується поступово починаючи або з третьої порожньої послід. (довжини 0), або з однойменної послід. (довжини 1). Тобто, якщо ми маємо деякий частковий розв’язок х₁, …, х _і, то намагаємось знайти таке допустиме значення x_i+1, що не виключає можливість продовження до повного розв’язку. Якщо таке допустиме, але ще не використане значення х_і+1 існує то долучаємо цю нову компоненту до часткового розв’язку і продовжуємо процес до послід. х₁,.., х_і, х_і+1. Якщо значення х_і+1 не існує то повертаємось назад до попередньої послід. х₁, …, х_і-1 і продовжуємо процес шукаючи нове, ще не використане значення х_і^’ і так далі.

Побудова гамільтонових циклів.

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

Задача про n ферзів.

Як n ферзів можна розмістити на шахівниці nxn так, щоб жодні 2 не били один одного? Для розв’язування цієї задачі потрібно визначити n позицій на шахівниці nxn так, щоб жодні 2 позиції не були в одному рядку, в одному стовпчику і в одній діагоналі. Діагональ містить усі позиції з координатами (i, j) такі, що i+j=m для деякого m, або i-j=m (i – номер рядка, j – номер стовпця). Починаємо з порожньої шахівниці. На (k+1)-му кроці намагаємось поставити нового ферзі в (k+1)-му стовпці, причому в перших k стовпцях уже є ферзі. Перевіряємо клітинки в (k+1)-му стовпці, починаючи з верхньої, а саме, шукаємо таку позицію для ферзі, щоб він не був у рядку та діагоналі з тими ферзями, які вже є на шахівниці. Якщо це неможливо, то повертаємось до місця ферзя на попередньому k-му кроці і розміщаємо цього ферзя на наступному можливому рядку в цьому k-му стовпці, якщо такий рядок є. Якщо немає, то повертаємось до ферзя у (k-1)-му стовпці.

12. Каркаси графів. Способи їх побудови.

Нехай G – простий зв’язний граф. Каркасом, або з’єднувальним деревом графа G називають його підграф, який є деревом і містить всі вершини графа G. Нехай граф G має n вершин та m ребер. Для того, щоб отримати каркас, можна використати процедуру вилучення ребер, що належать простим циклам. У такому разі, очевидно, потрібно вилучати ϒ (G)=m-(n-1)=m-n+1 ребер. Число ϒ (G) – називають цикломатичним числом графа G. Побудова каркаса є поширеною задачею. Алгоритм, який полягає у вилученні ребер з простих циклів, не ефективний для комп’ютерної реалізації. Такий алгоритм вимагає ідентифікації простих циклів, що є складною задачею. Ефективним для комп’ютерної реалізації алгоритмом побудови каркаса є послідовний добір ребер у каркас. Це можна здійснити за допомогою обходу графа G як пошуком вглиб, так і пошуком вшир. Під час виконання цих алгоритмів природним чином будують каркас.

Т-ма. Нехай Т – каркас графа G, побудований пошуком вшир, починаючи з вершини R, тоді шлях із а до довільної вершини v в Т є найкоротшим шляхом із а до v у графі G.

Д-ня ґрунтується на аналізі алгоритму пошуку вшир у графі G і пропонується як вправа.

Зауваження. Якщо для побудови дерева найкоротших шляхів від вершини а використати алгоритм Дейкстри (вважаємо, що довжина кожного ребра =1), то отримаємо те саме дерево, що і у разі використання алгоритму пошуку вшир.

13. Задача про мінімальний каркас. Алгоритм Краскала.

Алгоритм Краскала:

Нехай G – зв’язний зважений граф з n вершинами.

1. Вибрати ребро e₁, яке має в G найменшу вагу.

2. Індуктивно визначити послідовність ребер e₂, e₃, …, e_n-1; на кожному кроці вибирати ребро (відмінне від попередніх) з найменшою вагою і таке, що не утворює простих циклів з попередньо вибраними ребрами. Отримане дерево Т з множиною ребер ЕТ={e₁, e₂, e₃, …, e_n-1} є мінімальним каркасом графа G.

Розглянемо одну із можливих реалізацій алгоритму Краскала.

Початок. Упорядкувати множину ребер за зростанням ваг: e₁, e₂, e₃, …, e_m. Виконати розбиття множини вершин: ρ ₁={{v₁}, {v₂}, …, {v_n}}.

Ітерація. Вибрати таке чергове ребро із упорядкованої послідовності ребер, що його кінці містяться в різних множинах розбиття (це забезпечує відсутність простих циклів). Якщо вибране ребро е_і={v, w}, то множини, що містять вершини v та w, об’єднати в одну множину.

Закінчення. Роботу закінчити, коли буде вибране (n-1) ребро, при цьому всі підмножини розбиття об’єднаються в одну.

14. Відношення. Означення відношення із однієї множини в іншу, n-арні відношення. Означення відношення на множині. Бінарні відношення. Властивості відношень. Способи задання бінарних відношень.

Відношенням (n-місним відношенням) в теорії множин називається підмножина декартового степеня Mⁿ деякої множини M. Кажуть також, що елементи a₁, a₂,..., a_n∈ M знаходяться у відношенні R, якщо кортеж (a₁, a₂,..., a_n)∈ R.

Бінарне відношення з А в В – це деяка підмножина декартового добутку АхВ цих множин. Бінарні відношення описують зв’язки між елементами двох множин. Зв’язки між елементами більше, ніж 2 множин задають n-арними відношеннями. Здебільшого розглядають бінарні відношення за умови А=В. Відношенням на множині А називають бінарне відношення з А в А. Задати бінарне відношення на множині А можна за допомогою мулевої матриці або орієнтованого графа. Матриця, яка задає відношення R на n-елементній множині А, - це nxn матриця. М_R=[m_ij], i, j = 1, …, n, де

1, якщо (а_і, a_j)єR

m_ij=

0, якщо (а_і, a_j)не належить R

Граф G_R, який задає відношення R на множині А, будують так. Вершини графа позначають елементами цієї множини, а дуга (а_і, a_j) існує тоді і лише тоді, коли (а_і, a_j)єR. Такий граф G_R називають графом, асоційованим із відношенням R, або просто графом відношення R.

Властивості відношень на множині А:

Відношення R на множині А називають рефлексивним, якщо для будь-якого аєА виконується (а, a)єR. Відношення R на множині А називають симетричним, якщо для будь-яких a, bєA виконується умова: з того, що (a, b) єR випливає, що (b, a) єR. Відношення R на множині А називають антисиметричним, якщо для всіх a, bєA виконується умова: з того, що (a, b) єR та (b, a) єR випливає, що a=b. Відношення називають транзитивним, тоді і тільки тоді, що якщо пари (a, b) та (b, c) належать цим відношенням, то й пара (a, c) теж їм належить.

15. Відношення еквівалентності.

Розглянемо відношення, які одночасно мають декілька властивостей у потрібній комбінації. Відношення на множині А називають відношенням еквівалентності, якщо воно рефлексивне, симетричне й транзитивне. Два елементи множини А, які зв’язані відношенням еквівалентності, називають еквівалентними.

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

З відношенням еквівалентності тісно пов’язане поняття класу еквівалентності й розбиття множини на класи. Нехай R є відношенням еквівалентності на множині А. Множину всіх елементів, які еквівалентні де елемента аєА, називають класом еквівалентності (елемента а). Клас еквівалентності, який породжений елементом а за відношенням R, позначають [a]_R. Якщо мають на увазі певне відношення еквівалентності, то позначають [a]. Отже: [a]_R={s|(a, s)єR}. Якщо bє[a]_R, то b називають представником цього класу еквівалентності.

Т-ма. Нехай R – відношення еквівалентності на множині А. Тоді такі твердження рівносильні:

(I) aRb

(II) [a]=[b]

(III) [a] [b]

Кожне відношення еквівалентності породжує розбиття множини А (на класи еквівалентності).

16. Відношення часткового порядку.

Відношення R на множині А називають відношенням часткового порядку (або частковим порядком), якщо воно рефлексивне, антисиметричне, транзитивне. Множину А із частковим порядком R називають частково впорядкованою множиною і позначають (A, R).

Два елементи a та b частково впорядкованої множини (A, R)називають порівняльними, якщо aRb або bRa. Якщо а та b такі елементи, що ані aRb, ані bRa, то їх називають непорівняльними.

Якщо (A, R) частково впорядкована множина, й якій будь-які 2 елементи порівняльні, то таку множину називають тотально, або лінійно впорядкованою, а частковий порядок R називають тотальним, або лінійним порядком.

Елемент частково впорядкованої множини називають максимальним, якщо він не менший від будь-якого елемента цієї множини. Отже, а є максимальним елементом частково впорядкованої множини (A, R), якщо не існує такого bєA, що а передує b (а менше b).

Аналогічно, елемент називають мінімальним, якщо він не більший від будь-якого елемента частково впорядкованої множини. Отже, а є мінімальним, якщо не існує такого bєА, що b передує а (b менше а). Мінімальні та максимальні елементи легко визначити на діаграмі Хассе – це, відповідні, «верхні» і «нижні» її елементи. («верхні» елементи не мають висхідних ребер, а «нижні» - низхідних).

17. Рефлексивне замикання відношення. Симетричне замикання відношення.

Нехай R – відношення на множині А. Відношення R може не мати деяких властивостей. Наприклад, воно може не бути рефлексивним або симетричним.

Замикання відношення R за властивістю Р називають найменше відношення С, яке має властивість Р і таке, що R (підмножина) С. Термін «найменше відношення», означає, що С є підмножиною будь-якого відношення S, для якого виконуються умови:

1) S має властивість Р,

2) R підмножина S.

Можна довести, що замикання відношення R за властивістю Р, якщо воно існує, є перетином усіх відношень із властивістю Р, які містять R. За властивість Р можна розглядати рефлективність, симетричність, транзитивність. Отже, розглянемо рефлексивне замикання, симетричне замикання та транзитивне замикання відношення R.

Рефлексивне замикання R дорівнює R , ={(a, a)|aєR}. Відношення множині А називають діагональним. Якщо звернутись до орієнтованого графа, асоційованого з відношенням R, то рефлексивному замиканню відповідатиме граф, який отримують з даного графа додаванням петель у тих вершинах, де їх немає.

Для отримання симетричного замикання відношення R потрібно додати всі такі пари (b, a), що (b, a)не належить R, але (a, b)єR. Отже, симетричне замикання відношення R дорівнює R R^-1. Де R^-1={(b, a)|(a, b)єR}. Це можна сформулювати й у термінах графа, асоційованого з відношенням R: якщо є дуга (a, b), але немає (b, a), то додати таку дугу.

18. Транзитивне замикання відношення. З’єднувальне відношення.

Побудова транзитивного замикання відношення є складнішою задачею, ніж побудова рефлексивного або симетричного замикання. Шляхом у відношенні R з а в b називають послідовність елементів a, x₁, x₂, …, x_n-1, b множини А таких, що (а, х₁)єR, (х₁, х₂)єR, …, (х_n-1, b)єR. Покажемо, що процедура відшукання транзитивного замикання відношення R еквівалентна процедурі визначення, які пари вершин з’єднані шляхом. Зазначимо, що шлях у відношенні R з а в b відповідає шляху з вершини а у вершину b в асоційованому графі G_R.

Нехай R – відношення на множині А. З’єднувальним називають відношення R^*, яке складається з таких пар (а, b), що існує шлях з а в b у відношенні R. Отже, R^*= .

Т-ма. Транзитивне замикання відношення R дорівнює з’єднувальному відношенню R^*.

Т-ма. Нехай множина А має n елементів і R – відношення на множині А. Тоді

R^*= =R

З цієї теореми випливає таке матричне зображення для відношення R^*:

v M_R^[2] v … v M_R^[n].

Алгоритм, O(n⁴) операцій для обчислення матриці М_R*.