Дан список ребер ациклического неориентированного графа. Необходимо найти оптимальную раскраску (т.е. использовать минимальное количество цветов) ребер графа такую, чтобы никакие два смежных ребра не имели один и тот же цвет. Подскажите оптимальный или эффективный алгоритм для решения.
1 ответ
Мое решение (низкая эффективность): Заводим массив множеств, который будут содержать цвета ребер соответствующих вершин. Для каждого ребра проходим в цикле от 1 до максимальной степени графа, если видим, что вершину можно покрасить в i-ый цвет, то красим, сразу выводим результат и выходим из цикла.