Развернутый пример решения

В качестве примера возьмём граф, представленный на рисунке 2:

Рисунок 2.

Цвета обозначим:

красный: 1,.

зеленый: 2,.

синий: 3.

Неявный перебор

• 1. Раскрашиваем вершины по порядку в минимально возможные цвета: 1 -красный, 2 — зеленый, 3 — зеленый, 4 — красный, 5 — синий.
• 2. Вершина номер 5 имеет максимальный цвет (с номером 3). Попытаемся от него избавиться: делаем шаг возвращения из вершины 5.
• 3. Смежная вершина с максимальным номером, которая меньше 5 — это 3. Перекрасить ее в цвет больший ее (2) и меньший, чем максимальный (3) — нельзя. Делаем шаг возвращения из вершины 3.
• 4. Смежная вершина с максимальным номером, которая меньше 3 — это 1. Мы достигли первой вершины и завершаем алгоритм.

Эвристический метод.

• 1. Сортируем вершины по степени: 1, 3, 2, 4, 5.
• 2. Окрашиваем в первый цвет (красный). Мы можем окрасить вершины 1. Вершины 2 и 3 окрасить нельзя, поскольку они смежные с 1. Вершина 4 не

инцидентна, так что может быть окрашена в красный. Смежную с первой вершину 5 окрасить нельзя.

• 3. Сортируем вершины по количеству смежных неокрашенных вершин: 3, 2, 5.
• 4. Выбираем следующий цвет — зеленый. Мы можем окрасить в него вершины 2 и 3.
• 5. Сортируем вершины по количеству смежных неокрашенных вершин: остаётся только 5.
• 6. Выбираем следующий цвет — синий (3).
• 7. Окрашиваем последнюю вершину 5 в синий цвет.