Раскраска графов. Лекция 07

Раскраска графов
Определение. Пусть G=(V, E) – неориентированный граф и k – натуральное число.
Функция f: V→{1,…,k} называется раскраской графа.
Раскраска называется правильной, если для любых смежных вершин x,y∈V справедливо неравенство f(x) ≠ f(y). Число k – количество красок раскраски f.
Определение. Наименьшее число красок, необходимое для правильной раскраски графа G называется хроматическим числом графа G.
Правильную раскраску таким числом красок будем называть оптимальной.
Хроматическое число обозначается через χ(G).

Пример
χ(G1) = 3 χ(G2) = 4

Задача составления расписаний
Предположим, что в учебном центре надо провести несколько занятий за кратчайшее время.
Длительность всех занятий одинакова, например, один час. Некоторые занятия не могут проводиться одновременно, например, это занятия в одной и той же учебной группе (по разным предметам), или занятия проводит один и тот же преподаватель.
Для решения задачи построим граф G, вершинам которого взаимнооднозначно соответствуют занятия. Две вершины соединены ребром, если соответствующие занятия нельзя проводить одновременно.
Ясно, что правильная раскраска графа G определяет расписание, удовлетворяющее требованиям несовместимости по времени: занятия, соответствующие вершинам, окрашенным одинаково, можно проводить одновременно.
Справедливо и обратное, любое такое расписание определяет правильную раскраску графа G. Следовательно, кратчайшее время необходимое для проведения всех занятий равно χ(G), а из оптимальной раскраски графа G получается необходимое расписание.

Задача распределения ресурсов
Необходимо выполнить некоторое множество V={v1,v2,…,vn} работ.
Имеется множество S={s1,s2,…,sr} ресурсов, требуемых для выполнения этих работ.
Каждая работа использует часть указанных ресурсов.
Одновременно могут выполняться работы, использующие разные ресурсы.
Все работы выполняются за одно и то же время t.
Нужно распределить ресурсы так, чтобы общее время выполнения всех работ было минимальным.
Рассмотрим граф G с множеством вершин V. Две различные вершины v и v’ графа G смежны тогда и только тогда, когда для выполнения работ v и v’ требуется хотя бы один общий ресурс.
Наименьшее время выполнения всех работ равно χ(G)·t.
Оптимальная раскраска графа G определяет распределение ресурсов.

Задача экономии памяти
Предположим, что необходимо написать программу для вычисления функции φ(х1,x2,…,xn). Вычисление этой функции разбито на ряд блоков, у каждого из блоков имеются входные и выходные переменные.

Предположим, что значения переменной занимают одну ячейку памяти.
Задача состоит в том, чтобы определить наименьшее число ячеек памяти, необходимое для хранения указанных в блок – схеме переменных.
Решить эту задачу можно следующим образом. На множестве переменных V={a,b,…,g,h} введем структуру графа: две переменных соединим ребром, если времена их жизни пересекаются. Полученный граф будем называть графом несовместимости переменных.
Значения переменных не могут занимать одну ячейку памяти тогда и только тогда, когда переменные соединены ребром в графе несовместимости.
Следовательно, задача экономии памяти сводится к нахождению оптимальной раскраски графа несовместимости.

Алгоритм последовательной раскраски
Упорядочиваем вершины графа G: V={v1,v2,…,vn}.
Вершину v1 красим первой краской.
Предположим, что вершины v1,…,vi уже раскрашены и на это использовано k красок.
Если на раскрашенные вершины, смежные с vi+1, использованы все краски, то vi+1 раскрашиваем k+1 краской.
Если среди k красок найдется краска, которая не использована для вершин, смежных с vi+1, то вершину vi+1 красим этой краской.
1
2
4
3
7
6
5
8
9
10
11
12
1
2
3
4

Раскраска ребер
Реберная раскраска называется правильной, если смежные ребра имеют различные цвета.
Граф, доаускающий правильную реберную k-раскраску, называется реберно k-раскрашиваемым.

Проблема четырех красок
Проблема возникла в математике в середине 19 века.
Первоначально вопрос формулировался так: сколько нужно красок для раскраски любой географической карты, при которой соседние страны раскрашены в разные цвета?
Достаточно ли четырех красок для раскраски любой географической карты?
Достаточно ли четырех красок, чтобы раскрасить любой планарный граф (граф, в котором можно так расположить вершины, что ребра, соединяющие их, не пересекаются).
1
2
3
4
5
6
7

Проблема четырех красок
Эта проблема вызвала большой интерес в математике.
Есть свидетельства, что ей занимались известные математики Мебиус и де Морган.
В 1880 году А. Компе опубликовал положительное решение проблемы четырех красок.
Однако в 1890 году Р. Хивуд обнаружил ошибку в этом доказательстве. Он доказал, что любой планарный граф можно раскрасить пятью красками.
После этого появлялось довольно много «доказательств» гипотезы четырех красок и «контрпримеров» к ней, в которых обнаруживались ошибки.