какая-то теория / раскраски графов
.pdfДИСКРЕТНАЯ МАТЕМАТИКА
ГРУППЫ 1/42, 1/147, 1/184
Ксенофонтова Ольга Леонидовна
ТЕОРИЯ ГРАФОВ
РАСКРАСКИ ГРАФОВ
лекция
Раскраски графов
Пусть дан неориентированный граф G = (V, E). Раскраской графа G в k цветов или k -раскраской называется разбиение элементов графа на k классов.
Рассматривают раскраски вершин и ребер, а также раскраски граней плоских карт.
Правильная раскраска
Вершинной раскраской графа называет-
ся приписывание цветов (натуральных чисел)
его вершинам.
Раскраска называется правильной, если никакие две смежные вершины не получают одинаковый цвет (то есть смежным вершинам приписываются различные натуральные числа).
Правильная раскраска
Граф, для которого существует правильная k -раскраска, называется k -раскрашиваемым
или раскрашиваемым k цветами.
Пример
Рассмотрим граф. Натуральными числами 1, 2, 3 и 4 обозначены краски вершин.
Приведенная раскраска является правильной.
Раскрасить правильно данный
граф меньшим числом нельзя,
поэтому хроматическое число графа
Задачи, сводящиеся к правильной раскраске графов
Задачи, сводящиеся к правильной раскраске графов
Задачи, сводящиеся к правильной раскраске графов
Алгоритм построения правильной раскраски