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

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

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

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

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

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

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

Визначити, чи являється орієнтований граф, який зображено на наступному малюнку, ациклічним.

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

Орієнтований граф задачі

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

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

Дерево обходу в глубину заданого орієнтованого графа

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

Блок-схема алгоритму перевірки орієнтованого графа на наявність циклів

Залишити коментар

Your email address will not be published. Required fields are marked *

*