Лекция: Раскраска графов
Раскраской частей плоскости, связей между объектами и т.д. явялется присваение различной мпркировки (цветов, чисел, букв и т.д.) каждой компоненте.
Раскраска графов – присвоение маркировки либо вершинам, либо ребрам графа.
2.14.1. Раскраска вершин графаОпределения
Пусть G=(V,E), будет графом, а{1,2,3,…,k} – подмножеством натуральных чисел («цвета»).
Тогда отображение f: V → {1,2,3,…,k} называют k-раскраской вершин графа G.
k-раскраска будет правильной, если смежные вершины получают различную окраску.
Граф G=(V,E) называют k-раскрашиваемым, если для него существуетправильная k-раскраска.
| ||||||
| ||||||
· χ(G) –хроматическое число графа G. Является наименьшим числом k, для которого граф G будет k-раскрашиваемым.
| |||||||
Хроматическое число простого планарного графа не более четырех.
| |||
Для хроматического числа простого графа G справедливо утверждение
χ(G) ≤ Δ(G) + 1,
где Δ(G) – максимальная степень графа G.
Равенство выполняется только для полносвязных графов Kn и нечетных циклов Cn.
Если ω(G) – размер наибольшей клики графа G=(V,E), то χ(G) ≥ω(G)
Если α(G) – число независимости графа G=(V,E), то
Назовем граф, для которого χ(G) = 2, бихроматическим.
Непустой граф является бихроматическим тогда и только тогда, когда он не содержит циклов нечетной длины.
Следствие 1. Любое дерево бихроматично.
Следствие 2. Любой двудольный граф бихроматичен.
Определение хроматического числа графа в общем случае является NP-трудной. Раскраска графа – NP-сложной.
|
Точные алгоритмы (методы линейного программирования, квадратичного бинарного программирования без ограничений и т.д.) позволяют решать задачу раскраски графа размерностью не более 100-200 вершин.
| |||
Последовательные эвристические алгоритмы раскраски вершин графа можно разделить на три группы:
· жадные алгоритмы, в которых для заданного упорядочения вершин последовательно делаются попытки раскрасить вершины с использованием некоторого количества цветов;
· для заданного упорядочения вершин делается попытка последовательно раскрасить вершины вначале в 1 цвет, затем в 2 и т.д.
· для заданного упорядочения вершин делается попытка последовательно раскрасить вершины в х цветов, где х определяется специфическим путем (например, по размеру максимальной клики).
Упорядочение вершин графа производится двумя способами:
· наибольшая степень вершин первая, когда вершины записываются а порядке убывания степени;
· наименьшая степень первая, когда вершины записываются в порядке возрастания их степеней.
1. Упорядочить вершины в порядке убывания, случайно располагая в списке вершины с одинаковыми степенями.
2. Начиная с первой не раскрашенной вершины в упорядочении, раскрасить ее в первый цвет, скажем цвет А.
3. Просмотреть список всех не раскрашенных вершин. Каждую не раскрашенную вершину раскрасить в цвет А, если ни одна из инцидентных ей вершин не раскрашена в цвет А.
4. Повторять 2 и 3 для других неиспользованных цветов (скажем В, С,…) до тех пор, пока все вершины не будут раскрашены.
Шаг 1. Выбираем вершину 3 и раскрашиваем ее в цвет А.
Шаг 2. Из списка степеней выбираем вершину 2. Раскрасить ее в цвет А не удается (вершина 2 инцидентна вершине 3).
Шаг 3. Из списка степеней выбираем следующую вершину 5. Раскрасить ее в цвет А не удается (вершина 5 инцидентна вершине 3).
Шаг 4. Из списка степеней выбираем вершину 1. Раскрасить ее в цвет А не удается (вершина 1 инцидентна вершине 3).
Шаг 5. Из списка степеней выбираем вершину 4. Раскрасить ее в цвет А не удается (вершина 4 инцидентна вершине 3).
Шаг 6. Из списка степеней вершин вычеркиваем раскрашенные вершины. В нашем случае: {deg2 =3, deg5 =3, deg1 =2, deg4 =2}.
Шаг 7. Из списка выбираем вершину 2. Раскрашиваем ее в цвет В.
Шаг 8. Следующая вершина в списке – вершина 5. Раскрасить ее цвет В не удается (вершина 5 инцидентна вершине 2).
Шаг 9. Из списка выбираем вершину 1. Раскрасить ее в цвет В не удается (вершина 1 инцидентна вершине 2).
Шаг 10. Из списка степеней вершин выбираем вершину 4. Раскрашиваем ее в цвет В, т.к. вершина 4 не инцидентна вершине 2).
Шаг 11. Из списка степеней вычеркнуть раскрашенные в цвет В вершины. В нашем случае: {deg5 =3, deg1 =2}.
Шаг 12. Выбираем вершину 5 и раскрашиваем ее в цвет С.
Шаг 13. Выбираем вершину 1 раскрашиваем ее в цвет С, т.к. она не инцидентна с вершиной 1, а вершины 2, 3 и 4 раскрашены в другие цвета.
Шаг 14. Из списка вычеркиваем вершины раскрашенные в цвет С. Список пуст, алгоритм стоп.
Интуитивно раскрасим граф двумя способами.
Первое решение:
Второе решение:
2.14.2. Раскраска ребер графаОпределения
Пусть G = (V,E) будет графом, а {1,2,3,…,k} – подмножество натуральных чисел («цвета»).
Тогда отображение j: E® {1,2,3,…,k}называют k-раскраской ребер графа G.
k-раскраска будет правильной, если смежные ребра получают различную окраску.
Граф называется k-реберно-раскрашиваемым, если существует правильная раскраска ребер в k цветов.
| ||||||||||
| ||||||||||
· c’(G) – реберное хроматическое число илихроматический индекс: минимальное число k, при котором существует правильная k-раскраска ребер графа).
Если D(G) – минимальная степень простого графа, то
D(G) £ c’(G) £ D(G) +1
Для двудольных графов c’(G) = D(G).
| |||
Проблема раскраски ребер в c’(G) цветов является NP-тяжелой, а проблема нахождения c’(G) – NP-сложной.
Пусть f будет функцией, которая присваивает цвета ребрам графа. Тогда f-раскраской графа G является раскраска ребер этого графа, такой, что для каждой вершины vÎV по меньшей мере f(v) ребер, инцидентных вершине v, раскрашены одним цветом.
Обычная раскраска ребер графа есть специальный случай f-раскраски при f=1 для каждой вершины vÎV.
| |||
· c’f — f-хроматический индекс -минимальное число цветов, необходимое для f-раскраски графа.
|
Проблема нахождения f-раскраски ребер графа является NP-тяжелой, а нахождение f-хроматического индекса – NP-сложной.