Категорія: Цикли

Перевірка орієнтованого графа на наявність циклів

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

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

Пошук циклів в орієнтованому графі

Перевірка орієнтованого графа на наявність циклів

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

Читати далі

Пошук Гамільтоновго циклу в неорієнтованому графі

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

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

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

Читати далі

Побудова Ейлерового циклу в неорієнтованому графі використовуючи алгоритм Флері

Перш ніж приступити до розгляду чергового алгоритму рішення задачі пошуку Ейлерового циклу нагадаємо собі означення та необхідну умову його існування в неорієнтованому графі. Отже, Ейлеровим циклом називається замкнутий маршрут, в якому кожне ребро графа зустрічається точно один раз. Згідно з твердженням, яке ми розглядали в минулому параграфі, для існування такого маршруту в зв’язному графові необхідно і достатньо, щоб степені всіх його вершин були парними. Відмітимо, що в даному параграфі нами вже було вивчено один з можливих вірівнтів знаходження Ейлерового циклу, який базується на використанні алгоритму обходу графа в глибину. Сьогодні розглянемо дещо простішу та наочнішу процедуру відому під назвою алгоритм Флері.

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

Читати далі

Пошук Ейлерового циклу в неорієнтованому графі

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

Пошук Ейлерового циклу в графі

Графічне представлення алгоритму пошуку Ейлерового циклу

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

Читати далі