#graph #graph-coloring
Вопрос:
Я узнал от Google, что у плоского графика есть полиномиальный алгоритм для задачи раскраски 4-цветного графика.
Есть ли способ преобразовать один график в плоский график без потери достижимости между любыми двумя узлами?
Комментарии:
1. Является ли график направленным или неориентированным? Если он неориентирован, это можно легко сделать, найдя связующее дерево (и вы можете раскрасить его в 2 цвета); если он направлен, эквивалентного плоского графика может не существовать.