@VerNika

Как реализовать точный алгоритм правильной раскраски рёбер графа?

Нужно найти хроматический индекс графа. Пока реализовала только неточный алгоритм путем поиска степеней вершин графа, последовательного выбора вершины с максимальной степенью и раскраски инцидентных рёбер выбранной вершины в разные цвета, пока есть ещё неокрашенные.

На то он и не точный, что выдаёт только максимально приближенный хроматический индекс.
Вот пример его ошибки, раскрашивает 5-ю цветами:
45db7c9321764f0185d6c250a2b45cef.png
Хотя можно 4-мя:
cec055bf4010476b86a53a780e695076.png

Как реализовать точный алгоритм правильной раскраски рёбер графа? Бить в лоб перебором всех окрасок - не вариант. Нужно что-то побыстрей и алгоритмичней. У самой идей нет, вернее были, но они тоже являются неточными. Пробовала гуглить, для раскраски ребёр ничего нормального не находила, только для раскраски вершин.
  • Вопрос задан
  • 2314 просмотров
Решения вопроса 1
@nirvimel
Существуют алгоритмы полиномиального времени, создающие оптимальную раскраску двудольных графов и раскраску простого не двудольного графа с числом цветов {\Delta}+1.

Однако, в общем случае, задача поиска оптимальной рёберной раскраски NP-полна и самый быстрый из известных алгоритмов для неё работает за экспоненциальное время.

Рёберная раскраска

Итак, можно найти раскраску в Delta + 1 цветов за полиномиальное время (что тоже может оказаться совсем не быстро). Но чтобы доказать, что не существует раскраски (иначе, найти ее) ровно в Delta цветов, необходимо решить NP-полную задачу за экспоненциальное время.
(Delta - максимальная степень вершины).
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы