3.2. Алгоритми. Обходи графів. Побудова ейлеревих та гамільтонових циклів графа.

Далі ми будемо розглядати алгоритми на графах. У зв’язку з цим виникає питання, щодо визначення поняття „алгоритм”. Точне визначення поняття „алгоритм” виходить за рамки цього посібника. Ми будемо користуватися так званим „інтуїтивним” визначенням поняття „алгоритм”.

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

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

1. Дискретність. Алгоритм повинен бути розбитий на скінченну кількість елементарних кроків.

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

3. Зрозумілість. Алгоритм повинен бути зрозумілим виконавцю.

4. Масовість. Алгоритм повинен розв’язувати всі задачі з певного класу (наприклад, алгоритм розв’язання квадратного рівняння вигляду працює для будь-яких значеннях,таокрім випадку).

5. Скінченність. За скінченну кількість кроків алгоритм або повинен давати розв’язок задачі, або видавати інформацію, що розв’язок не існує.

Ми будемо розглядати алгоритми для графів із пронумерованими вершинами, номери різних вершин не співпадатимуть та знаходяться у множині , де кількість вершин графа.

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

Алгоритм 3.1. Побудова обходу графа у глибину.

Спочатку всі вершини не помічені, поточною є вершина з номером 1.

Крок 1. Помічаємо поточну вершину і переходимо до кроку 2.

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

Крок 3. Повертаємося до тієї вершини, з якої ми перейшли до поточної. Цю вершину вважаємо поточною та переходимо до кроку 2.

Алгоритм закінчує свою роботу у випадку, коли поточною є вершина з номером 1 та крок 2 виконати неможливо. ■

Алгоритм 3.2. Побудова обходу графа у ширину.

Спочатку всі вершини, окрім поточної вершини з номером 1 рівня є не поміченими.

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

Алгоритм закінчує свою роботу у випадку, коли для кожної вершини рівня не можна побудувати вершину рівня. ■

Проілюструємо хід виконання обходів у глибину та ширину на наступному прикладі.

Приклад 3.3. Побудувати обходи у глибину та ширину для графа, заданого списком:

.

Результат побудови обходів у глибину та ширину за алгоритмами 3.1 та 3.2 для цього графа є таким:

Рис. 3.9. Обходи у глибину (ліворуч) та ширину для графа з приклада 3.3.

Зауважимо, що при побудові обходу у глибину поточними були вершини 1, 3, 6, 3, 7, 4, 2, 4, 7, 5, 7, 3, 1; при побудові обходу у ширину поточними були вершини 1, 3, 5, 6, 7, 4, 2. ■

Розглянемо ще один відомий варіант обходу графа. Ейлеровим називають цикл (не обов’язково простий), що містить всі ребра графа точно по одному разу. Також виділяють ейлерів ланцюг – такий ланцюг (не обов’язково простий), що містить всі ребра графа по одному разу. Граф, що містить ейлерів цикл називають ейлеревим, а граф, що містить ейлерів ланцюг – напівейлеровим.

Поняття ейлеревого циклу та ланцюга виникло у звзку із розв’язком у 1736 році Леонардом Ейлером відомої «задачі про кенігсбергські мости». Це була перша опублікована робота, пов’язана з графами, що дозволяє називати Ейлера «батьком теорії графів» [Харари].

Необхідною та достатньою умовою ейлеровості та напівейлеровості графа є наступна

Теорема Ейлера. Граф є ейлеревим тоді і лише тоді, коли він є зв’язним, та степені всіх його вершин – парні числа. Граф є напівейлеревим тоді і лише тоді, коли він є зв’язним, степені двох його вершин непарні, а степені всіх інших його вершин парні. ■

Для напівейлерового графа дві вершини непарного степеня є початком та кінцем ейлеревого ланцюга.

Алгоритм 3.3. Побудова ейлеревого циклу.

Спочатку всі ребра є непоміченими, вершина з номером 1 є поточною.

Крок 1. Якщо поточній вершині інцидентне хоча б одне непомічене ребро, то переходимо по такому ребру до вершиниз найменшим номером, помічаємо реброта робимо поточною вершину. Далі виконуємо крок 1.

Крок 2. Якщо крок 1 виконати неможливо (тобто не існує жодного непоміченого ребра, інцидентного поточній вершині ), то поточною робимо вершину, яка передувала вершиніта виконуємо крок 1.

Алгоритм закінчує свою роботу у випадку, коли поточною є вершина з номером 1 та крок 1 виконати неможливо. ■

Проілюструємо хід побудови ейлеревого циклу на наступному прикладі.

Приклад 3.4. Побудувати ейлерів цикл для графа, заданого списком:

.

Безпосередньою перевіркою пересвідчуємося, що степені всіх вершин графа є парними числами, а тому граф є ейлеревим (за умови його зв’язності). Результат побудови ейлеревого циклу за алгоритмом 3.3 для цього графа є наступним:

Рис. 3.10. Ейлерів цикл для графа з приклада 3.4.

Зауважимо, що при побудові ейлеревого циклу поточними були вершини 1, 3, 4, 1, 6, 7, 1, 7, 2, 5, 3, 7, 3, 5, 2, 7, 6, 1, 4, 3, 1. ■

Розглянемо ще один відомий варіант обходу графа. Гамільтоновим називають простий цикл, що містить всі вершини графа. Іншими словами, гамільтоновим є цикл, що містить кожну вершину графу точно по одному разу. Граф, що містить гамільтонів цикл називають гамільтоновим. Зрозуміло, що гамільтонові графи є зв’язними. Також неважко пересвідчитися, що гамільтонові графи не мають вершин степеня 1. Дійсно, нехай є вершиною степеня 1 та суміжна лише вершині. Тоді у будь-якому обході, що містить всі вершини графа, вершиназустрінеться мінімум два рази: один раз перед вершиною, а другий раз – після неї. Таким чином, гамільтонів цикл у такому графі побудувати неможливо.

Назва «гамільтонів цикл» пішла від прізвища ірландського математика Уільяма Гамільтона (1805 – 1865), який першим розглянув цю задачу у 1859 році. Ця задача має широке застосування на практиці при побудові оптимальних маршрутів пересування. У математиці найбільш відомою задачею, що пов’язана із побудовою гамільтонових циклів є так звана «задача комівояжера».

На жаль, не існує жодного набору необхідних та достатніх умов гамільтоновості довільного зв’язного графа. Проте існує значна кількість достатніх умов, серед яких найбільш відомими є умови Дірака, Оре, Хватала, Караганіса [Бондаренко]. Не існує також жодного "ефективного" (тобто такого, що не здійснює повний перебір варіантів) алгоритму знаходження гамільтонових циклів, тому процедура їх знаходження є дуже складною в обчислювальному сенсі задачею. Один із найбільш простих та відомих методів знаходження всіх гамільтонових циклів графа використовує так зване дерево досяжності вершин графа.

Нехай граф маєвершин. Створення дерева досяжності полягає у послідовній побудовірівнів вершин із використанням відношення суміжності без повторів вершин у кожній гілці. Так, на перший рівень виставляємо будь-яку вершину (корінь дерева досяжності); на другий рівень – всі вершини, суміжні з коренем дерева (діти кореня дерева). З кожної вершини другого рівнябудуємо відповідні їй вершини третього рівня – вершини, що є суміжними вершиніта не є коренем дерева і т.д. При побудові наступних рівнів повинна виконуватися така умова: кожний шлях з кореня дерева до нижчих рівнів не може містити повтори вершин. Після побудови дерева досяжності виділяємо вершини останнього-го рівня, що є суміжними з коренем дерева (звісно, якщо такі вершини існують), виписуємо ці вершини за рівнями "згори донизу" та у кінці кожної такої послідовності дописуємо вершину, що є коренем дерева досяжності. Ці послідовності вершин і будуть гамільтоновими циклами графа. В такий спосіб ми одержемо всі гамільтонові цикли графа, а якщо немає жодної такої послідовності, то граф не є гамільтоновим.

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

Проілюструємо виконання вищевказаної процедури на наступному прикладі.

Приклад 3.5. Знайти всі гамільтонові цикли для графа, заданого списком:

.

Побудуємо дерево досяжності для цього графа із коренем у вершині 1 (рис 3.11).

Рис. 3.11. Дерево досяжності для графа з приклада 3.5.

На цьому рисунку на останньому рівні підкреслено вершини, що суміжні вершині 1. З дерева досяжності одержимо такі послідовності вершин:

а) 1, 3, 2, 5, 4, 6, 1; г) 1, 4, 5, 6, 2, 3, 1;

б) 1, 3, 2, 5, 6, 4, 1; д) 1, 4, 6, 5, 2, 3, 1;

в) 1, 3, 2, 6, 5, 4, 1; е) 1, 6, 4, 5, 2, 3, 1.

При цьому послідовність (а) є парою до послідовності (е), (б) – до (д) та послідовність (в) є парою до послідовності (г). Запишемо у відповідь послідовності (а), (б) та (в). ■

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

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

Проілюструємо спрощену процедуру пошуку гамільтонових циклів.

Приклад 3.6. Для графа з приклада 3.5 побудувати всі гамільтонові цикли.

Побудуємо дерево досяжності для графа із коренем у вершині 3 (рис 3.12).

Рис. 3.12. Дерево досяжності для графа з приклада 3.6.

З дерева досяжності одержимо такі гамільтонові цикли:

а) 3, 1, 4, 5, 6, 2, 3;

б) 3, 1, 4, 6, 5, 2, 3;

в) 3, 1, 6, 4, 5, 2, 3.

При цьому цикл (а) з приклада 3.6 відповідає циклу (в) з приклада 3.5, цикл (б) з приклада 3.6 – циклу (б) з приклада 3.5, а цикл (в) приклада 3.6 – циклу (а) з приклада 3.5, тобто ми одержали однакові відповіді. ■

Оцінимо число ейлеревих та гамільтонових графів. Через позначимо множину зв’язних графів звершинами, черезта– відповідно множину ейлеревих та гамільтонових графів звершинами. Справедливе

Твердження 3.5. [Новиков].

1. Ейлерових графів майже нема, тобто .

2. Майже всі графи є гамільтоновими, тобто . ■