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

Аннотация

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