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

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

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

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

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

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

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

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

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

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

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

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

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар