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

 
 

 

 


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

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

Определения
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-раскрашиваемым.

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

 

 


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

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

 

 


Для хроматического числа простого графа 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 цветов.

                     
   
 
     
 
 
   
Рис.2.14.2. Реберная раскраска графов
 
Меры
 
   
 

 


· 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-сложной.

 

 

еще рефераты
Еще работы по информатике