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

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

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

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

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

Переборний алгоритм для розфарбування вершин графа

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

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

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

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

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

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

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

Дводольний граф

Приклад дводольного графа

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

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