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

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

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

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

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

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

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

poshuk_ejlerovogo_shljahu_v_grafi18

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

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

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

Перевірка неорієнтованого графа на наявність циклів в середовищі програмування delphi

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

Отже, delphi-проект складається з однієї форми, яка в свою чергу складається з наступних елементів: панель інструментів (компонент типу TPanel — служить контейнером для чотирьох кнопок «Додати вершину», «Додати ребро», «Видалити граф», «Перевірити граф на наявність циклів»), графічний редактор (компонент типу TImage) та область виводу результатів (компонент типу TMemo). Перші два з них призначені для побудови та графічного представлення неорієнтованого графа і третій — виводить, у вигляді послідовності вершин, в якій кожна вершина з'єднана з наступною ребром, всі цикли, які містить розглядуваний граф.

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

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

Пошук компонент зв'язності графа використовуючи алгоритм обходу в глибину

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

Відмітимо, що для розв'язку задач такого типу, зазвичай, використовують один з двох алгоритмів. Це обхід графа в глибину або обхід графа в ширину. Розглядуваний delphi-проект реалізує перший з них.

Отже, головна форма проекту ділиться на три частини і складається з панелі інструментів, графічного редактора та області виводу результатів. Розглянемо призначення кожної з них більш детально.

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

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

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

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

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

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

Пошук в глибину

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

У загальному випадку, коли ми перейшли в будь-яку вершину графа, в нашому випадку це вершина , виникають два варіанти можливих дій:

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