Алгоритм Шімбелла (реалізація в середовищі Delphi)

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

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

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

schimbels_method_delphi1

Створення вершин орієнтованого графа

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

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

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

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

Головне вікно проекту "Послідовна розмальовка графа"

Отже, головна форма delphi-програми ділиться на три частини і складається з панелі інструментів (компонент типу TPanel), графічного редактора (компонент типу TImage) та області виводу резільтатів (компонент типу TMemo):

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

Алгоритм Форда-Беллмана (реалізація в середовищі Delphi)

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

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

Головне вікно проекту "Знаходження дерева мінімальної вартості за алгоритмом Беллмана-Форда"

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

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

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

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

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

Головне вікно проекту "Розфарбування вершин графа"

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

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

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

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

Головне вікно проекту "Перевірка неорієнтованого графа на дводольність"

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

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

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

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

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

Вихідні дані програми — побудова дерева обходу в глибину та вивід у компонентів TMemo послідовності вершин орієнтованого циклу, якщо він існує.

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

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

Розглядуваний в даному параграфі delphi-проект реалізує процес побудови дерева обходу в глибину для орієнтованого графа. Головна форма проекту, як і у випадку з глибинним обходом неорієнтованого графа, ділиться на дві частини і складається з панелі інструментів та графічного редактора.

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

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

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

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

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