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

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

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

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

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

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

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

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

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

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

Правильне розфарбування вершин неорієнтованого графа

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

Скачати delphi-проект Розфарбування вершин графа.

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