Smallest Last

Материал из DISCOPAL
Перейти к: навигация, поиск

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

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

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

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

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

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

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

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

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