КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Обложка Макаровских Т.А. Маршруты-покрытия специального вида в графах: Теоретические основы и применение в ресурсосберегающих технологиях
Id: 235996
 
539 руб.

Маршруты-покрытия специального вида в графах: Теоретические основы и применение в ресурсосберегающих технологиях

URSS. 2018. 216 с. Твердый переплет. ISBN 978-5-9710-5352-1.

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

Издание может быть полезно студентам старших курсов, магистрантам и аспирантам, изучающим углубленные курсы по теории графов.


Оглавление
Предисловие5
Введение9
Глава 1.Введение в маршрутизацию на графах21
 1.1.Основные понятия и определения 22
 1.2.Маршруты в графах25
 1.3.Экскурс в историю. Задача о Кенигсбергских мостах26
 1.4.Разложения графов на цепи37
 1.5.Алгоритмы построения эйлеровых циклов без ограничений на порядок обхода ребер39
Глава 2.Маршруты с локальными ограничениями46
 2.1.Алгоритм построения допустимой цепи46
 2.2.Алгоритм построения допустимой эйлеровой цепи52
 2.3.Покрытие графа допустимыми цепями60
Глава 3.Маршруты с упорядоченным охватыванием63
 3.1.Построение OE-циклов для плоского эйлерова графа66
 3.2.Ранжирование ребер, вершин и граней88
 3.3.Эффективные алгоритмы построения OE-маршрута в произвольном связном плоском графе91
 3.4.Построение OE-покрытия для несвязного графа121
Глава 4.Построение OE-маршрутов с локальными ограничениями135
 4.1.О существовании системы переходов, допускающей AOE-цепь137
 4.2.Алгоритм построения AOE-цепи138
 4.3.Программная реализация алгоритма построения AOE-цепи146
 4.4.Класс самонепересекающихся OE-цепей150
 4.5.О числе эйлеровых OE-цепей для заданной системы переходов154
Глава 5.Применение алгоритмов маршрутизации в САПР технологической подготовки процессов раскроя166
 5.1.Особенности и различия составления планов раскроя для различных технологий172
 5.2.Абстрагирование раскройного плана до плоского графа174
 5.3.Абстрагирование технологических ограничений175
 5.4.Ранжирование ребер плоского графа178
 5.5.Добавление дополнительных ребер и построение маршрута179
 5.6.Задача прямоугольного раскроя и OE-покрытия181
Заключение188
Литература190

Об авторе
Макаровских Татьяна Анатольевна
Кандидат физико-математических наук, доцент кафедры «Экономико-математические методы и статистика» Южно-Уральского государственного университета. В 2003 г. окончила ЮУрГУ по специальности «Прикладная математика». В 2006 г. защитила кандидатскую диссертацию по специальности «Теоретические основы информатики» в Вычислительном центре имени А. А. Дородницына РАН. Является автором более 50 научных публикаций (в том числе 8 книг) и разработчиком пяти зарегистрированных программ для ЭВМ.