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

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

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

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

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

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

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

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

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

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

poshuk_ejlerovogo_shljahu_v_grafi18

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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