ДЕРЕВА. АЛГОРИТМИ ПОБУДОВИ ОСТОВНОГО ДЕРЕВА

5.1 Мета заняття

Ознайомлення на практичних прикладах з поняттям «дерево», з основними властивостями дерев та їх видами. Вивчення способів переліку графів і дерев. Ознайомлення з основними алгоритмами побудови дерев. Вивчення алгоритму побудови остовного дерева пошуком углиб.

5.2 Методичні вказівки з організації самостійної роботи студентів

Під час підготовки до практичного заняття необхідно повторити лекційний матеріал, розділи літератури [1–8, 10–12] з таких питань: визначення дерева; властивості дерев; перелік графів і дерев (неізоморфних, кореневих, позначених); використання теорії переліку конфігурацій, що створена Д. Пойа, при обчисленні кількості неізоморфних графів; використання формули А. Келі для підрахування числа позначених дерев з вершинами; остови графа, перелік остовів для повного (простого) графа; перелік остовів графа у загальному випадку (теорема Кірхгофа); алгоритм побудови остовного дерева (пошук углиб); алгоритм побудови остовного дерева шляхом довільного перегляду ребер; алгоритми побудови остова мінімальної ваги (алгоритм Дж. Краскала, алгоритм Р. Прима); орієнтовані та бінарні дерева; правила обходу бінарних дерев; правило побудови бінарного дерева з будь-якого дерева.

Підготовка і виконання практичного заняття проводиться у два етапи. Перший етап пов’язаний з вивченням на практичних прикладах таких основних понять і визначень: дерево; центр дерева; ліс; позначений граф; однакові позначені графи; кількість неорієнтованих, простих, позначених графів; кількість неізоморфних (простих, неорієнтованих) графів без позначок; кількість позначених дерев; кількість звичайних (неізоморфних) дерев з вершинами; корінь дерева; кореневе дерево; остовний підграф (остов, каркас графа); матриця Кірхгофа простого графа; зважений граф; остів мінімальної ваги; вага підграфа; орієнтоване дерево; нащадок вершини; предок вершини; «батько» для вершини; «син» для вершини; лист; глибина вершини; висота вершини; висота дерева; рівень вершини; упорядковане дерево; бінарне (двійкове) дерево; ліве піддерево; праве піддерево; еквівалентне бінарне дерево.

Під час виконання першого етапу практичного заняття студент має запропонувати і записати індивідуальний приклад для кожного з розглянутих вище понять і визначень. Другий етап виконання практичного заняття пов’язаний з розв’язанням практичних завдань, поданих у підрозділі 5.3, на основі запропонованих типових прикладів (див. підрозділ 5.4).

5.3 Контрольні запитання і завдання

5.3.1 Контрольні запитання

1. Який граф називається деревом? Наведіть приклади дерев.

2. Що називається лісом у теорії графів?

3. Перелічіть основні властивості дерев.

4. Який граф називається позначеним?

5. Які два позначених графа не різняться (є однаковими)?

6. Якою формулою можна скористатися для визначення кількості неорієнтованих позначених простих графів з вершинами та ребрами?

7. Якою формулою можна скористатися для визначення кількості неізоморфних позначених дерев?

8. Як визначити число неізоморфних графів без позначок?

9. У яких випадках використовується формула А. Келі? Наведіть цю формулу.

10. Дайте визначення остову (каркасу) графа.

11. Наведіть приклад складання матриці Кірхгофа простого графа.

12. Для розв’язання яких задач використовується теорема Кірхгофа?

13. Перелічить основні алгоритми побудови остовів графа.

14. Наведіть алгоритм Дж. Краскала для побудови остова мінімальної ваги.

15. Дайте визначення орієнтованих і бінарних дерев.

16. Охарактеризуйте способи обходу бінарного дерева.

17. Поясніть правило побудови бінарного дерева з будь-якого дерева.

5.3.2 Контрольні завдання

Завдання 1. Підрахувати кількість позначених неорієнтованих простих графів з вершинами і ребрами та нарисувати декілька з таких графів.

Завдання 2. Підрахувати кількість усіх позначених неорієнтованих простих графів з вершинами та нарисувати ці графи.

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

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

Завдання 5. Знайти кількість усіх позначених неорієнтованих дерев з вершинами. Нарисувати 10 таких дерев.

Завдання 6. Знайти кількість простих неорієнтованих неізоморфних дерев з вершинами. Нарисувати такі дерева.

Завдання 7. Знайти кількість кореневих дерев з вершинами. Нарисувати такі дерева.

Завдання 8. Визначити кількість остовів (каркасів, кістяків) графа , зображеного на рис. 5.1. Наведіть зображення п’яти будь-яких остовів.

Рисунок 5.1 – Граф , для якого визначається кількість остовів

Завдання 9. Скільки остовних дерев є у графів Понтрягіна-Куратовського ( і )?

Завдання 10. Скільки остовних дерев має граф ? Скільки остовних дерев має граф ?

Завдання 11. Використовуючи матричну формулу Кірхгофа (теорему Кірхгофа), визначити число остовних дерев для кожного з графів, зображених на рис. 5.2.

Рисунок 5.2

Завдання 12. Задаються графи на рис 5.3. Вершини графів упорядковані так, як позначені. Знайти остовні дерева графів пошуком углиб.

Рисунок 5.3

Завдання 13. Для дерева, зображеного на рис. 5.4, визначити: висоту дерева; рівень вершини ; рівень вершини ; рівень вершини ; вершину, яка є предком вершини ; вершини, які є синами вершини ; листи дерева. Відповідь дати для: а) якщо коренем вибрана вершина ; б) якщо коренем вибрана вершина ; в) якщо коренем вибрана вершина ; г) якщо коренем вибрана вершина ; д) якщо коренем вибрана вершина .

Рисунок 5.4

5.4 Приклади аудиторних і домашніх завдань

Завдання 1. Чому дорівнює кількість позначених неорієнтованих простих графів з вершинами і ребрами? Нарисувати усі ці графи.

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

Тому . Ці три графа зображено на рис. 5.5.

Рисунок 5.5 – Позначені неорієнтовані прості графи з
вершинами і ребрами

Завдання 2. Чому дорівнює кількість усіх позначених неорієнтованих простих графів з вершинами? Нарисувати усі ці графи.

Розв’язок. Кількість позначених неорієнтованих простих графів з вершинами і ребрами дорівнює , де . Сумуючи числа за всіма можливими кількостями ребер від випадку безреберного графа до випадку повного графа з вершинами, одержуємо число усіх позначених графів з вершинами . Якщо , то і . Усі позначені неорієнтовані прості графи з вершинами наведено на рис. 5.6.

Рисунок 5.6 – Позначені неорієнтовані прості графи з вершинами

Завдання 3. Знайти на рис. 5.6, де подані неорієнтовані прості графи з вершинами, попарно неізоморфні графи без позначок, нарисувати їх, підрахувати кількість таких графів.

Розв’язок. Число попарно неізоморфних графів без позначок з вершинами дорівнює =4. Ці графи наведено на рис. 5.7.

Рисунок 5.7 – Неізоморфні неорієнтовані прості графи з вершинами

Завдання 4. Чому дорівнює кількість усіх позначених неорієнтованих дерев з вершинами? Нарисувати усі ці дерева.

Розв’язок. За формулою Келі число позначених дерев з вершинами дорівнює , тому кількість усіх позначених неорієнтованих дерев з вершинами буде .

Усі ці позначені дерева наведено на рис. 5.8.

Рисунок 5.8 – Позначені неорієнтовані дерева з вершинами

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

Розв’язок. Число звичайних (неізоморфних) дерев дорівнює 1. Це дерево наведено на рис. 5.9.

Рисунок 5.9 – Дерево з вершинами

Завдання 6. Чому дорівнює кількість кореневих дерев з вершинами? Нарисувати усі ці дерева.

Розв’язок.

Усі кореневі дерева з числом вершин зображені на рис. 5.10.

Рисунок 5.10 – Кореневі дерева з вершинами

Завдання 7. Нехай – зв’язний граф з позначеними вершинами. Знайти кількість остовних дерев графа , який зображено на рис. 5.11.

Рисунок 5.11 – Граф

Розв’язок. Для розв’язання завдання використаємо теорему Кірхгофа (матричну формулу Кірхгофа), тобто число остовних дерев у простому зв’язному графі з вершинами () дорівнює алгебраїчному доповненню будь-якого елемента матриці Кірхгофа .

Матриця Кірхгофа складається з таких елементів

Запишемо матрицю Кірхгофа для графа

.

Розрахуємо алгебричне доповнення елемента матриці

.

Існує вісім остовних дерев графа .

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

Рисунок 5.12 – Граф

Розв’язок. Для розв’язання завдання використаємо такий алгоритм пошуку остовного дерева вглиб.

Крок 1. Позначити кожну вершину графа символом .

Крок 2. Вибрати довільний елемент графа та назвати його коренем дерева.

Крок 3. Замінити позначку вершини з «нов» на «вик» і назначити .

Крок 4. Поки є вершини, які ще не вибрані, суміжні з , виконати такі дії:

а) вибрати вершину , суміжну з ;

б) якщо має позначку «нов», додати () в множину (множину ребер остовного дерева, яке будується), замінити позначку на «вик», позначити і повторити крок 4;

в) якщо має позначку «вик» і не є «батьком» , додати () в множину (множину зворотних ребер) і повторити крок 4.

Крок 5. Якщо , позначити і повторити крок 4. Поки для вершини є суміжна невикористана вершина , продовжується шлях від до . Тільки в тому випадку, коли рухатися далі не можна, переходимо до кроку 5, повертаємося до «батька» вершини .

Використаємо цей алгоритм для пошуку остовного дерева графа , зображеного на рис. 5.12.

Як корінь довільним способом виберемо вершину . Змінюємо позначку з «нов» на «вик». Оскільки вершина суміжна з і має позначку «нов», додаємо ребро в множину і замінюємо позначку вершини на «вик», як зображено на рис. 5.13, а).

Рисунок 5.13

Від вершини переходимо до вершини , оскільки вона є суміжною з . Вершина має позначку «нов», тому додаємо ребро в множину і заміняємо позначку вершини на «вик», як зображено на рис. 5.13, б).

Тепер вибираємо вершину, яка суміжна з вершиною . Можна вибрати або . Вибір визначає форму дерева, тому пошук углиб не продукує дерево єдиним способом. Припустимо, що наступною вершиною буде вершина . Вершина має позначку «нов», тому додаємо ребро в множину і замінюємо позначку вершини на «вик», як зображено на рис. 5.13, в).
З вершини вибираємо вершину , оскільки вона є суміжною з . Вершина має позначку «нов», тому додаємо ребро в множину і замінюємо позначку вершини на «вик», як зображено на рис. 5.13, г). З вершини вибираємо вершину , оскільки вона є суміжною з вершиною . Однак вершина вже має позначку «вик», тому додаємо ребро в множину , як зображено на рис. 5.14, а).

Рисунок 5.14

Оскільки більше немає ребер для перевірки на суміжність з вершиною , окрім «батька», повертаємося до вершини (далі не будемо згадувати «батька» як можливу суміжну вершину). Інших ребер для перевірки на суміжність з вершиною теж немає, тому повертаємось до . Тут єдиною вершиною для перевірки є вершина , але вершина вже має позначку «вик», тому ребро додаємо в і повертаємось до вершини , як зображено
на рис. 5.14, б).

Ребер для перевірки на суміжність з вершиною більше немає, тому повертаємось до вершини . Зауважимо, що, якби була можливість досягти кожну вершину, побудувавши шлях з , то поки дерево не побудовано повністю, не треба було б повертатися до вершини . Повернувшись до вершини , можна вибрати або . Припустимо, що вибрали вершину . Оскільки вершина має позначку «нов», додаємо ребро в множину і замінюємо позначку вершини на «вик», як зображено на рис. 5.14, в).

Вершина суміжна з вершиною і має позначку «нов». Додаємо ребро в множину і замінюємо позначку вершини на «вик», як зображено на рис. 5.15, а).

Припустимо тепер, що вибрана вершина , оскільки вона є суміжною з вершиною . Але вершина вже має позначку «вик», тому ребро додаємо в і повертаємось до вершини , як зображено на рис. 5.15, б).

Оскільки вершина суміжна з , додаємо ребро в множину і замінюємо позначку вершини на «вик», як зображено на рис. 5.15, в).

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

Рисунок 5.15

Остовним деревом графа є дерево, зображене на рис. 5.16.

Рисунок 5.16

Завдання 9. Нехай існує орієнтоване упорядковане дерево (рис. 5.17). Для цього дерева визначити: висоту дерева; глибину, висоту, рівень вершини 8; листя, їх рівні, глибину, висоту.

Рисунок 5.17 – Кореневе дерево, упорядковане за рівнями

Розв’язок. Дерево упорядковане, множина синів кожної вершини упорядкована зліва направо: . Висота дерева, яке зображене на рис. 5.17, тобто кількість дуг найдовшого шляху (висота кореня) дорівнює 3. Вершина 8 має глибину 2, тобто довжина шляху з кореневої вершини до вершини 8 дорівнює 2. Вершина 8 має висоту 1, тобто довжина найдовшого шляху з вершини 8 до будь-якого листа (до листа 9) дорівнює 1. Рівень вершини 8, тобто різниця між висотою всього дерева і глибиною цієї вершини, дорівнює 1.

Листям дерева є вершини 3, 5, 7, 9. Їхні рівні та глибина такі: листя 3,7 мають рівень 1, глибину 2; листя 5, 9 мають рівень 0, глибину 3. Висота будь-якого листа дорівнює 0.

6 ВІДШУКАННЯ НАЙКОРОТШИХ ВІДСТАНЕЙ
МІЖ ВЕРШИНАМИ ГРАФА (МЕРЕЖІ)

6.1 Мета заняття

Ознайомлення з основними методами та алгоритмами розв’язку задач відшукання оптимальних шляхів в орієнтованих графах (алгоритмами Дейкстри, Форда, Флойда, Данцига). Вивчення формального опису алгоритму Дейкстри побудови найкоротших шляхів із вершини графа. Використання алгоритму Дейкстри для знаходження відстані між парами вершин в орієнтованих і неорієнтованих графах для побудови остовного орієнтованого дерева графа.

6.2 Методичні вказівки з організації самостійної роботи студентів

Під час підготовки до практичного заняття необхідно повторити лекційний матеріал, розділи літератури [1–8, 10–12] з таких питань: постановка задачі відшукання найкоротших відстаней між вершинами графа (мережі) із заданими вагами ребер; задача пошуку оптимальних шляхів в орієнтованих мережах; економічний зміст задачі відшукання найкоротших відстаней між вершинами графа (мережі) із заданими вагами ребер; алгоритми розв’язку
задач відшукання оптимальних шляхів в орієнтованих мережах (алгоритми Дейкстри, Форда, Флойда, Данцига); складність алгоритму Дейкстри.

Підготовка і виконання практичного заняття проводиться у два етапи.

Перший етап пов’язаний з вивченням на практичних прикладах таких основних понять і визначень: шлях; маршрут; орієнтований маршрут; довжина (вага) дуги (ребра); довжина маршруту; зважений граф; відстань між вершинами графа; мінімальна сума ваг дуг; найкоротший шлях з вершини до вершини графа.

Виконуючи перший етап практичного заняття, студент має запропонувати і записати індивідуальний приклад для кожного з розглянутих вище понять і визначень. Другий етап виконання практичного заняття пов’язаний з розв’язанням практичних завдань, поданих у підрозділі 6.3, на основі запропонованих типових прикладів (див. підрозділ 6.4).

6.3 Контрольні запитання і завдання

6.3.1 Контрольні запитання

1. Який граф називається зваженим графом?

2. Що є вагою (довжиною) ребра графа?

3. Наведіть постановку задачі відшукання найкоротших відстаней між вершинами графа (мережі) із заданими вагами ребер.

4. Який економічний зміст мають задачі відшукання найкоротших відстаней між вершинами графа (мережі) із заданими вагами ребер?

5. Поясніть ідею алгоритму Е. Дейкстри, який використовується для розв’язання задачі відшукання найкоротших відстаней між вершинами графа.

6. Наведіть формальний опис алгоритму Дейкстри побудови найкоротших шляхів із вершини графа.

7. Як можна оцінити складність алгоритму Дейкстри?

8. Якщо у графі є дуги з від’ємними і додатними вагами, чи знаходить алгоритм Дейкстри найкоротший шлях?

9. Поясніть, чим відрізняється алгоритм Форда від алгоритму Дейкстри при побудові найкоротших шляхів у графі.

10. Опишіть алгоритм Флойда пошуку найкоротших шляхів між усіма парами вершин графа.

11. Опишіть алгоритм Данцига пошуку найкоротших шляхів графа.

6.3.2 Контрольні завдання

Завдання 1. Нехай потрібно знайти відстань до всіх вершин графа (рис. 6.1) від його вершини . Ваги дуг, що дорівнюють цілим числам, вказано на рис. 6.1.

Рисунок 6.1

Завдання 2. За допомогою алгоритму Дейкстри побудувати остовне дерево найкоротших шляхів із вершини до вершин графа , зображеного на рис. 6.2. Кожне орієнтоване ребро з вагою розглядається як пара протилежно спрямованих дуг з однаковими вагами .

Рисунок 6.2

Завдання 3. Знайти відстань від вершини до всіх інших вершин і найкоротший шлях між вершинами і орграфа , який задано такою матрицею відстаней

,

де – довжина (вага) дуги між вершиною і вершиною .

Завдання 4. Знайти відстань від вершини до вершини і всі найкоротші шляхи між цими вершинами для орграфа , який задається матрицею відстаней

.

6.4 Приклади аудиторних і домашніх завдань

Завдання 1. Нехай задається зважений граф (рис. 6.3), множина вершин якого є , ваги дуг, що дорівнюють цілим числам, вказано на рис. 6.3. Необхідно знайти найкоротший шлях між вершинами і , вказати найкоротші шляхи меншої довжини з вершини до відповідних вершин.

Рисунок 6.3

Розв’язок.

Введемо позначення: – вага (довжина) дуги , – довжина -шляху або позначка вершини на цьому кроці, – довжина
-шляху або позначка вершини на попередньому кроці.

Цикл 1.

Крок 1. Привласнення початкових значень.

– постійна позначка; фарбується.

– тимчасові позначки вершин . Припускаємо, що .

Крок 2. Розгляд вершини (). Оновлення позначок.

.

Крок 3. Розгляд вершини (). Перетворення позначки на постійну.

.

Вершина одержує постійну позначку , вершина – фарбується разом з дугою . Поточне дерево найкоротших шляхів з вершини містить вершини і дугу (рис. 6.4). Припускаємо .

Рисунок 6.4 – Зростаючі орієнтовані дерева найкоротших шляхів

Цикл 2.

Крок 2. Розгляд вершини . Оскільки , переходимо до
кроку 2 при . Здійснюємо оновлення позначок.

.

Крок 3. Розгляд вершини . Перетворення позначки на постійну.

.

Вершина одержує постійну позначку , вершина – фарбується разом з дугою . Поточне дерево найкоротших шляхів складається з вершин і дуг , (див. рис. 6.4).

Припускаємо .

Цикл 3.

Крок 2. Розгляд вершини . Оскільки , переходимо до кроку 2 при . Здійснюємо оновлення позначок.

.

Крок 3. Розгляд вершини . Перетворення позначки на постійну.

.

Вершина одержує постійну позначку , вершина і дуга фарбується. Поточне дерево найкоротших шляхів складається з вершин і дуг , , (див. рис. 6.4).

Припускаємо .

Цикл 4.

Крок 2. Розгляд вершини . Оскільки , здійснюємо оновлення позначок.

.

Крок 3. Розгляд вершини (). Перетворення позначки на постійну.

.

Вершина одержує постійну позначку

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: