pro.algorithms
Рёберная раскраска (дерева) — назначение «цветов» рёбрам графа (дерева) таким
образом, что никакие два смежных ребра не имеют один и тот же цвет.
Что такое раскрасить краской - это по сути как покрасить в белый (краска присутствует) и черный цвет (краска отсутствует).
Что такое раскрасить двумя красками - это как покрасить в 2 * 2 = 4 разных цвета?
3 ответов
кажется так можно покрасить только пути
Тут зависит от числа ребер от одной вершины, та же теорема, что вроде 3 цвета достаточно для покраски плоскости эта по сути ваша задача
https://ru.m.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D1%87%D0%B5%D1%82%D1%8B%D1%80%D1%91%D1%85_%D0%BA%D1%80%D0%B0%D1%81%D0%BA%D0%B0%D1%85
Похожие вопросы
Обсуждают сегодня