12. Раскраска графа

Под раскраской графа понимается приписывание цветов вершинам или рёбрам графа, обладающее определёнными свойствами.

Далее рассматривается вершинная раскраска графа.

Определение. Правильной называется такая раскраска вершин графа, при которой Смежные вершины окрашиваются в Разные цвета.

Определение. Хроматическим числом графа называется наименьшее число цветов для его правильной раскраски.

Раскраска вершин графа в различных цветов является Отображением множества его вершин во множество , в котором каждый элемент интерпретируется как цвет вершины. Это отображение не обязательно является взаимно-однозначным, поэтому при правильной раскраске графа возможно использование Менее цветов. Правильная раскраска является разбиением множества вершин на одноцветные классы – подмножества вершин, покрашенных в один цвет.

Теорема 19. Если , то -раскраска графа существует.

Теорема 20. Для любого графа , имеющего -рас­крас­ку, выполняются следующие свойства:

1) число одноцветных классов не превосходит ;

2) никакие две вершины в одноцветном классе не являются смежными.

В дискретной математике общей формулы для вычисления не существует.

Самая простая оценка формулируется для графа, степени всех вершин которого известны. Обозначим наибольшую степень вершин графа .

Теорема 21. Для любого графа выполняется неравенство .

Например, хроматическое число графа, диаграмма которого представлена на рис. 1, равно трем. Раскраска вершин этого графа в три различных цвета определяется отображением и представлена на рис. 19. Это отображение является разбиением множества на три класса одноцвет­ности: , , .

Рис. 19. Раскраска графа

Теорема 22.

1) .

2) .

3) .

4) .

Теорема 23. Всякий планарный граф можно правильно раскрасить пятью красками.

Задачи и упражнения

49. Найдите хроматические числа графов и задачи 1.

50. Вычислите хроматическое число графа Петерсена.

51. Найдите классы одноцветности графа задачи о трех домах и трех колодцах.

52. Найдите классы одноцветности простого цикла с четырьмя вершинами.

53. Найдите классы одноцветности простого цикла с пятью вершинами.