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

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

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

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

Читати повністю

Знаходження точок сполучення зв'язного неорієнтованого графа та перевырка його на двозв'язність

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

Точки сполучення неорієнтованого графа

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

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

Читати повністю

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

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

Читати повністю

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

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

Читати повністю

Пошук мостів та компонент реберної двозв'язності в неорієнтованому графі

Мостом неорієнтованого графа називається ребро, при видаленні якого збільшується кількість компонент зв'язності графа. Відповідно, для зв'язного графа мостом називається ребро, при видаленні якого граф перестає бути зв'язним. При видаленні всіх мостів граф розпадається на компоненти зв'язності, які називаються компонентами реберної двозв'язності.

Між будь-якими двома вершинами однієї компоненти реберної двозв'язності існує, принаймні, два шляхи, що не перетинаються по ребрах. Справедливе і зворотне твердження: будь-які дві вершіні, між якими існують два шляхи, що не перетинаються по ребрах, належать одній компоненті реберної двозв'язності.

Між двома компонентами реберної двозв'язності не може бути більше одного ребра — в іншому випадку, вони утворюватимуть одну компоненту реберної двозв'язності. Якщо дві різні компоненти реберної двозв'язності з'єднані ребром, то це ребро — міст.

Читати повністю

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

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

poshuk_ejlerovogo_shljahu_v_grafi18

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

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

Читати повністю

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

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

Читати повністю

« Попередня сторінкаНаступна сторінка »