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

Определения

Раскраской частей плоскости, связей между объектами и т.д. явялется присваение различной мпркировки (цветов, чисел, букв и т.д.) каждой компоненте.

Раскраска графов– присвоение маркировки либо вершинам, либо ребрам графа.

2

Определения

.14.1. Раскраска вершин графа

Пусть G=(V,E) , будет графом, а{1,2,3,…,k} – подмножеством натуральных чисел («цвета»).

Тогда отображение f:V→ {1,2,3,…,k} называютk-раскраской вершин графа G.

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

Граф G=(V,E) называютk-раскрашиваемым, если для него существует правильнаяk-раскраска.

Пример

Рис.2.14.1. 5-раскрашиваемый граф

Меры

• χ(G) – хроматическое числографаG. Является наименьшим числомk, для которого графGбудетk-раскрашиваемым.

Примеры

Класс графа

Хроматическое число χ(G)

Полносвязный граф К_n

n

Граф звезда S_n,n>1

2

Граф цикл (кольцо) C_n,n>1

3 для nнечетных,

2 для n четных

Граф колесо W_n,n>2

3 для nнечетных,

4 для n четных

Теоремы

Терема о четырех цветах

Хроматическое число простого планарного графа не более четырех.

Теорема Брукса (Brooks)

Для хроматического числа простого графа Gсправедливо утверждение

χ(G) ≤ Δ(G) + 1,

где Δ(G) – максимальная степень графаG.

Равенство выполняется только для полносвязных графов K_nи нечетных цикловC_n.

Теорема 1

Если ω(G) – размер наибольшей клики графаG=(V,E), тоχ(G) ≥ω(G)

Теорема 2

Если α(G) – число независимости графаG=(V,E), то

Теорема Кёнига (Konig)

Назовем граф, для которого χ(G) = 2, бихроматическим.

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

Следствие 1. Любое дерево бихроматично.

Следствие 2.Любой двудольный граф бихроматичен.

Класс сложности

Определение хроматического числа графа в общем случае является NP-трудной. Раскраска графа –NP-сложной.

Точные решения

Точные алгоритмы (методы линейного программирования, квадратичного бинарного программирования без ограничений и т.д.) позволяют решать задачу раскраски графа размерностью не более 100-200 вершин.

Эвристические алгоритмы

Последовательные эвристические алгоритмы раскраски вершин графа можно разделить на три группы:

• жадные алгоритмы, в которых для заданного упорядочения вершин последовательно делаются попытки раскрасить вершины с использованием некоторого количества цветов;

• для заданного упорядочения вершин делается попытка последовательно раскрасить вершины вначале в 1 цвет, затем в 2 и т.д.

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

Упорядочение вершин графа производится двумя способами:

• наибольшая степень вершин первая, когда вершины записываются а порядке убывания степени;

• наименьшая степень первая, когда вершины записываются в порядке возрастания их степеней.

Жадный последовательный алгоритм

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

2. Начиная с первой не раскрашенной вершины в упорядочении, раскрасить ее в первый цвет, скажем цвет А.

3. Просмотреть список всех не раскрашенных вершин. Каждую не раскрашенную вершину раскрасить в цвет А, если ни одна из инцидентных ей вершин не раскрашена в цвет А.

4. Повторять 2 и 3 для других неиспользованных цветов (скажем В,С,…) до тех пор, пока все вершины не будут раскрашены.

Пример

4

1

Упорядочение вершин по возрастанию степеней:

{deg₃ =4, deg₂ =3, deg₅ =3, deg₁ =2, deg₄ =2}

1 – цвет С,

2 – цвет В,

3 – цвет А,

4 – цвет В,

5 – цвет С

(G) = 3

3

5

2

Шаг 1.Выбираем вершину 3 и раскрашиваем ее в цвет А.

Шаг 2.Из списка степеней выбираем вершину 2. Раскрасить ее в цвет А не удается (вершина 2 инцидентна вершине 3).

Шаг 3.Из списка степеней выбираем следующую вершину 5. Раскрасить ее в цвет А не удается (вершина 5 инцидентна вершине 3).

Шаг 4.Из списка степеней выбираем вершину 1. Раскрасить ее в цвет А не удается (вершина 1 инцидентна вершине 3).

Шаг 5.Из списка степеней выбираем вершину 4. Раскрасить ее в цвет А не удается (вершина 4 инцидентна вершине 3).

Шаг 6.Из списка степеней вершин вычеркиваем раскрашенные вершины. В нашем случае: {deg₂=3,deg₅=3,deg₁=2,deg₄ =2}.

Шаг 7.Из списка выбираем вершину 2. Раскрашиваем ее в цвет В.

Шаг 8.Следующая вершина в списке – вершина 5. Раскрасить ее цвет В не удается (вершина 5 инцидентна вершине 2).

Шаг 9.Из списка выбираем вершину 1. Раскрасить ее в цвет В не удается (вершина 1 инцидентна вершине 2).

Шаг 10.Из списка степеней вершин выбираем вершину 4. Раскрашиваем ее в цвет В, т.к. вершина 4 не инцидентна вершине 2).

Шаг 11.Из списка степеней вычеркнуть раскрашенные в цвет В вершины. В нашем случае: {deg₅=3,deg₁=2}.

Шаг 12.Выбираем вершину 5 и раскрашиваем ее в цвет С.

Шаг 13.Выбираем вершину 1 раскрашиваем ее в цвет С, т.к. она не инцидентна с вершиной 1, а вершины 2, 3 и 4 раскрашены в другие цвета.

Шаг 14. Из списка вычеркиваем вершины раскрашенные в цвет С. Список пуст, алгоритм стоп.

Пример

Три клики максимального размера:

• {1,2},{2,3},{3,1}

• {2,3},{3,5},{2,5}

• {3,4},{3,5},{4,5}

4

1

3

5

2

Согласно Теореме 1:

(G)(G), т.е.(G)  3

Интуитивно раскрасим граф двумя способами.

Первое решение:

1 - красный



4



1 - красный



1 - зеленый



4- красный





1



1 - синий

1 - красный



1 - зеленый



4 - красный





1 - черный



1 - синий

1 - зеленый





1



1 - синий

в)

а)

б)

Четыре цвета, (G) = 4

Второе решение: