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

Теорема Кенига 
Непустой граф является бихроматическим тогда и только тогда, когда 
он не содержит циклов нечетной длины. 
Следствие 1.
Любое дерево бихроматично. 
Следствие 2.
Любой двудольный граф бихроматичен. 
5.7.2. П
РИБЛИЖЕННЫЕ АЛГОРИТМЫ РАСКРАСКИ ГРАФА
 
Задачи о поиске хроматического числа является NP-сложной, т. е. не 
существует эффективных полиномиальных алгоритмов. Рассмотрим не-
сколько приближенных алгоритмов. 
5.7.2.1. Алгоритм последовательной раскраски вершин.
Это субоптимальный, приближенный алгоритм, который дает раскрас-
ку, близкую к минимуму. 
1.
Произвольной вершине графа G приписываем цвет 1. 
2.
Пусть раскрашены i вершин графа G в цвета от 1 до i, где 
i 
≥ l. Произвольной неокрашенной вершине v
i + 1
приписыва-
ем минимальный цвет неиспользованной при раскраске 
смежных вершин. 
Алгоритм последовательной раскраски зависит от способа перебора 
вершин. 
На рисунке 5.17 приведен пример правильной раскраски, если последо-
вательность такова: (A, B, G, D, C, F). 
2
2
1
1
3
4
A
B
C
F
D
G
Рис. 5.17. Последовательность (A, B, G, D, C, F) 
1 / 23

---

186 
Этот же граф может быть раскрашен иначе (рис. 5.18). 
3
2
1
1
3
2
A
B
C
F
D
G
Рис. 5.18. Последовательность (A, B, D, C, F, G) 
5.7.2.2. Алгоритм упорядочивания вершин 
Этот алгоритм последовательной раскраски основан на методе упоря-
дочивания вершин «наибольшие – первыми» или «наименьшие – первыми». 
Метод «наибольшие – первыми» состоит в следующем. Упорядочиваем 
вершины графа G в порядке невозрастания их степеней. Если две вершины 
имеют одинаковые степени, то вычисляем двушаговые степени вершины v
i
как число маршрутов длины 2, исходящих из этой вершины. 
В методе «наименьшие – первыми» сначала выбираем в исходном гра-
фе вершину с наименьшей степенью и присваиваем ей номер p. Удаляем эту 
вершину со всеми инцидентными ей ребрами. В полученном графе находим 
вершину с наименьшей степенью и присваиваем ей номер p 
− 1 и т. д. 
На рисунке 5.19 показан пример раскраски по методу «наибольшие – 
первыми». 
3
2
2
1
3
A
B
C
F
D
G
Рис. 5.19. Раскраска по методу «наибольшие – первыми»: (D, A, B, C, E, F)
На рисунке 5.20 показан пример раскраски того же графа по методу 
«наименьшие – первыми» 
2 / 23

---

187 
A
B
C
F
D
G
Рис. 5.20. Раскраска по методу «наименьшие – первыми»: (D, C, E, B, A, F) 
Опишем алгоритм решения по шагам: 
1.
Вычислить степени вершин и отсортировать их в порядке не-
возрастания их степеней. Положить K = 0. 
2.
Просмотреть вершины в порядке невозрастания степеней и 
окрасить первую неокрашенную вершину в цвет номер K. 
3.
Просмотреть вершины в порядке невозрастания степеней и 
окрасить в цвет номер K все вершины, которые несмежны 
вершинам, уже окрашенным в цвет номер K. 
4.
Если все вершины окрашены, то K — искомое хроматическое 
число. Иначе K = K + 1 и переход к пункту 2. 
Число использованных цветов будет приближенным значением хрома-
тического числа графа. 
Для реализации алгоритма требуется упорядочить вершины в порядке 
невозрастания степеней. Эта сортировка реализована для простоты пузырь-
ковым способом, но при сортировке переставляются не сами вершины, а эле-
менты вспомогательного массива V, в котором содержатся номера следова-
ния вершин (листинг 5.37).