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

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

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

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

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

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

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

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

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

Після цього, скориставшись відповідною кнопкою, перевіримо неорієнтований граф на дводольність.

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

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

Залишити коментар

Your email address will not be published. Required fields are marked *

*