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

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

Для того, щоб запустити програму необхідно, в каталозі де збережено delphi-проект, знайти файл Project1.ехе і запустити його. Після запуску програми на екрані буде відображено наступне вікно.

Побудова Гамільтонового циклу на delphi

Головне вікно проекту "Побудова Гамільтонового циклу для неорієнтованого графа"

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

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

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

Після того, як граф побудовано, для відшукання його Гамільтонових циклів достатньо скористатись кнопкою «Знайти Гамільтонів цикл» (для того, щоб видалити весь граф і повернути програму в початковий стан необхідно скористатись кнопокою «Видалити граф»).

В якості демонстрації можливостей роботи програми, наведемо приклад рішення задачі на знаходження Гамільтонового циклу для неорієнтованого графа наступного вигляду:

gaimiltoniv_cykl_delphi2

Неорієнтований граф

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

gaimiltoniv_cykl_delphi3

Побудова неорієнтованого графа

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

Побудова Гамільтонового циклу

Скачати delphi-проект Побудова Гамільтонового циклу для неорієнтованого графа.

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар