Раскраска в графах

Раскраска связана с решением задач оптимизации: Задан граф G. Нужно раскрасить вершины графа в разные цвета так, чтобы смежные вершины были окрашены в разные цвета, а при раскраске использовался минимум разных цветов. Минимальное количество цветов связано с понятием хроматического числа.

Определения:

1. Множество вершин графа называется внутренне устойчивым, если у любой пары вершин этого множества отсутствует соединительное ребро.

2. Множество вершин графа называется максимальным внутренне устойчивым, если при добавлении к нему одной вершины оно превращается во внутренне неустойчивое.

3. Множество вершин графа называется внутренне неустойчивым, если в нем найдется хотя бы одна пара вершин, связанная ребром.

Пример: Задан граф без петель. Выполним разбиение вершин графа на внутренне устойчивые взаимно непересекающиеся подмножества.

Вариантов несколько:

А₄ = {7}

Тогда каждому множеству A_i в каждом варианте разбиений можно сопоставить свой цвет.

Варианты 2 и 3 требуют 3-х цветов, 1 – 4-х цветов для раскраски.

Граф называется K-хроматическим, если он допускает раскраску своих вершин в K цветов при условии, что смежные вершины окрашены в разные цвета.

Минимальное число K цветов, при котором граф ещё остается K-хроматическим, называется хроматическим числом. Его можно получить (как в примере) перебором всех вариантов разбиения множества вершин на множество взаимно непересекающихся внутренне устойчивых подмножеств. Выбирается вариант с минимальным числом подмножеств. Это и есть хроматическое число .