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

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

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

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

Delphi-прект реалізує черговий алгоритм з курсу теорія графів і призначений для пошуку Ейлерового циклу в неорієнтованому графі. Інтерфейс головної форми аналогічний до розглянутих в попередніх параграфах delphi-проектів (обхід графа в глибину, обхід графа в ширину, перевірка графа на наявність циклів). Тобто, задання графа здійснюється з допомогою графічного редактора і кнопок «Додати вершину» та «Додати ребро» (містяться на панелі інструментів). Підготовка проекту до нового прикладу здійснюється з допомогою кнопки «Видалити граф». А вивід списку вершин, послідовний обхід яких, для заданого графа, утворює Ейлерів цикл та його графічне представлення — з допомогою кнопки «Побудувати Ейлерів цикл». Провіримо його роботу на конкретному прикладі. Для цього, розглянемо неорієнтований граф наступного вигляду.

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

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

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

poshuk_ejlerovogo_shljahu_v_grafi18

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

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

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

Програмна реалізація методу подвійного обходу в середовищі delphi

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

Отже, після запуску проекту, на екрані появиться форма наступного вигляду:

Головне вікно проекту "Розв'язок задачі комівояжера методом подвійного обходу мінімального кістяка"

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

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

Розв'язок задачі комівояжера використовуючи метод подвійного обходу мінімального кістяка

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

Далі, у вигляді списку, запишемо методи рішення задачі комівояжера, які нами вже було розглянуто і з теоретичною частиною яких можна ознайомитись, перейшовши по відповідному посиланню:

  1. Метод редукції рядків та колонок.
  2. Метод осереднених коефіцієнтів.
  3. Метод Монте-Карло.
  4. Метод найближчого сусіда.

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

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