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

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

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

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

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

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