ПРИКЛАДНАЯ ИНФОРМАТИКА № 1 (43) 2013 Т. А. Панюкова, канд. физ.-мат. наук, доцент Южно-Уральского государственного университета, г. Челябинск И. О. <...> Алферов, студент Южно-Уральского государственного университета, г. Челябинск Маршруты с локальными ограничениями: 1 алгоритмы и программная реализация Методы теории графов находят широкое применение в множестве приложений. <...> Примером практически востребованной задачи может служить задача построения в графе пути с заданными свойствами. <...> При построении систем управления манипуляторами с помощью неориентированного графа отображают всевозможные элементы его траектории и решают задачи построения маршрутов, удовлетворяющих различным ограничениям, например: прямолинейных маршрутов [2]; маршрутов, в которых следующее ребро определяется заданным циклическим порядком на множестве ребер, инцидентных текущей вершине [3–5]; маршрутов, в которых часть ребер следует пройти в заданном порядке [5]. <...> 1 Ограничения на порядок обхода вершин З и ребер графа можно классифицировать: • на локальные, когда следующее ребро в маршруте определяется условиями, заданными в текущей вершине или на текущем ребре [2–5, 6–8]; 1 Работа выполнена при поддержке Министерства образования и науки РФ, соглашение 14. <...> Инструментальные средства адачи нахождения маршрутов на графах, удовлетворяющих определенным ограничениям, вызываются кон• глобальные (эйлеровы, гамильтоновы циклы, бинаправленные двойные обходы [4, 5] и т. д. <...> ). Большинство работ посвящено алгоритмам с локальными ограничениями на порядок обхода ребер. <...> В данной статье рассмотрена задача покрытия графа минимальным числом цепей, удовлетворяющих заданным локальным ограничениям в каждой вершине [9]. <...> Алгоритм построения допустимой цепи Обобщение большинства частных случаев задачи построения простой цепи с локальными ограничениями и анализ вычислительной сложности этой проблемы даны С. <...> Для вершины vV G∈ () определим множество EG (v <...>