Маршруты с локальными ограничениями

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