Раскраски графов Раскраска вершин Пусть Г (V,E,Ф) – граф, раскраска вершин Г в n цветов – отображение f : V {1,2,…,n } Правильная раскраска вершин графа. - презентация

1 Раскраски графов Раскраска вершин Пусть Г (V,E,Ф) – граф, раскраска вершин Г в n цветов – отображение f : V {1,2,…,n } Правильная раскраска вершин графа Г – это раскраска Г, в которой смежные вершины имеют разные цвета. Хроматическое число Г ( χ(Г) ) – это минимальное количество цветов, в которые можно правильно раскрасить вершины Г

2 Раскраска ребер Пусть Г (V,E,Ф) – граф, раскраска ребер Г в n цветов – отображение g : E {1,2,…,n } Правильная раскраска ребер графа Г – это раскраска Г, в которой, ни из какой вершины не выходит два одноцветных ребра. Реберное хроматическое число Г ( χ(Г) ) – это минимальное количество цветов, в которые можно правильно раскрасить ребра Г

3 Хроматическое число Свойства хроматического числа V(Г) – количество вершин в Г α(Г) – число независимости графа Г ω(Г) – кликовое число графа Г 1)χ(Г) ω(Г) 2)χ(Г)α(Г) V(Г) Способы оценки хроматического числа 1) Теорема χ(Г) 2 в Г нет нечетных циклов

4 Δ(Г) – max степень вершины Г δ(Г) – min степень вершины Г 2) Утверждение χ (Г) Δ(Г) + 1 3) Теорема Пусть d 3, Г – связный граф, не К d + 1, Δ(Г) d, тогда χ(Г) d Реберное хроматическое число Утверждение χ(Г) Δ(Г) Теорема χ(Г) Δ(Г) + 1

5 Покрывающая раскраска ребер – это покраска ребер, такая, что ребра каждого цвета покрывают все вершины Утверждение Количество цветов в покрывающей раскраске не больше δ(Г) Теорема Существует покрывающая раскраска графа в которой δ(Г) – 1 цветов В двудольном графе Г χ(Г) = Δ(Г) и существует покрывающая раскраска в δ(Г) цветов

6 Совершенные графы Совершенный граф Г – это граф, для которого в любом индуцированном подграфе Н χ(Н) = ω(Н) Слабая гипотеза Бержа Граф Г совершенный совершенный Сильная гипотеза Бержа Граф Г совершенный ни Г ни не содержит нечетный цикл в качестве индуцированного подграфа

7 Раскраска графа по степеням вершин Алгоритм 1. Упорядочить вершины по степеням начиная с наибольшей степени вершины. 2. Задать начальное значение счетчика k=1. 3. Первую вершину окрашиваем в цвет k и заносим в букет B(k). 4. Просматриваем следующую неокрашенную вершину, если она несмежная с вершинами букета B(k) то окрашиваем ее в цвет k, иначе пропускаем. 5. Проверяем количество просмотренных вершин, если i n (i- номер текущей вершины), то возврат в п.4, иначе k=k+1 и просмотр списка начинается заново исключая окрашенные вершины. 6. Проверка на окончание поиска: если неокрашенных вершин не осталось, то конец поиска, иначе п.5.

8 Пример: задан граф Вершина v i Степень B(1)B(2)B(3)B(4) Цвет 1234 Раскрасить по степеням вершин Составим таблицу:

9 Раскраска графа с использованием независимого множества вершин Алгоритм определения независимого множества S 1. Выбирается начальная вершина v 0 и заносится в S. 2. Рассматривается следующая вершина v i, если v i несмежная с S, то она включается в S, иначе не включается. 3. Проверка на окончание: если просмотрены все вершины, то – конец, иначе п.2. Алгоритм раскраски с использованием независимого множества вершин Рассмотрим следующую схему рекурсивной процедуры Р: 1. Выбрать в графе G некоторое максимальное независимое множество вершин S max. 2. Окрасить вершины множества S max в очередной цвет. 3. Применить процедуру Р к графу G\ S max.

10 Пример: задан граф Раскрасить с использованием независимых множеств вершин Определим S max S max1 ={1,3,7} – 1 цвет S max2 ={4,9} – 2 цвет S max3 ={5,8} – 3 цвет S max4 ={2,6} – 4 цвет