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

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

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

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

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

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

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

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

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

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

Розфарбування вершин графа найменшим набором кольорів

Скачати delphi-проект Послідовна розмальовка графа.

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