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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Побудова дерева обходу в ширину в середовищі програмування delphi

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

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

Пошук в ширину на delphi

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

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

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

Наступна сторінка »