Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

5.7. К
ОМБИНАТОРНЫЕ ЗАДАЧИ НА ГРАФАХ
 
5.7.1. М
ИНИМАЛЬНАЯ РАСКРАСКА ГРАФА
 
Задача о раскраске графа, как уже говорилось выше, связана с разбие-
нием множества вершин графа на подмножества. Свойство вершин, поло-
женное в основу такого разбиения, условно называют цветом. Соотвествен-
но, k-раскраской графа G называется произвольная функция f, отображающая 
множество вершин графа G в некоторое множество A из k элементов: 
f : V → A = {a
1
, a
2
, ... , a
k
}. 
22 / 23

---

184 
В качестве элементов множества A обычно используют отрезок нату-
рального ряда {1, 2, ... , k}. Если f(u) 
≠ f(v) для любых смежных вершин u и v 
графа, то раскраска называется правильной. Иначе говоря, концевые верши-
ны любого ребра должны быть окрашены в разные цвета. Граф, для которого 
существует правильная k-раскраска, называется k-раскрашиваемым. 
В графе на рисунке 5.15, состоящего из пяти узлов, для закраски ис-
пользовалось пять красок с номерами от 1 до 5. 
1
2
4
5
3
A
B
C
D
E
Рис. 5.15. 5-раскрашиваемый граф (раскраска правильная) 
На рисунке 5.16 для правильной раскраски того же графа потребова-
лось три краски. 
1
2
1
1
3
A
B
C
D
E
Рис. 5.16. 3-раскрашиваемый граф (правильная раскраска) 
Минимальное число красок, обеспечивающее правильную раскраску 
графа, называется его хроматическим числом, а соответствующий граф на-
зывается k-хроматическим (используемое обозначение λ(G) = k). 
Правильную k-раскраску графа G можно рассматривать как разбиение 
множества вершин графа G на не более чем k непустых множеств, которые 
называются цветными классами: 
V = V
1
U ... V
k
. 
23 / 23

---

185 
Каждый цветной класс является независимым множеством. Для полно-
го графа хроматическое число равно числу его вершин. Очевидно, что для 
цикла с четным числом вершин хроматическое число равно двум, а для цикла 
с нечетным числом вершин – трем. Для пустого цикла это число полагают 
равным единице. Граф с хроматическим числом, равным двум, называется 
бихроматическим.