Smallest Last

Материал из DISCOPAL
Версия от 12:04, 9 декабря 2017; StasFomin (обсуждение | вклад) (Новая страница: «Алгоритм для задачи [https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D0%BA%D1%80%D0%B0%D1%81%D0%BA%D0%B0_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 р…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

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

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

…

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

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

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

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

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

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

Источник — «https://discopal.ispras.ru/index.php?title=Smallest_Last&oldid=6489»