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

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

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

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

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

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

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

Читати далі

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

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

Читати далі

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

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

Читати далі

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

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

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

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

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

Читати далі