7. Раскраска графов

На практике часто необходимо разбить множество вершин на классы попарно несмежных вершин, причём таких классов требуется найти наименьшее число.

Пусть G=(V,E) граф, k – натуральное число. Функция f, переводящая множество вершин в множество {1,2,…,k} называется раскраской графов.

Раскраска называется правильной, если для любых смежных вершин x и y

k – это число красок в раскраске f. Правильность раскраски означает что смежные вершины раскрашиваются в разные цвета.

Наименьшее число красок χ , необходимых для правильной раскраски графа G называется хроматическим числом графа G, а раскраска является оптимальной.

Оба графа содержат трёхэлементный полный подграф.

Если G1, G2,…,GC – компоненты связности графа G, то χ(G)=max{χ(G1);χ(G2);…;χ(GC)}, в том числе и для компонент двусвязности.

Приведём примеры задач, которые сводятся к нахождению хроматического числа, соответствующее оптимальной раскраске.

+ точки сочленения и двусвязные компоненты.

8. Алгоритмы раскраски графов

Если нет формулы для вычисления хроматического числа, то можно использовать приемлимые оценки этого значения.

Плотностью ϕ(G) называется наибольшее число вершин полного подграфа графа G. Определение плотности графа связано с решением задачи о клике (кликой называют полный подграф).

Для любого графа G выполняется ϕ(G)≤χ(G) – хроматическое число графа не может быть меньше плотности (мощности максимальной клики). На практике разность между ϕ(G) и χ(G) может быть сколь угодно большой.

Число независимости графа – вторая оценка.

Множество попарно несмежных вершин называется независимым множеством. Числом независимости β(G) называется наибольшее число вершин независимого подмножества.

Тогда для любого графа G нижняя граница будет

где n – число узлов.

Однако вычисления независимости и плотности столь же сложна, как и задача вычисления хроматического числа. Для упрощения более грубая оценка нижней границы хроматического числа , где m – число дуг,

Верхняя граница часто определяется по теореме Брукса и обозначается – наибольшая степень вершин графа G, т.е.

∆(G) может быть сколь угодно далека от χ(G), и является приемлемой для тех графов, степени вершин которых предельно одинаковы. Задача определения хроматического числа относится к np-полным задачам, поэтому не существует алгоритма, решающего её за полиномиальное время. Предложим полиномиальный алгоритм, дающий приближённое (локально-оптимальное) решение.

1. Упорядочиваем вершины графа, т.е. задаём лексикографический порядок.

2. Предположим, что вершины уже раскрашены в число красок L. Тогда при раскраске вершины проверяем:

   1. Если при раскраске вершин смежных ( ) использованы все L красок, до добавляем краску и её закрашиваем вершину .

   2. Если существует краска , не использованная при раскраске смежных вершин , то ею раскрашиваем вершину .

«Гипотеза четырёх красок» - для любого планарного графа хватает для раскраски четырёх красок.

9. Задачи сводимые к задачи раскраски

1. Задача составления расписания

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

Для решения построим граф, к вершинам которого биективно соответствуют занятия. Две вершины соединены ребром, если соответствующие занятия нельзя проводить одновременно. Тогда правильная раскраска графа G определяет расписание, удовлетворяющее требованиям несовместимости: занятия, проводимые одновременно раскрашены одним цветом. Тогда хроматическое число определяет минимальное число лекций.