Алгоритм послідовної розмальовки графа

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

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

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

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

Алгоритм послідовної розмальовки графа — приклад:

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

Розфарбування графа - приклад

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

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

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

Прдовжуючи ітераційний процес далі, після виконання ітерації номер три, алгоритм послідовної розмальовки для заданого графа можна завершувати. Кожній з його вершин призначений певний колір (вершини «1», «3», «5» та «7» пофарбовані в зелений колір).

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

Блок-схема алгоритму послідовної розмальовки графа

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