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

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

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

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

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

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

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

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

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

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

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

Топологічне сортування вершин орієнтованого графа методом видалення вершини-джерела в середовищі програмування delphi

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

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

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

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

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

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

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

Далі, перейдемо до практики, тобто, застосуємо розглядуваний в даному параграфі delphi-проекту для розв'язку задачі, яка полягає у відшуканні всіх компонент сильної зв'язності орієнтованого графа наступного вигляду:

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

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

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

Топологічне сортування вершин орієнтованого графа в середовищі програмування delphi

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

Головна форма розглядуваного проекту складається з панелі інструментів та графічного редактора.

Головне вікно проекту "Топологічне сортування вершин орієнтованого графа"

Розглянемо призначення кожного з цих едементів більш детально.

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

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

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

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

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

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

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

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

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

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

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

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

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