Дискретна математика для програмістів
Ознайомлення з історією виникнення теорії множин. Способи опису характеристичних властивостей множин. Декартовий добуток та бінарні відношення. Ін’єктивні, сюр’єктивні та бієктивні відображення. Поняття та властивості бінарної алгебраїчної операції.
| Рубрика | Математика |
| Вид | лекция |
| Язык | украинский |
| Дата добавления | 28.10.2014 |
| Размер файла | 2,5 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Розв'язання:
Список ребер, записаний відповідно до матриці інцидентності орієнтованого графа має вигляд:
|
Ребро |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||
|
Вершини |
початок |
b |
b |
c |
c |
d |
d |
e |
a |
|
|
кінець |
a |
c |
c |
d |
d |
e |
f |
f |
У визначенні уведене поняття ізоморфних графів. Чи можливо встановити, чи є графи ізоморфними за їхніми матрицями інцидентності, суміжності, або списку ребер?
Для перевірки ізоморфності графів і за матрицею суміжності необхідно визначити, чи існує така перестановка рядків і стовпців у матриці суміжності , щоб у результаті вийшла матриця . Із цією метою треба зробити всі можливі перестановки рядків і стовпців (а їхня максимальна кількість дорівнює •)! Якщо після однієї із цих перестановок матриці суміжності тотожньо збіжаться, то графи ізоморфні.
Для перевірки ізоморфності графів і за матрицею інцидентності (і списку ребер) необхідно визначити, чи існує така перестановка рядків і стовпців у матриці інцидентності , щоб у результаті вийшла матриця . Із цією метою треба зробити всі можливі пари перестановок рядків і стовпців (а їхня максимальна кількість дорівнює )! Якщо після однієї із цих перестановок матриці інцидентності тотожно збіжаться, то графи ізоморфні.
І в першому, і в другому випадку це досить трудомісткі операції, і рішення задачі "вручну" не завжди виправдано. Найчастіше изоморфність графів простіше встановити з їх графічних подань.
5.3 Зв'язність графа. Маршрути, шляхи, ланцюги, цикли
5.3.1 G _ неорієнтований граф
Визначення. Маршрутом (шляхом) у графі називається така послідовність ребер , у якій кожні два сусідніх ребра і мають загальну вершину. У маршруті те саме ребро може зустрічатися кілька разів. Іншими словами маршрут - це сукупність ребер, які об'єднані разом вершинами так, що можна рухатися по них уздовж графа.
Визначення. Початок маршруту - це вершина , інцидентна ребру і не інцидентна ребру . Кінець маршруту - це вершина інцидентна ребру і не інцидентна . Якщо ребра , ( , ) _ кратні, то необхідно додатково вказувати, яку із двох інцидентних вершин вважати початком (кінцем) маршруту.
Визначення. Маршрут довжини _ послідовність, що містить ребер. Іншими словами, довжиною маршруту називається кількість ребер у ньому; при цьому кожне ребро враховується стільки разів, скільки разів воно зустрічається в маршруті.
Позначення маршруту з у _ послідовністю надлишкове, тому ми будемо позначати маршрут як .
Визначення. Маршрут, всі ребра якого різні, називається ланцюгом. Ланцюг, що не перетинає себе, тобто не має вершин, що повторюються, називається простим.
Приклад. Визначити можливі маршрути (і їхню довжину) з вершини в у графі, зображеному на наступному рисунку.
Розв'язання: з вершини у ведуть, наприклад, шляхи:
1) _ довжини 2; 5) _ довжини 6;
2) _ довжини 4; 6) _ довжини 6;
3) _ довжини 4; 7) _ довжини 8;
4) _ довжини 6; 8) _ довжини 10.
Шляхи: 6), 8) не є простими.
Визначення. Маршрут, у якому збігаються початок і кінець _ і _ називається циклічним. Циклічний маршрут називається циклом, якщо він є ланцюг, і простим циклом - якщо це простий ланцюг.
Наприклад, маршрут для графа, зображеного на рис. 6.17, є простим циклом; а маршрут є циклом, але не буде простим, тому що містить вершини, які повторюються.
Визначення. Вершини і графа називаються зв'язаними, якщо існує маршрут з початком у і кінцем у . Маршрут між зв'язаними вершинами може бути поданий простим ланцюгом.
Визначення. Граф називається зв'язним, якщо будь-які пари його вершин зв'язані між собою.
Приклад. Граф, зображений на рис. 5.9,а - не зв'язний, а граф на рис. 5.9,б - зв'язний.
Рисунок 5.9 - Приклад незв'язного і зв'язного графів
Теорема. Якщо існує маршрут з вершини в графа , то існує простий ланцюг, що з'єднує вершини і .
Наслідок. Граф є зв'язним тоді і тільки тоді, коли між будь-якими двома його вершинами існує простий ланцюг.
Визначення. Максимальний непустий зв'язний підграф графа називається компонентом графа .
Отже, кожен граф являє собою об'єднання своїх компонент, які попарно не перетинаються.
Незв'язний граф має, як мінімум, два компоненти. Наприклад, граф, зображений на рис. 5.9,а, має два компоненти: і .
Визначення. Вершина називається точкою зчленування, якщо видалення її із графа приводить до збільшення числа компонент зв'язності.
Визначення. Ребро називається міст, якщо видалення його із графа приводить до збільшення числа компонент зв'язності.
Визначення. Множина ребер зв'язного графа називається множиною розрізу, якщо видалення ребер із множини порушує зв'язність графа, а видалення власної підмножини множини залишає граф зв'язним. Якщо множина складається з одного ребра, то це ребро називається ребром розрізу.
Приклад. Визначити ребра розрізу графа, зображеного на наступному рисунку.
Розв'язання: ребра , і _ є ребрами розрізу. Їх видалення порушує зв'язність графа.
Приклад. Визначити множини розрізу для графа, зображеного на наступному рисунку.
Розв'язання: Множинами розрізу для даного графа можуть бути, наприклад:
, , , , і т.д.
5.3.2 G _ орієнтований граф
Визначення. Послідовність ребер, у якому кінець кожного попереднього ребра збігається з початком наступного , називається шляхом або орієнтованим маршрутом. У шляху те саме ребро може зустрічатися кілька разів.
Визначення. Початком шляху є вершина ребра , а кінцем шляху є вершина ребра .
Визначення. Довжиною орієнтованого маршруту називається кількість орієнтованих ребер, що входять у цей шлях.
Приклад. Для графа, зображеного на рис. 5.10, приведемо приклади орієнтованих маршрутів з вершини до вершини : ; ; _ довжини 3; _ довжини 5.
Рисунок 5.10 - Приклади орієнтованих маршрутів
Визначення. Орієнтованим ланцюгом називається шлях, кожне ребро якого зустрічається не більше одного разу, і простим ланцюгом, якщо будь-яка вершина орграфа інцидентна не більш ніж двом його ребрам.
Визначення. Контуром називається шлях, початок і кінець якого збігаються. Контур називається циклом, якщо він є ланцюгом, і простим циклом - якщо це простий ланцюг.
Приклад. Для графа, зображеного на рис. 5.11,а, приклади: орієнтованого ланцюга _ ; контуру _ ; циклу _ . Для графа, зображеного на рис. 5.11,б, приклади: простого орієнтованого ланцюга _ ; простого циклу _ . При цьому зауважимо, що при записі циклу як для орієнтованого, так і для неорієнтованого графа, як початком, так і кінцем може бути обрана будь-яка вершина. Наприклад: ; і т.п.
Рисунок 5.11 - Приклади ланцюгів і циклів
Визначення. Для кожного орієнтованого графа може бути побудований неорієнтований граф , такий, що всі вершини цих графів збігаються, а кожне ребро (крім петель), стане неорієнтованим ребром графа . У такому випадку граф називається співвіднесеним графом орієнтованого графа .
Приклад. Для графа , зображеного на рис. 5.12,а, співвіднесений граф буде мати вигляд (рис. 5.12,б):
Рисунок 5.12 - Приклад співвіднесеного графа
Визначення. Вершина називається досяжною з вершини , якщо існує шлях з початком у і кінцем у .
Визначення. Орієнтований граф називається зв'язним, якщо його співвіднесений граф є зв'язним. Орієнтований граф називається сильно зв'язним, якщо для будь-якої пари вершин існує орієнтований шлях з , у .
Так, наприклад, граф, зображений на рис. 5.12,а, є зв'язним, але не є сильно зв'язним.
5.4 Метрика на графах
Визначення. Відстанню між вершинами і графа називається мінімальна довжина простого ланцюга з початком у вершині і кінцем у вершині . Якщо вершини і не з'єднані ланцюгом, тобто належать різним компонентам, то покладається, що .
У зв'язному графі відстань між вершинами задовольняє наступним умовам:
1) , і тоді і тільки тоді, коли ;
2) , ;
3) , .
Функція , що задовольняє трьом перерахованим умовам, називається метрикою графа.
Визначення. Центром графа називається вершина, від якої максимальна з відстаней до інших вершин була б мінімальною.
Визначення. Периферійною точкою графа називається вершина, від якої максимальна з відстаней до інших вершин була б максимальна.
Визначення. Максимальна відстань від центра графа до його вершин називається радіусом графа .
Визначення. Найпростіший ланцюг найкоротшої довжини називається геодезичним.
Визначення. Відхиленням вершини називається найбільша довжина геодезичної, яка з неї виходить.
У зв'язку із цим можна дати ще одне визначення радіуса графа:
Визначення. Відхилення центра називається радіусом графа , а відхилення периферійної точки - діаметром графа .
Алгоритм знаходження відстаней від даної вершини до інших вершин графа :
1) позначаємо через ;
2) позначаємо індексом всі вершини, суміжні з вершиною , виписуємо множину всіх цих вершин з їхніми позначками;
3) кожну вершину, що не належить множині і суміжну з кожною з вершин, що належать множині , позначаємо індексом ; виписуємо множину всіх цих вершин з їхніми позначками …;
) повторюємо описану процедуру доти, поки множина непомічених вершин не виявиться порожньою.
Приклад. Визначити відстань від вершини 7 (для зручності запису позначимо вершини графа арабськими цифрами) до всіх вершин графа , зображеного на наступному рисунку.
Розв'язання. Згідно алгоритму відстань від вершини 7 будемо шукати в такий спосіб:
1) ; 2) ; 3) .
Більше непомічених вершин немає. Тобто відстані від вершини 7 до кожної з вершин графа такі:
; .
Для визначення центра і радіуса графа необхідно побудувати для нього матрицю відстаней , кожен елемент якої описує відстань між вершинами і графа , тобто . Очевидно, що матриця відстаней симетрична щодо головної діагоналі (елементи якої дорівнюють нулю, тому що ).
Приклад. Визначити центр, периферійні вершини, радіус і діаметр графа , зображеного на на наступному рисунку.
Розв'язання.
Матриця відстаней графа має вигляд.
Знайдемо максимальну відстань від кожної з вершин графа як :
; ; ; ; ; ; ; ; .
Отже, згідно з визначенням 6.36, центром графа є вершина 4; периферійні вершини - 1, 6, 7, 8, 9. Радіус графа , а діаметр графа .
5.5 Ейлерів цикл. Ейлерів граф
Теорія графів бере свій початок з рішення видатним математиком Ейлером у 1736 р. задачі про кенігсбергські мости. Вона виникла в пруськом містечку Кенігсберг на річці Прегал. Жителі Кенігсберга полюбляли гуляти по доріжках, які включають сім мостів через річку. Людей цікавило питання, чи можуть вони, почавши шлях з однієї ділянки суши, обійти всі мости по черзі за одну ходу, і повернутися в початок шляху, не перепливаючи річку. План розташування семи мостів у Кенігсберзі наведений на рис. 5.13.
Рисунок 5.13 - План розташування семи мостів у Кенігсберзі
Ейлер замінив план міста графом (рис. 5.14), у якому ділянки суші зобразив як вершини, а мости, їх з'єднуючі - як ребра.
Рисунок 5.14 - Заміна плана міста графом
Для того, щоб відповістити на поставлене запитання, дамо ряд визначень.
Визначення. Ейлеровим циклом називається цикл, що містить всі ребра графа.
Ейлерів цикл можна вважати як слід олівця, що вичерчує граф, не відриваючись від паперу.
Відшукання ейлерових циклів пов'язане з рядом прикладних задач. Наприклад, при перевірці дорожньої мережі необхідно по кожній дорозі досліджуваної мережі проїхати тільки один раз і повернутися у вихідний пункт. Очевидно, що такі цикли існують не на будь-якому графі.
Визначення. Ейлеровим графом називається граф, що містить ейлеров цикл.
Теорема Ейлера. Кінцевий неорієнтований граф ейлеров тоді і тільки тоді, коли він зв'язний, і степінь всіх його вершин парна (при підрахунку степеня вершини, будь-яку інцидентну їй петлю вважати двічі).
Доведення:
Необхідність. Якщо граф містить ейлеров цикл , то будь-які дві його вершини належать цьому циклу; граф зв'язний. Якщо при обході циклу деяка вершина зустрічається разів, то ми разів входимо і виходимо з неї (щораз по різних ребрах). Отже, степінь вершини дорівнює .
Достатність. Нехай граф зв'язний і степінь будь-якої його вершини парна (рис. 5.15). Нехай _ деяка вершина графа, _ суміжна їй вершина. Цій вершині інцидентно хоча б одне ребро , відмінне від , вершині _ ребро, відмінне від , і т.д.
Рисунок 5.15 - Ейлерів граф
Побудуємо із цих ребер ланцюг, відзначаючи їх і не повторюючи вже пройдені.
Граф кінцевий, то цей ланцюг повинен закінчитися в деякій вершині . Число ребер, інцидентных вершині парне. Якби була відмінною від , ланцюг необхідно було би продовжити. Отже, .
Ми побудували цикл . Якщо в графі залишилися невідмічені ребра, то оскільки зв'язний, серед них найдеться хоча б одне, інцидентне якій-небудь вершині на циклі . Починаючи з вершини , ми можемо побудувати, як і раніше, цикл із ребер, що не ввійшли в . З і можна скласти новий цикл, що проходить із у по , потім уздовж усього циклу , і по частині циклу , що залишилася від до . Оскільки граф кінцевий, то після кінцевого числа кроків, ми одержимо ейлеров цикл.
Отже, ми готові відповістити на запитання жителів Кенігсберга. Для цього підрахуємо степіні вершин графа, побудованого Ейлером (рис. 6.33): ; ; ; . Цей граф має непарні степені вершин. Отже, цей граф не має ейлерова цикла. Тобто, неможливо пройти кожен міст по черзі за одну ходу і повернутися у вихідну точку шляху.
Приклад. Чи мають графи, зображені на рис.5.16 (а, б), ейлерів цикл?
Рисунок 5.16 - Приклад графів
Розв'язання:
Щоб відповістити на поставлене запитання, порахуємо степені вершин графа: а) ; ; ; ; .
Степені всіх вершин графа, зображеного на рис. 6.35,а, парні, отже, граф, має ейлеров цикл;
б) ; ; ; ; ; .
Степені вершин і графа, зображеного на рис. 6.35,б, непарні, отже, граф не має ейлеров цикл.
Що стосується кенігсбергських мостів, можна задати інше питання: " чи можливо пройти кожен міст по одному разі і не обов'язково повертатися у вихідну точку маршруту?" Відповідь на це питання жадає від нас знання наступного визначення і теореми.
Визначення. Шлях, що включає кожне ребро графа тільки один раз, називається ейлеровим шляхом. У тому випадку, якщо ейлеров шлях не є ейлеровим циклом, він називається власним ейлеровим шляхом.
Теорема (про ейлерів шлях). Граф має власний ейлерів шлях тоді і тільки тоді, коли він зв'язний і рівно дві його вершини мають непарний степінь.
Так як граф для задачі про кенігсбергські мости має чотири вершини з непарними степенями, то можна зробити висновок про те, що даний граф не має власного ейлерова шляху, а отже, неможливо пройти кожен міст по одному разі, навіть якщо не потрібно повертатися у вихідну точку маршруту.
5.6 Шляхи і цикли Гамільтона
В 1857 році математик Вільям Роуен Гамільтон придумав іграшку-головоломку. Ця іграшка являла собою додекаедр - правильний багатогранник, 12 граней якого ? це правильні п'ятикутники. У кожному з 20 кутів просвердлувалась дірка, у яку вставляли кілочок, що зображував місто. За допомогою мотузки було потрібно знайти шлях через міста, відвідав кожне місто один раз, і повернутися у вихідне місто. Додекаедр на площині зображується так, як показано на рис. 5.17.
Рисунок 5.17 - Зображення додекаедра на площині
Задача головоломки зводиться до знаходження циклу в графі, що проходить через кожну вершину, крім початкової, тільки один раз.
Визначення. Шляхом Гамільтона (або гамільтоновим ланцюгом) називається простий ланцюг, що проходить через всі вершини графа, з початком і кінцем у різних вершинах .
Визначення. Цикл Гамільтона _ це простий цикл, що проходить через всі вершини графа .
Гамільтонів цикл у деякому змісті протилежний ейлерову циклу, що проходить через всі ребра один раз, хоча до певного моменту обидва цикли можуть здаватися схожими. Цикл Гамільтона виявляється набагато складніше, і для його знаходження поки немає ефективних алгоритмів, що вимагають істотно меншого часу, чим пряме перебирання варіантів. Проте приведемо ряд теорем без доведення, що дозволяють нам судити про можливість відшукати гамільтонів цикл у досліджуваному графі. А для початку покажемо один з варіантів рішення головоломки, запропонованої Гамільтоном (рис. 5.18).
Рисунок 5.18 - Варіант розв'язання головоломки Гамільтона
Теорема. Для будь-якої вершини із циклу Гамільтона існує рівно два ребра із цього циклу, інцидентні даній вершині.
Визначення. Граф, що має цикл Гамільтона, називається гамільтонів.
Виходячи з наведеного визначення, як наслідок теореми 6.5, робимо висновок про те, що будь-який граф, що має вершину степені 1, не є гамільтонів. Помітимо також, що для того, щоб граф мав цикл Гамільтона, необхідно, щоб він був зв'язним.
Приклад. Граф Петерсона, зображений на рис. 5.19,а, має шлях Гамільтона (рис. 5.19,б), але не має цикл Гамільтона.
Рисунок 5.19 - Граф Петерсона
Теорема. Якщо граф має ребро розрізу, то він не може мати цикл Гамільтона. Якщо компоненти графа, отримані шляхом видалення ребра розрізу, мають цикл Гамільтона, то граф має шлях Гамільтона.
Теорема. Якщо _ зв'язний граф з вершинами і для кожної пари несуміжних вершин , сума степенів вершин задовольняє умові , тоді граф має цикл Гамільтона.
Наслідок. Якщо _ зв'язний граф з вершинами і для кожної вершини виконується умова , то граф має цикл Гамільтона.
Приклад. Знайдіть цикл Гамільтона, якщо він існує, для графа , зображеного на рис. 5.20,а.
Рисунок 5.20 - Знаходження циклу Гамільтона
Розв'язання: Граф _ зв'язний, кількість вершин графа - . Степінь кожної з вершин дорівнює 3, тобто кожна з вершин графа задовольняє умові . Отже, даний граф є гамільтонів, тобто існує цикл Гамільтона. Знайти його можемо тільки методом перебирання. Результати прямого перебирання - цикл (рис. 6.41,б).
Практичне застосування циклів Гамільтона знаходимо в рішенні класичної задачі комівояжера, яка цікава для людей, у чиє коло обов'язків входить знаходження оптимальних шляхів, наприклад, об'їзду філій фірми, транспортування вантажів, доставки товарів і інше.
Задача комівояжера. Комівояжер повинен відвідати кілька міст і повернутися у вихідний пункт. Відстані між містами відомі. Потрібно знайти дорогу найкоротшої довжини. При такій постановці задачі схема доріг являє собою граф, у якій будь-якому ребру запропонована певна довжина . Задача комівояжера зводиться до знаходження в отриманому графі із заданими довжинами ребер циклу Гамільтона мінімальної довжини.
Існує ряд алгоритмів, досить громіздких, що дозволяють знаходити найкоротший шлях від вершини до вершини , таких як алгоритми Дейкстри, Флойда-Уоршолла і т.п. Але ефективних алгоритмів, для пошуку циклу Гамільтона мінімальної довжини немає. Через їхню відсутність, щораз цю практичну задачу доводиться вирішувати методом прямого перебирання.
5.7 Планарні графи
Визначення. Граф називається правильно укладеним на площині, якщо його графічне подання таке, що ребра графа перетинаються тільки в його вершинах.
Визначення. Граф називається плоским (планарним), якщо він ізоморфний деякому графу, правильно укладеному на площині. Тобто плоский граф - це граф, який можна правильно укласти на площині.
Приклад. Графи і , подані на наступному рисунку, ізоморфні. Граф _ правильно укладений на площині. Отже, дані графи - плоскі.
Розглянемо граф як малюнок на аркуші паперу. Якщо граф планарний, тобто намальований так, що його ребра не перетинаються, і його необхідно розрізати уздовж ребер, то граф виявиться розділеним на частини, включаючи зовнішню частину. Такі частини називаються гранями. Границя кожної грані є циклом.
Визначення. Гранню планарного графа називається така максимальна ділянка площини, що будь-які дві її точки можуть бути з'єднані кривою, що не перетинає ребро графа.
Задача про можливості правильного укладання графа на площині є актуальною у зв'язку з використанням у радіотехніці друкованих схем. Інтегральні мікросхеми складаються із шарів мініатюрних мікросхем, удрукованих у пластину. Ці схеми наносяться на ізолятор у друкований спосіб і перетинання яких-небудь двох провідників, у непередбачуваних точках (не у вершинах графа), привело б до їх замикання. Тобто для друкування електричних схем просто необхідно, щоб графи (що їх зображують) були плоскими.
Задачі, пов'язані із плоскими графами, актуальні не тільки в радіотехніці. Приведемо класичну задачу про три міста і три джерела постачання. Нехай є три міста , і і три джерела життєзабезпечення: водонапірна башта , електростанція і станція магістрального газопроводу . Чи можна з'єднати ці міста із джерелами постачання водою, газом і електрикою так, щоб траншеї, прориті для цих ліній (на одній глибині) не перетиналися?
Ця задача зводиться до побудови плоского графа, ізоморфного графу, зображеному на рис. 5.21.
Рисунок 5.21 - Заданий граф
Відповідь на питання поставлене у сформульованій задачі негативна. Завжди можна намалювати 8 попарно неперетинаючихся ліній, а дев'ята обов'язково перетне одну із цих восьми.
Доведення неможливості такої побудови спирається на теорему, доведену Жорданом. Проілюструємо її в такий спосіб. Нехай _ безперервна замкнута лінія без самоперетинань (рис. 5.22). Ця лінія ділить площину на дві частини: зовнішню і внутрішню. Будь-які дві точки і із внутрішньої і зовнішньої частин відповідно можна з'єднати тільки лінією, що перетинає .
Рисунок 5.22 - Безперервна замкнута лінія
Позначимо граф, зображений на рис. 5.21 як . Замінимо граф йому ізоморфним (рис. 5.23).
Рисунок 5.23 - Ізоморфний граф
З'єднати вершини і без перетинання вже проведених ребер неможливо, тому що точка лежить усередині області, обмеженої кривою , а точка _ поза зазначеної області. Отже, граф не є планарним.
Аналогічно доводиться непланарність повного графа (рис. 5.24).
Рисунок 5.24 - Повний граф
Використовуючи графи і , можна сформулювати наступний критерій планарності графів.
Теорема. (Теорема Куратовського). Граф є планарним тоді і тільки тоді, коли він не містить підграф, ізоморфний графу або .
Існують і інші критерії планарності графів.
Теорема. Якщо _ зв'язний планарний граф, що містить вершин, ребер і граней, то повинна виконуватися умова .
За допомогою теореми 6.8 задача про життєзабезпечення трьох будинків (рис. 6.44) вирішується в такий спосіб. У графа шість вершин і дев'ять ребер: , , а кількість граней _ . Підставимо в умову . Умова теореми 6.8 не виконується. Отже, граф _ не планарний.
Лема. У довільному планарному графі з кількістю вершин не менше трьох має місце нерівність .
За допомогою леми 6.1 доведемо, що граф не планарний. Граф має п'ять вершин і десять ребер: , . Скористаємося умовою . Як бачимо, умова для графа не виконана, отже, граф не планарний.
5.8 Розфарбування графів
Нехай G =(V,E ) довільний граф, а Nk={1,2,...,k }.
Будь-яке відображення f :V Nk, яке ставить у відповідність кожній вершині v V деяке натуральне число f (v) Nk, називається розфарбуванням графа G. Число f (v) називається кольором або номером фарби вершини v.
Розфарбування f графа G називається правильним, якщо для будь-яких його суміжних вершин v і w виконується f (v) f (w).
Мінімальне число k, для якого існує правильне розфарбування графа G, називається хроматичним числом графа G і позначається Xp(G ).
Мінімальним правильним розфарбуванням графа G називається правильне розфарбування для k= Xp (G ).
Для певних типів графів визначити хроматичні числа нескладно. Наприклад, 1-хроматичними є порожні графи G =(V,) і тільки вони. Хроматичне число повного графа Kn дорівнює n, а хроматичне число довільного двочасткового графа 2. 2-хроматичні графи часто називають біхроматичними.
Очевидними є такі твердження.
Лема. Якщо кожна зв'язна компонента графа G потребує для свого правильного розфарбування не більше k фарб, то (G )k.
Лема. Граф є біхроматичний тоді і тільки тоді, коли він двочастковий.
Зокрема, всі дерева і прості цикли парної довжини C2k є біхроматичні. У той же час, (C2k+1)=3.
Використовуючи теорему Кеніга, останню лему можна переформулювати у такому вигляді.
Лема. Граф є біхроматичний тоді і тільки тоді, коли він не має циклів непарної довжини.
Проблема визначення, чи є заданий граф k-хроматичним для певного k, та проблема знаходження мінімального правильного розфарбування для заданого графа належать до класу задач, для яких на сьогодні не існують (і є всі підстави вважати, що не існують взагалі) ефективні точні алгоритми їх розв'язку. Тому важливими є результати, які дозволяють оцінити значення хроматичного числа (G ), виходячи з певних характеристик та властивостей графа G.
Теорема. Позначимо через (G ) найбільший зі степенів вершин графа G, тоді (G ) (G )+1.
Доведення проведемо індукцією за кількістю n вершин графа G. Для тривіального графа (n=1) і графів з двома вершинами нерівність виконується.
Нехай твердження теореми виконується для всіх графів з кількістю вершин t (t 2). Розглянемо довільний граф G з t +1 вершиною. Вилучимо з G деяку вершину v, дістанемо граф G , всі степені вершин якого не перевищують (G ). Отже, за припущенням індукції, для правильного розфарбування G потрібно не більше ніж (G )+1 фарба. Правильне розфарбування для G дістанемо з правильного розфарбування графа G , якщо пофарбуємо вершину v у колір, відмінний від кольорів усіх суміжних із v вершин. Оскільки таких вершин не більше, ніж (G ), то для правильного розфарбування графа G достатньо (G )+1 фарба.
Наслідок. Для правильного розфарбування довільного кубічного графа достатньо чотири фарби.
Так склалося історично, що окреме місце в теорії графів займають дослідження з розфарбування планарних графів. Пов'язано це зі славетною проблемою або гіпотезою чотирьох фарб.
Грані плоскої карти назвемо суміжними, якщо їхні межі мають принаймні одне спільне ребро.
Гіпотеза чотирьох фарб виникла у зв'язку з розфарбуванням друкованих географічних карт (звідси й термін "плоска карта") і формулювалась так:
"Грані довільної плоскої карти можна розфарбувати не більше ніж чотирма фарбами так, що будь-які суміжні грані матимуть різні кольори".
Згодом з'явилось інше, рівносильне, формулювання гіпотези чотирьох фарб.
Для правильного розфарбування вершин довільного планарного графа потрібно не більше чотирьох фарб.
Ця гіпотеза виникла в середині ХIХ століття. Більше ста років професійні та непрофесійні дослідники намагалися довести або спростувати цю гіпотезу. В результаті багаторічних досліджень виявилось, що для вирішення проблеми чотирьох фарб необхідно перевірити її справедливість для скінченного числа графів певного виду. Кількість варіантів, які потрібно було перебрати, була настільки великою, що тільки за допомогою потужної ЕОМ, яка неперервно працювала протягом більше двох місяців, у 1976 році справедливість гіпотези чотирьох фарб була підтверджена. Однак такий "фізичний" експериментальний спосіб доведення не зовсім влаштовує багатьох професійних математиків, і вони продовжують пошуки аналітичного доведення гіпотези.
Зауважимо, що існують планарні графи, хроматичне число яких дорівнює 4. Найпростішим таким графом є K4. Отже, гіпотезу чотирьох фарб не можна "вдосконалити", перетворивши у "гіпотезу трьох фарб".
5.9 Дерева і ліс
Визначення. Неорієнтованим деревом (або просто деревом) називається неорієнтований зв'язний граф без циклів, отже без петель і кратних ребер, що має не менш двох вершин.
Дерево є мінімальним зв'язним графом у тому розумінні, що видалення хоча б одного ребра приводить до того, що граф виявляється незв'язним.
Приклад. Чи є графи, зображені на рис. 5.25, (а), (б) деревами?
Рисунок 5.25 - Графи
Розв'язання:
Граф на рис. 5.25(а) є деревом, тому що він зв'язний і не містить циклів. Граф на рис. 5.25(б) не є деревом, тому що містить цикл .
Дамо без доведення ряд теорем, корисних для вивчення дерев.
Теорема. Будь-яке дерево з вершинами містить ребро.
Теорема. Нехай _ граф, що містить більше однієї вершини. Видаляючи його ребра можна одержати дерево тоді і тільки тоді, коли він зв'язний.
Визначення. Лісом називається незв'язний неорієнтований граф без циклів. Зв'язані компоненти лісу є деревами.
Приклад. На рис. 5.26 наведений приклад лісу, що містить три дерева.
Рисунок 5.26 - Приклад лісу, що містить три дерева
Добре зрозумілим прикладом дерева є: будь-яке генеалогічне дерево; організаційна структура будь-якого підприємства, організації.
Визначення. Орієнтованим деревом називається вільний від петель орієнтований граф, співвіднесений граф якого є деревом; тому якщо існує шлях від вершини до вершини , то він єдиний.
Помітимо, що якщо в орієнтованому дереві є ребро , то немає ребра , інакше шлях був би циклом.
Приклад. На рис. 5.27 наведено приклад орієнтованого дерева:
Рисунок 5.27 - Приклад орієнтованого дерева
Визначення. Вершини дерева степіня 1 називаються листя, інші вершини - внутрішніми вершинами.
Наприклад, у дерева, зображеного на рис. 6.49(а), листя це вершини . Інші вершини є внутрішніми.
Дерева визначаються такою властивістю: для будь-яких двох вершин дерева шлях з вершини до вершини єдиний. І, навпаки, якщо для будь-яких двох вершин графа існує єдиний шлях з вершини до вершини , тоді граф _ дерево.
Припустимо, що дерево являє собою якийсь фізичний об'єкт, рухливий у вершинах. Його можна підвісити за кожну з вершин. Так, наприклад, якщо дерево, зображене на рис. 5.28(а) підвісити за вершину , або , то воно буде виглядати, як показано на рис. 5.28(а) або на рис. 5.28 (б).
Рисунок 5.28 - Приклад дерева
Обрана нами вершина називається коренем дерева і розташовується в самій верхній його частині. Для дерева на рис. 5.28(а) коренем є вершина , а для дерева на рис. 5.28(б) - вершина .
Визначення. Дерево, корінь якого визначений, називається кореневим деревом.
Аналогічно визначається і орієнтоване кореневе дерево. При цьому варто пам'ятати, що всі його ребра орієнтуються від кореня.
При заміні кореневого неорієнтованого дерева на кореневе орієнтоване дерево , говорять, що є породженим кореневим деревом .
Приклад. На рис. 5.29(а) зображене неорієнтоване кореневе дерево, а на рис. 5.29(б) - породжене їм орієнтоване кореневе дерево.
Рисунок 5.29 - Неорієнтоване і породжене ним орієнтоване дерево
Якщо корінь дерева обраний, то можна ввести ще ряд визначень.
Визначення. Рівнем вершини називається довжина єдиного шляху від кореня дерева до вершини .
Визначення. Висотою дерева називається довжина самого довгого шляху від кореня дерева до листя.
Приклад. Для кореневого дерева, зображеного на наступному рисунку, визначити рівень вершини , висоту дерева.
Розв'язання: Рівень вершини дорівнює двом; а висота дерева з коренем у вершині дорівнює максимальному шляху від кореня до вершини _ _дорівнює п'яти.
Для генеалогічних дерев дамо ряд визначень. Їх можна розповсюдити на будь-які орієнтовані кореневі дерева.
Визначення. Якщо існує орієнтоване ребро з в , то вершина називається батьком вершини , а вершина _ сином (дочкою) вершини .
Визначення. Якщо є одночасно батьком і , то і називаються братами (сестрами).
Визначення. Якщо існує орієнтований шлях з вершини у вершину , то вершина називається предком вершини , а вершина _ нащадком вершини .
Приклад. Визначити батьків і синів, братів, предків і нащадків кореневого орієнтованого дерева, зображеного на на наступному рисунку.
Розв'язання: є батьком і ; _ батьком і ; _ батьком , і ; _ батьком і ; _ батьком ; _ батьком і . І навпаки: і _ сини ; і _ сини ; , і _ сини ; і _ сини ; _ син ; і _ сини .
Груп нащадків і предків можна виділити дуже багато, приведемо лише деякі приклади: _ нащадки , отже, _ предок для ; є нащадком , отже, _ предок .
5.10 Алгоритми пошуку найкоротших шляхів
Розглянемо орієнтований граф G=(V,E), дугам якого приписані ваги. Це означає, що кожній дузі (u,v) поставлено у відповідність деяке дійсне число a(u,v), яке називається вагою даної дуги. Вважаємо a(u,v)=?, якщо дуга (u,v) не існує.
Під довжиною шляху будемо розуміти суму ваг дуг, з яких складається шлях. Довжину найкоротшого шляху будемо позначати d(s,t) і називати відстанню від s до t. Якщо не існує жодного шляху з s в t, то вважаємо d(s,t)=?.
Введемо ще одне обмеження. Нехай ваги дуг будуть тільки додатними значеннями. Тому що при існуванні дуг з від'ємними вагами довжина найкоротшого шляху між парою вершин стає невизначеною, виходячи з можливості кількаразового включення таких дуг у шлях.
Якщо відома відстань між парою вершин, можна легко визначити найкоротший шлях. Тому що для двох довільних вершин s і t (s?t) існує така вершина v, що d(s,t)=d(s,v)+d(v,t). Цією властивістю володіє і передостання вершина в найкоротшому шляху від s до t. Отже, визначаючи в такий спосіб передостанню вершину, можна пройти від кінця найкоротшого шляху до його початку.
Більшість відомих алгоритмів знаходження відстані між двома вершинами s і t можна описати наступною послідовністю дій:
1) При заданій матриці ваг дуг A[u,v], обчислюємо деякі верхні обмеження D[v] на відстані від s до всіх вершин v.
2) Щораз, коли з'ясовується, що D[u]+A[u,v]<D[v], поліпшуємо оцінку D[v]=D[u]+A[u,v].
3) Процес закінчується, коли подальше поліпшення жодного з обмежень неможливо. Значення кожної D[u] дорівнює відстані d(s,u). Вершину s у цьому випадку називають джерелом.
5.10.1 Алгоритм пошуку у глибину
Робота всякого алгоритму обходу складається в послідовному відвідуванні вершин і дослідженні ребер. Які саме дії виконуються при відвідуванні вершини і дослідженні ребра - залежить від конкретної задачі, для розв'язування якої виконується обхід. У кожному разі факт відвідування вершини запам'ятовується, так що з моменту відвідування і до кінця роботи алгоритму вона вважається відвідуваною. Вершину, що ще не відвідана, називають новою. У результаті відвідування вершина стає відкритою і залишається такою, поки не будуть досліджені всі інцидентні їй ребра. Після цього вона перетворюється в закриту.
Існує багато алгоритмів на графах, в основі яких лежить систематичний перебір вершин, такий, що кожна вершина проглядається в точності один раз. Тому важливою задачею є знаходження гарних методів пошуку в графі. Метод пошуку гарний, якщо він дозволяє алгоритму розв'язання задачі, що цікавить нас, легко використовувати цей метод, і кожне ребро графа аналізується не більше одного разу (або кількість таких досліджень обмежена зверху).
Пошук у глибину - це найбільш важлива завдяки численності додатків стратегія обходу графа. Ідея цього методу - шлях вперед у недосліджену область, поки це можливо, якщо ж навколо все досліджено, відступити на крок назад і шукати нові можливості для просування вперед. Метод пошуку в глибину відомий під різними назвами: "бектрекінг", "пошук з поверненням".
Обхід починається з відвідування заданої стартової вершини a, що стає активною і єдиною відкритою вершиною. Потім вибирається інцидентне вершині a ребро (a, y) і відвідується вершина y. Вона стає відкритою і активною. Надалі, як і при пошуку завширшки, кожний черговий крок починається з вибору активної вершини з множини відкритих вершин. Якщо всі ребра, які інцидентні активній вершині x, уже досліджені, вона перетворюється в закриту. У протилежному випадку вибирається одне з недосліджених ребер (x, y), це ребро досліджується. Якщо вершина y нова, то вона відвідується і перетворюється у відкриту.
При пошуку в глибину в якості активної вибирається та з відкритих вершин, що була відвідана останньою. Для реалізації такого правила вибору найбільш зручною структурою зберігання множини відкритих вершин є стек: вершини, які відкриваються, складаються в стек у тім порядку, у якому вони відкриваються, а в якості активної вибирається остання вершина.
5.10.2 Алгоритм пошуку завширшки
Пошук завширшки - це класичний метод розв'язування задачі знаходження найкоротшого шляху між двома конкретними вершинами графа. Найкоротший шлях - це такий шлях, що з'єднує вершини графа та володіє тією властивістю, що ніякий інший шлях, що з'єднує ці вершини, не містить менше число ребер. Пошук у глибину мало придатний для розв'язування цієї задачі, оскільки пропонований їм порядок проходження графа не має відношення до пошуку найкоротших шляхів, а пошук завширшки призначений саме для досягнення цієї мети.
Розглянемо метод пошуку завширшки. В розглянутому методі пошуку в глибину чим пізніше буде відвідана вершина, тим раніше вона буде використана - точніше, так буде при допущенні, що друга вершина відвідується перед використанням першої. Це прямий наслідок того факту, що переглянуті, але ще не використані вершини накопичуються в стеці. Пошук завширшки, грубо говорячи, ґрунтується на заміні стека чергою.
Ідея пошуку завширшки полягає в тому, щоб відвідувати вершини в порядку їхньої далекості від деякої заздалегідь обраної або зазначеної стартової вершини a. Інакше кажучи, спочатку відвідується сама вершина a, потім всі вершини, суміжні з a, тобто які знаходяться від неї на відстані 1, потім вершини, що перебувають від a на відстані 2, і далі по далекості.
Розглянемо алгоритм пошуку завширшки із заданою стартовою вершиною a. Спочатку всі вершини позначаються як нові. Першою відвідується вершина a, вона стає єдиною відкритою вершиною. Надалі кожний черговий крок починається з вибору деякої відкритої вершини x. Ця вершина стає активною. Далі досліджуються ребра, інцидентні активній вершині. Якщо таке ребро з'єднує вершину x з новою вершиною y, то вершина y відвідується і перетворюється у відкриту. Коли всі ребра, інцидентні активній вершині, досліджені, вона перестає бути активною і стає закритою. Після цього вибирається нова активна вершина, і описані дії повторюються. Процес закінчується, коли множина відкритих вершин стає порожньою.
Основна особливість пошуку завширшки, що відрізняє його від інших способів обходу графів, полягає в тому, що в якості активної вершини вибирається та з відкритих, яка була відвідана раніше інших. Саме цим забезпечується головна властивість пошуку завширшки: чим ближче вершина до старту, тим раніше вона буде відвідана. Для реалізації такого правила вибору активної вершини зручно використати для зберігання множини відкритих вершин чергу - коли нова вершина стає відкритою, вона додається в кінець черги, а активна вибирається в її початку.
Обидва методи пошуку в графі - у глибину і завширшки можуть бути використані для знаходження шляху між фіксованими вершинами a і b. Досить почати пошук у графі з вершини a і вести його до моменту відвідування вершини b.
Перевагою пошуку в глибину є той факт, що в момент відвідування вершини b стік містить послідовність вершин, що визначає шлях з a в b. Це стає очевидним, якщо відзначити, що кожна вершина, що попадає в стек, є суміжною з попередньою.
Однак недоліком пошуку в глибину є те, що отриманий у такий спосіб шлях у загальному випадку не буде найкоротшим шляхом з a в b. Від цього недоліку вільний метод знаходження шляху, заснований на пошуку завширшки.
5.10.3 Алгоритм Дейкстри
Найбільш ефективний алгоритм пошуку найкоротших шляхів на графах дав Дейкстра. Эдсгер Вібе Дейкстра (нідерл. Edsger Wybe Dijkstra; народився 11травня 1930 року в Роттердамі (Нідерланди) - помер 6 серпня 2002 року) - видатний нідерландський вчений, ідеї якого зробили величезний вплив на розвиток комп'ютерної індустрії. Популярність Дейкстрі принесли його роботи в галузі застосування математичної логіки при розробці комп'ютерних програм. Він брав активну участь в розробці мов програмування. Один з авторів концепції структурного програмування і алгоритму знаходження найкоротшого шляху на орієнтованому графі з вагами ребер, відомий як Алгоритм Дейкстри. У 1972 році Дейкстра став лауреатом премії Тьюрінга.
Нехай G = (V, E) - зважений орієнтований граф, w(vi, vj) - вага дуги (vi,vj). Почавши з вершини a, знаходимо відстань від a до кожної із суміжних із нею вершин. Вибираємо вершину, відстань від якої до вершини a найменша; нехай це буде вершина v*. Далі знаходимо відстані від вершини a до кожної вершини суміжної з v* вздовж шляху, який проходить через вершину v*. Якщо для якоїсь із таких вершин ця відстань менша від поточної, то замінюємо нею поточну відстань. Знову вибираємо вершину, найближчу до a та не вибрану раніше; повторюємо процес.
Описаний процес зручно виконувати за допомогою присвоювання вершинам міток. Є мітки двох типів: тимчасові та постійні. Вершини з постійними мітками групуються у множину M, яку називають множиною позначених вершин. Решта вершин має тимчасові мітки, і множину таких вершин позначимо як T, T=V\M. Позначатимемо мітку (тимчасову чи постійну) вершини v як l(v). Значення постійної мітки l(v) дорівнює довжині найкоротшого шляху від вершини a до вершини v, тимчасової - довжині найкоротшого шляху, який проходить лише через вершини з постійними мітками.
Фіксованою початковою вершиною вважаємо вершину a; довжину найкоротшого шляху шукаємо до вершини z (або до всіх вершин графа). Розглянемо приклади.
Варіант 1. Дана мережа автомобільних доріг, що з'єднують міста України. Знайти найкоротші шляхи від Київа до кожного міста України (якщо рухатися можна тільки по дорогах).
Варіант 2. Надана кількість маршрутів пасажирського транспорту, для кожного маршруту відома його вартість. Знайти маршрут мінімальної вартості (можливо, з пересадками), наприклад, від Таїровського житлового масиву до Іллічівська.
У загальному випадку алгоритм Дейкстри заснований на присвоєнні вершинам тимчасових позначок, причому позначка вершини дає верхню межу довжини шляху від деякої вершини s до наданої вершини. Ці позначки поступово зменшуються за допомогою деякої ітераційної процедури, і на кожному кроці ітерації тільки одна з тимчасових позначок стає постійною. Останнє указує на те, що позначка вже не є верхньою межею, а дає точну довжину найкоротшого шляху від t до наданої вершини.
Розглянемо докладніше цей алгоритм. Надано граф G = (X, A, C) із зваженими дугами, приклад якого показано на рис.5.30 Позначимо L(хi) позначку вершини хi. Ваги відстаней наведено в таблиці.
Рисунок 5.30 - Граф із зваженими дугами
Таблиця - Ваги відстаней
|
x1 |
x2 |
x3 |
x4 |
||
|
x1 |
c1 |
c3 |
|||
|
x2 |
c2 |
||||
|
x3 |
c5 |
||||
|
x4 |
c4 |
Розглянемо алгоритм знаходження найкоротшого шляху від вершини s до вершини t графа і більш загальний випадок: від вершини s до всіх вершин графа.
Привоєння початкових позначок.
КРОК 1. Присвоїти L(s)=0 і вважати цю позначку постійною. Для всіх вершин хis покласти L(хi)=? і вважати ці позначки тимчасовими. За поточну дану вершину з постійною позначкою візьмемо вершину p, тобто покласти p=s.
Оновлення позначок
КРОК 2. Для вершин, що входять в пряме відображення вершини р, тобто для всіх хi, належних Г(p), позначки яких тимчасові, змінити позначки відповідно до наступного виразу:
L(xi) min[L(xi),L(p)+C(p,xi)] (5.1)
Перетворення позначки в постійну.
КРОК 3. Серед всіх вершин з тимчасовими позначками знайти таку, для якої L()=min[L(xi)].
КРОК 4. Рахувати позначку вершини постійною і покласти p=.
КРОК 5(а). (При знаходженні шляху від s до t) - якщо поточна вершина p є шуканою, тобто p = t, то L(p) є довжиною найкоротшого шляху від s до t. Якщо pt, перейти до КРОКУ 2.
КРОК 5(б). (При знаходженні шляхів від s до всіх вершин)
- якщо всі вершини відмічені постійними позначками, то ці позначки дають довжини найкоротших шляхів;
- якщо деякі позначками є тимчасовими, то слід перейти до КРОКУ 2.
Як тільки довжини найкоротших шляхів від вершини s будуть знайдені, шляхи можна одержати за допомогою рекурсивної процедури (*). Оскільки вершина безпосередньо передує вершині хi в найкоротшому шляху від s до хi, то для будь-якої вершини хi відповідну вершину можна знайти як одну з вершин, що залишилися, для якої
L()+c(,xi)=L(xi) (5.2)
Якщо найкоротший шлях від s до будь-якої вершини хi є єдиним, то дуги (, xi) цього найкоротшого шляху утворюють орієнтоване дерево з коренем s.
Якщо існує декілька найкоротших шляхів від s до якої-небудь іншої вершини, то при деякій фіксованій вершині співвідношення (*) виконуватиметься для більш ніж однієї вершини хi . В цьому випадку вибір може бути або довільним (якщо потрібен якийсь один найкоротший шлях між s і хi), або таким, що розглядаються всі дуги (, x2), що входять в який-небудь з найкоротших шляхів, і при цьому сукупність всіх таких дуг утворює не орієнтоване дерево, а загальний граф, званий базою щодо s.
Приклад. Розглянемо граф змішаного типу, зображений на рис. 5.31 (а), де кожне неорієнтоване ребро розглядається як пара протилежно направлених дуг рівної ваги.
Матриця вагів надана на рис. 5.31 (б). Потрібно знайти всі найкоротші шляхи від вершини х1 до всієї решти вершин.
КРОК 1. Привласнимо L(х1)=0, L(хi)=? для всіх хi, окрім х1 . Покладемо р=х1.
Перша ітерація.
КРОК 2. Знайдемо пряме відображення для поточної даної вершини:
Г(р)=Г(х1)={х2,х7,х8,х9}. Всі вершини, що входять в пряме відображення мають тимчасові позначки, тому перерахуємо їх значення:
L(x2)=min[L(x2),L(x1)+c(x1,x2)]=min[?,0+10]=10;
L(x7)=min[?,0+3]=3;
L(x8)=min[?,0+6]=6;
L(x9)=min[?,0+12]=12.
Рисунок 5.31 - Приклад пошуку найкоротшого шляху:
а) граф; б) матриця вагів дуг
КРОК 3. На даному кроці ітерації маємо наступні тимчасові позначки вершин:
L(х2)=10, L(х3)=?,
L(х7)=3, L(х4)=?,
L(х8)=6, L(х5)=?,
L(х9)=12, L(х6)=?.
Очевидно, що мінімальну позначку, яка дорівнює 3, має вершина х7.
КРОК 4. За наступну поточну позначку приймаємо вершину х7, тобто p=х7, а її позначка стає постійною, L(х7)=3+.
КРОК 5. Оскільки не всі вершини графу мають постійні позначки, переходимо до кроку 2.
Друга ітерація.
Граф з поточними значеннями позначок вершин надано на рис.5.32.
Рисунок 5.32 - Позначки в кінці першої ітерації
КРОК 2. Знаходимо Г(х7)={х2,х4,х6,х9}. Позначки всіх вершин тимчасові, отже перераховуємо їх значення:
L(х2)=min[10,3+2]=5,
L(х4)=min[?,3+4]=7,
L(х6)=min[?,3+14]=17,
L(х9)=min[12,3+24]=12.
КРОК 3. На даному кроці ітерації маємо наступні тимчасові позначки вершин:
L(х2)=5, L(х3)= ? ,
L(х4)=7, L(х5)= ? ,
L(х6)=17, L(х8)=6, L(х9)=12.
Очевидно, що мінімальну позначку, рівну 5, має вершина х2 .
КРОК 4. За наступну поточну позначку приймаємо вершину х2, тобто p=х2, а її позначка стає постійною, L(х2)=5+ .
КРОК 5. Оскільки не всі вершини графа мають постійні позначки, переходимо до кроку 2.
Третя ітерація.
Граф з поточними значеннями позначок вершин надано на рис. 5.33.
Рисунок 5.33 - Позначки в кінці другої ітерації
КРОК 2. Знаходимо Г(х2)={х1,х3,х7,х9}. Помітки вершин х3 і х9 тимчасові, отже перераховуємо їх значення:
L(х3)=min[?,5+18]=23,
L(х9)=min[12,5+13]=12.
КРОК 3. На даному кроці ітерації маємо наступні тимчасові помітки вершин:
L(х3)=23, L(х4)=7, L(х5)=? ,
L(х6)=17, L(х8)=6, L(х9)=12.
Очевидно, що мінімальну мітку, рівну 6, має вершина х8.
КРОК 4. За наступну поточну помітку приймаємо вершину х8, тобто p=х8, а її мітка стає постійною, L(х8) = 6+ .
КРОК 5. Не всі вершини графа мають постійні помітки, тому переходимо до кроку 2.
Четверта ітерація.
КРОК 2. Знаходимо Г(х8)={х1,х5,х6,х9}. Помітки вершин х5, х6 і х9 тимчасові, отже, перераховуємо їх значення:
L(х5)=min[?,6+23]=29,
L(х6)=min[17,6+15]=17,
L(х9)=min[12,6+5]=11.
КРОК 3. На даному кроці ітерації маємо наступні тимчасові позначки вершин:
L(х3)=23, L(х4)=7,
L(х5)=29, L(х6)=17, L(х9)=11.
Очевидно, що мінімальну позначку, рівну 7 має верші на х4 .
КРОК 4. За наступну поточну мітку приймаємо вершину х4, тобто p=х4, а її мітка стає постійною, L(х4) = 7+.
КРОК 5. Оскільки не всі вершини графа мають постійні позначки, переходимо до кроку 2.
П'ята ітерація.
КРОК 2. Знаходимо Г(х4)={х3,х5,х6,х7}. Позначки вершин х3, х5 і х6 тимчасові, отже, перераховуємо їх значення:
L(х3)=min[23,7 + 25]=23,
L(х5)=min[29,7 + 5]=12,
L(х6)=min[17,7 +1 6]=17.
КРОК 3. На даному кроці ітерації маємо наступні тимчасові позначки вершин:
L(х3) = 23, L(х5) = 29,
L(х6) = 17, L(х9) = 11.
Очевидно, що мінімальну позначку, рівну 11 має вершина х9 .
КРОК 4. За наступну поточну позначку приймаємо вершину х9, тобто p=х9, а її мітка стає постійною, L(х9) = 11+.
КРОК 5. Оскільки не всі вершини графа мають постійні позначки, переходимо до кроку 2.
Шоста ітерація.
КРОК 2. Знаходимо Г(х9)={х1,х2,х6,х7,х8}. Саме вершина х6 тимчасова, отже перераховуємо її значення: L(х6)=min[17,11+9]=17.
КРОК 3. На даному кроці ітерації маємо наступні тимчасові позначки вершин: L(х3) = 23, L(х5) = 12, L(х6) = 17.
Очевидно, що мінімальну позначку, рівну 12 має вершина х5 .
КРОК 4. За наступну поточну мітку приймаємо вершину х5, тобто p = х5, а її мітка стає постійною, L(х5) = 12+.
КРОК 5. Оскільки не всі вершини графа мають постійні мітки, переходимо до кроку 2.
Сьома ітерація.
КРОК 2. Знаходимо Г(х5) = {х4, х6}. Позначка вершини х6 тимчасова, отже, перераховуємо її значення:
L(х6)=min [17,12 + 10]=17.
КРОК 3. На даному кроці ітерації маємо наступні тимчасові позначки:
L(х3) = 23, L(х6) = 17.
Очевидно, що мінімальну позначку, рівну 17 має вершина х6 .
КРОК 4. За наступну поточну позначку приймаємо вершину х6, тобто p=х6, а її позначка стає постійною, L(х6) = 17+.
КРОК 5. Оскільки не всі вершини графа мають постійні позначки, переходимо до кроку 2.
Восьма ітерація.
КРОК 2. Знаходимо Г(х6)={х3,х5,х7,х8,х9}. позначка вершини х3 тимчасова, отже, перераховуємо її значення: L(х3)=min[23,17 + 20]=23.
КРОК 3. На даному кроці ітерації маємо одну тимчасову позначку вершини: L(х3)=23, яка стає постійною.
КРОК 4. Всі вершини мають постійні мітки, тому алгоритм закінчений. Для знаходження найкоротшого шляху між вершинами, наприклад, х2 і початковою х1 послідовно використовуємо співвідношення:
L(x'2)+c(x'2,x2)=L(x2) = 5, (5.3)
де вершина x'2 - це вершина, безпосередньо передуюча x2 в найкоротшому шляху від х1 до x2 . Єдиною такою вершиною є вершина х7 . Далі відношення (5.3) застосовуємо другий раз:
L(x'7)+с(x'7,x7)=L(x7)=3 (5.4)
Єдиною такою вершиною є вершина х1 . Тому найкоротший шлях від х1 до x2 є перелік вершин: х1, х7, х2.
Вершина х1, є базою та надає всі найкоротші шляхи від х1 , які надано на рис.5.34.
Дев'ята ітерація. Кінець алгоритму.
Рисунок 5.34 - Вершина х1 є базовою вершиною
5.10.4 Алгоритм Флойда
Алгоритм Флойда - динамічний алгоритм для находження найкоротших відстаней між усіма вершинами зваженого орієнтованого графа. Розроблений у 1962 році Робертом Флойдом. Роберт Флойд (англ. Robert Floyd, 8 червня 1936 року, Нью-Йорк, США - 25 вересня 2001 року, Стенфорд, США) - американський вчений в області теорії обчислювальних систем. Мав нагороди: у 1978 році - премія Тюрінга за його безперечний вплив на методологію створення ефективного і надійного програмного забезпечення і за його допомогу в становленні таких областей комп'ютерних наук як семантика мов програмування, автоматична верифікація програм, автоматичний синтез програм, і аналіз алгоритмів", у 1991 році - премія піонера обчислювальної техніки (англ. Computer Pioneer Award) від IEEE [4].
Припустимо, що ми маємо помічений орграф, який містить час польоту по маршрутах, що зв'язують певні міста.
Припустимо, що необхідно побудувати таблицю, де приводився би мінімальний час перельоту з одного (довільного) міста в будь-який іншій. В цьому випадку ми стикаємося із загальною задачею знаходження найкоротших шляхів, тобто знаходження найкоротших шляхів між всіма парами вершин орієнтованого графа.
Подобные документы
Поняття множини. Операції над множинами. Об’єднання і переріз двох множин. Різниця і доповненя множин. Множини з відношеннями. Прямий (декартів) добуток множин. Бінарні відношення. Відношення еквівалентності. Відношення порядку. Предикати.
курсовая работа [239,3 K], добавлен 10.06.2007Означення теорії множин. Дії над множинами. Алгебра множин. Вектори і прямий добуток множин. Властивості відношень. Способи задання функції. Сукупність підстановок множини. Алгебраїчні операції та системи. Властивості рефлексивності та симетричності.
конспект урока [263,1 K], добавлен 28.06.2012Поняття про бінарні відношення, способи їх задання, існуючі операції, характерні властивості. Відношення еквівалентності, порядку, домінування й переваги. Поняття та значення R-оптимальності, найкращого, найгіршого, максимального й мінімального елементів.
реферат [1,3 M], добавлен 04.10.2015Теорія множин як абстрактно-теоретична наука про множини довільної природи, розгляд головних проблем. Загальна характеристика теореми Кантора-Берштейна. Знайомство з властивостями множин потужності континууму. Аналіз діяльності математика К. Геделя.
курсовая работа [325,6 K], добавлен 27.04.2016Основні засади комбінаторики та теорії множин на основі аксіоматики Цермело-Френкеля і використання правила суми й добутку. Знаходження кусково-постійних конфігурацій множин засобами мови програмування IDE C++ Builder з допомогою вбудованого GUI.
контрольная работа [539,5 K], добавлен 27.11.2010Множина як визначена сукупність елементів чи об’єктів. Списковий спосіб подання множини. Множина, кількість елементів якої скінченна (скінченна множина). Виведення декартового добутку з кожної заданої комбінації. Алгоритм рішення та реалізація програми.
задача [112,0 K], добавлен 23.06.2010Визначення та властивості упорядкованих множин, приклади діаграм. Дистрибутивні ґрати як один з основних алгебраїчних об'єктів. Поняття нижньої і точної грані, їх властивості та приклади, доказ лем. Застосування та суть топологічних стоунових просторів.
курсовая работа [288,0 K], добавлен 24.03.2011Виключення третього як фундаментальний принцип логіки, істинність і хибність як логічні значення пропозиції. Таблиці істинності, поняття тавтології і еквівалентності. Властивості функцій множин і запереченням гіпотези Гольдбаха в термінах квантифікаторів.
реферат [82,7 K], добавлен 03.03.2011Поняття сукупності предметів, об'єднаних за певною характеристичною ознакою. Основні загальноприйняті множини (геометрична фігура, ГМТ, область визначення та значень функції). Позначення множин, їх елементи, належність об'єктів та способи задання.
презентация [517,1 K], добавлен 19.01.2011Визначення метричного простору. Границя функції у точці. Властивості границь дійсних функцій. Властивості компактних множин. Розв’язок системи лiнiйних рівнянь. Теорема про існування i єдність розв’язку диференціального рівняння. Нумерація формул.
методичка [461,1 K], добавлен 25.04.2014
