Smallest Last

Ссылки сюда (1) →

Алгоритм для задачи раскраски графа.

Пусть у нас есть граф G=(V,E). Сначала определим нумерацию вершин, построим ее с конца в начало:

• Последняя вершина — вершина с минимальной степенью.
• Предпоследняя вершина — вершина с минимальной степенью в графе G без вершины

…

• Вершина — вершина с минимальной степенью в графе G без вершин
• Вершина — та, что осталась.

Затем берем и последовательно красим вершины.

• Если к i-й вершине мы использовали только k красок, пробуем
  • покрасить вершину в краску с минимальным номером из этих
  • это невозможно (вершина степени k, и все предыдущие раскрашены в разные цвета) — вводим новый цвет, k+1

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.