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

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

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

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

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

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

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

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

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

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

rozfarbuvannja_grafa22

Використання алгоритму методу перебору для розв’язку задачі про розфарбування графа

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

Розфарбування вершин графа використовуючи переборний алгоритм – приклад:

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

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

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

rozfarbuvannja_grafa26

Дерево варіантів

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

Отже, на першому кроці, розфарбуємо кожну вершину графа з мінімальним хроматичним числом в свій колір. Наприклад, вершину  «d» в червоний колір, і вершину «1» – в синій. Після цього, виходячи з того, що вершина «d» була отримана в результаті злиття двох вершин «4» та «a» фарбуємо їх також в червоний колір. І на останньому кроці, з аналогічних міркувань, фарбуємо вершини «2» та «3» також в червоний колір. В результаті отримаємо:

Правильне розфарбування вершин неорієнтованого графа
Блок-схема алгоритму знаходження числа кольорів необхідного для реалізації правильного розфарбування графа

rozfarbuvannja_grafa28

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

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

*