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

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

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

Пошук Ейлерового циклу використовуючи алгоритм Флері в середовищі програмування delphi

Програму розроблено в середовищі програмування Delphi, основним призначенням якої є побудова Ейлерового циклу в Ейлеровому графі. В якості методу, використовується алгоритм Флері.

Граф задається у вигляді вершин (пронумеровані точки) та ребер (прямі лінії що їх з'єднюють). Для цього в програмі передбачено графічний редактор (компонент типу TImage) та дві кнопки типу TSpeedButton («Додати вершину» і «Додати ребро»). Підготовка проекту до нового прикладу здійснюється з допомогою кнопки «Видалити граф» (компонент типу TButton). При натисканні на кнопку «Побудувати Ейлерів цикл» (також компонент типу TButton) власне і запускається алгоритм Флері пошуку Ейлерового циклу.

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

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

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

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

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

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

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

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

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

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

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

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

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