автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Построение маршрутов с ограничениями на порядок обхода ребер в плоских графах: алгоритмы и программное обеспечение

На правах рукописи

Макаровских Татьяна Анатольевна

ПОСТРОЕНИЕ МАРШРУТОВ С ОГРАНИЧЕНИЯМИ НА ПОРЯДОК ОБХОДА РЕБЕР В ПЛОСКИХ

ГРАФАХ:

АЛГОРИТМЫ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ

05.13.17 - Теоретические основы информатики

1 8 МАР 2015

Автореферат диссертации на соискание учёной степени доктора физико-математических наук

Челябинск - 2015

005560550

005560550

Работа выполнена на кафедре экономико-математических методов и статистики ФГБОУ ВПО «Южно-Уральский государственный университет» (Национальный исследовательский университет).

Официальные оппоненты: БРОНШТЕЙН Ефим Михайлович,

доктор физико-математических наук, профессор, профессор кафедры вычислительной математики и кибернетики, ФГБОУ ВПО Уфимский государственный авиационный технический университет

КАРТАХ Вадим Михайлович,

доктор физико-математических наук,

профессор, заведующий кафедрой

прикладной информатики,

ФГБОУ ВПО Башкирский государственный

педагогический университет им. Акмуллы

КИПНИС Михаил Мордкович,

доктор физико-математических наук,

профессор, профессор кафедры

математического анализа,

ФГБОУ ВПО Челябинский государственный

педагогический университет

Ведущая организация - ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина»

Защита диссертации состоится 27 мая 2015 г., в 12:00 часов, на заседании диссертационного совета Д 212.298.18 при Южно-Уральском государственном университете по адресу: 454080, г. Челябинск, пр. им. В.И. Ленина, 70.

С диссертацией можно ознакомиться в библиотеке Южно-Уральского государственного университета и на сайте:

http://susu.ac.ru/ru/dissertation/d-21229818/niakarovskih-tatyana-anatolevna.

Автореферат разослан « ж» 2015 г.

Учёный секретарь диссертационного совета

кандидат физико-математических наук, доцент Цымблер М.Л.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

Одной из работ по специальным вопросам эйлеровых графов является монография Г. Фляйшнера «Эйлеровы графы и смежные вопросы», где систематизировано и достаточно подробно рассмотрены некоторые виды эйлеровых цепей, например, цепи, не содержащие запрещенных переходов, попарно-совместимые эйлеровы цепи, А-цепи в графах.

Имеется ряд журнальных публикаций других авторов, в которых также рассматриваются задачи, посвященные эйлеровым цепям специального вида, например, расширение класса запрещенных переходов (статья С. Зейдера), самонепересекающиеся и непересекающиеся цепи, бинаправленные двойные обходы (монография Г. Фляйшнера и прочие его статьи), маршруты Петри, прямолинейные маршруты, реберно-упорядоченные маршруты и т.д.

Интерес к задачам маршрутизации объясняется их использованием в качестве математических моделей многих проблем управления и автоматизации проектирования.

Например, необходимость линейного упорядочения вершин параллельно-последовательных графов возникает в задаче размещения объектов с учетом связей между ними (например, проектирование расположения технологического оборудования нефтехимического предприятия). Технологическая схема производства задает порядок обработки сырья. Требуется разместить единицы оборудования таким образом, чтобы суммарная стоимость трубопроводных связей была минимальной (работы Забудского Г.Г.). Для планирования и оперативного управления выбора маршрута доставки решается задача, основанная на представлении совокупности типовых состояний системы в виде узлов графа, переходы которого соответствуют управляющим решениям нечеткой ситуационной сети (статьи Фараонова A.B.). Математическая модель выбора оптимального маршрута между различными объектами, фиксированными как вершины ориентированного графа, вообще, является одной из самых исследуемых областей (например, работы Моргунова И.В. и др.). На основе автоматического построения обхода графа возможно исследование эффективности генерации тестов. Здесь необходимо построение маршрута, проходящего через все дуги графа (исследования Арутюняна А.Р). С помощью модифицированного метода Дейкс-тры удается построить оптимальные маршруты в беспроводных эпизодических

сетях. Для поиска эффективных и полуэффективных решений на графах с векторными весами ребер используется метод сверток. В качестве ограничений применены критерий общей загрузки сети, показатель относительной нагрузки на канал и длина маршрута (работа Кулакова Ю.О. и Воротникова В.В.). Для решения задачи маршрутизации при распределении пассажирских и транспортных потоков, учитывающей специфику перемещений пассажиров в крупных городах, необходимо правильно описать поведение пассажира при выборе им пути следования. На его поведение оказывает влияние множество факторов. Для обеспечения единого информационного простанства задач предлагается использовать специальный граф, который представляет собой систему всех возможных перемещений в пределах города или граф путей сообщения (представляющего собой объединение подграфов, соответствующих картам метрополитена, железной дороги, пеших перемещений, автомобильных дорог и пр.). Все дуги данного графа обладают конечным жизненным циклом: каждый элемент графа характеризует момент создания и момент пометки на удаление. Такая организация хранения данных предоставляет возможность отслеживать изменения городской ситуации и генерировать варианты срезов ситуации на расчетный период времени (работы Баламирзоева А.Г. и Султанахмедова М.А.).

Целями диссертационной работы являются:

• постановка и исследование задач маршрутизации специального вида в плоских графах, являющихся математическими моделями задач управления и проектирования;

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

В соответствии с поставленной целью в диссертационной работе решаются следующие задачи:

• Классификация существующих задач маршрутизации и методов их решения.

• Формальная постановка ряда прикладных задач, требующих построения маршрутов специального вида.

• Анализ полученных задач, разработка алгоритмов их решения для всех возможных ситуаций, анализ разработанных алгоритмов.

• Программная реализация разработанных алгоритмов.

Основными объектами исследования являются: плоский граф; методика построения маршрута, в котором цикл из пройденных ребер не охватывает еще непройденных.

Методами исследования являются: алгоритмические методы, теория графов, анализ алгоритмов, программирование, тестирование разработанных программных средств.

Научная новизна полученных в диссертации результатов заключается в следующем.

• Введен класс ОЕ маршрутов в плоских графах. Маршруты введенного класса удовлетворяют требованию отсутствия пересечения внутренних граней пройденной части маршрута с ребрами его непройденной части.

• Доказано, что плоские эйлеровы графы имеют эйлеровы циклы, принадлежащие классу ОЕ.

• Введен класс АОЕ маршрутов в плоских графах. Маршруты введенного класса, как и в классе ОЕ удовлетворяют требованию отсутствия пересечения внутренних граней пройденной части маршрута с ребрами его непройденной части, но на них наложено дополнительное локальное ограничение: следующее ребро определяется заданным циклическим порядком на множестве ребер, инцидентных текущей вершине (т.е. построенная цепь является Л-цепью).

• Разработаны эффективные алгоритмы нахождения в плоском графе G = (V, Е) эйлеровых покрытий введенных классов, имеющие полиномиальную вычислительную сложность. Данные алгоритмы позволяют минимизировать длину дополнительных построений между концевыми вершинами цепей, принадлежащих построенным покрытиям.

• Определены оценки количества 0£-цепей для фиксированной системы переходов (последовательности обхода ребер).

Теоретическая значимость. Полученные теоретические результаты являются продолжением ряда исследований Г. Фляйшнера, В.А. Верхотурова, Э.А. Мухачевой, A.A. Петунина и позволяют решать задачу построения маршрутов специального вида. Рассмотренный метод решения расширяет раздел теории графов, связанный с построением маршрутов со специальными ограничениями в плоских графах. Решение задачи осуществляется за полиномиальное время.

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

Работа выполнялась в соответствии с планами госбюджетных НИР ЮУр-ГУ (номер гос. регистрации 01.2001 05137). Работа поддерживалась грантами РФФИ «Урал» (проекты 01-01-96401, 10-07-96002-р_урал_а), Грантом Президента РФ МК-2603.2008.9, Губернаторским грантом Челябинской области р2001урчел-01-04 и грантами губернатора Челябинской области для студентов, аспирантов и молодых ученых в 2002, 2003, 2013 гг. Часть работы выполнялась

в рамках соглашения № 14.В37.21.0395 с Министерством образования и науки Российской Федерации от 06 августа 2012 года.

Разработанное программное обеспечение позволяет получить решения поставленной задачи для произвольного плоского графа, соответствующему заданному на листе раскройному плану. Правообладателем разработанного в рамках данной модели комплекса программ является ФГБОУ ВПО ЮУрГУ (НИУ).

Новизна и результативность предложенных алгоритмов подтверждены свидетельствами о регистрации программ.

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

1. Российская молодежная инженерная выставка «Шаг в будущее», Москва, МГТУ им. Н.Э. Баумана, 9-13 марта, 1999 г.

2. XII Международная конференция «Проблемы теоретической кибернетики», Нижний Новгород, МГУ им.М.В. Ломоносова, Институт прикладной математики им.М.В. Келдыша РАН, ННГУ им. Н.И. Лобачевского, 17-22 мая, 1999 г.

3. XI Соревнование молодых ученых Европейского Союза, Греция, 19-26 сентября, 1999 г.

4. VII Международный семинар «Дискретная математика и ее приложения», Москва, МГУ им. М.В. Ломоносова, 29 января - 2 февраля, 2001 г.

5. Второй международный конгресс студентов, аспирантов и молодых ученых «Молодежь и наука - третье тысячелетие», Москва, МГТУ им. Н.Э. Баумана, 15-19 апреля, 2002 г.

6. XIII Международная конференция «Проблемы теоретической кибернетики», Казань МГУ им. М.В. Ломоносова, Институт прикладной математики им.М.В.Келдыша РАН, ННГУ им. Н.И. Лобачевского, КГУ, 27-31 мая, 2002 г.

7. Российская конференция «Дискретный анализ и исследование операций», Новосибирск, Институт математики им. С.Л. Соболева СО РАН, 24-28 июня, 2002 г.

8. Всероссийская конференция «Проблемы оптимизации и экономические приложения», Омск, Омский филиал института математики СО РАН, 1-5 июля, 2003 г.

9. The International Workshop on Computer Science and Information Technologies' 2003, Уфа, УГАТУ, 16-18 сентября, 2003 г.

10. VIII Международный семинар «Дискретная математика и ее приложения», Москва, МГУ им. М.В. Ломоносова, 2-6 февраля, 2004 г.

11. Российская конференция «Дискретный анализ и исследование операций», Новосибирск, Институт математики им. С.Л. Соболева СО РАН, 28 июня -2 июля, 2004 г.

12. Молодежная конференция «Проблемы теоретической и прикладной математики», Екатеринбург, PIMM, УрО РАН, 2005-2009 гг.

13. Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications. Prague, Charles University, 2006.

14. 6-th International Congress on Industrial and Applied Mathematics, Zurich, 16-20 July, 2007.

15. International meeting «Euler and Modern Combinatorics», St. Petersburg, June 1-7, 2007.

16. Международная научная конференция «Информационно-математические технологии в экономике, технике и образовании», Екатеринбург, УГТУ-УПИ, 2007-2008 гг.

17. Научно-практическая конференция «Обратные задачи в приложениях», Бирск, БирГСПА, 2008.

18. The International Workshop on Computer Science and Information Technologies - 2008, Turkey, Antalya, September 15-17, 2008.

19. X Белорусская математическая конференция, Минск, Институт математики HAH Беларуси, 3-7 ноября 2008 г.

20. 13-th IFAC Symposium on Information Control Problems in Manufacturing, Moscow, 2009.

21. IV Всероссийская конференция «Проблемы оптимизации и экономические приложения»: Материалы конференции (Омск, 29 июня — 4 июля, 2009).

22. Международная научная конференция «Дискретная математика, алгебра и их приложения», Минск, Институт математики HAH Беларуси, 19-22 октября, 2009 г.

23. X Международный семинар «Дискретная математика и ее приложения» (Москва, МГУ им. М.В. Ломоносова, 1-6 февраля, 2010 г.).

24. Российская конференция «Дискретная оптимизация и исследование операций» (Алтай, 27 июня - 3 июля, 2010).

25. 8th French Combinatorial Conference, Orsay, France (June,28-July,2, 2010).

26. Workshop on Computer Science and Information Technologies (CSIT'2010), Russia, Moscow - St.Petersburg, September 13-19, 2010.

27. XIV Всероссийская конференция «Математическое программирование и приложения», Екатеринбург, 2011.

28. 13-th International Workshop on Computer Science and Information Technologies, Garmish-Partenkirchen, Germany, September,26-October,l, 2011.

29. Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование», Москва, МГУ им. М.В. Ломоносова, 2011-2013 гг.

30. Всероссийская конференция «Статистика. Моделирование.Оптимизация» (Челябинск, 28 ноября - 2 декабря, 2011 г.).

31. XVI Международная конференция «Проблемы теоретической кибернетики» (Нижний Новгород, 20-25 июня 2010 г.).

32. Международная конференция «Информационные технологии и системы», респ. Башкортостан, оз. Банное, 2012-2014 гг.

33. Математическое моделирование, оптимизация и информационные технологии: сборник научных трудов 3-й Международной конференции. - Кишинев. - 2012.

34. Международная конференция «Дискретная оптимизация и исследование операций», Новосибирск, 2013.

35. International Conference «Information Technologies for Intelligent Decision Making Support» (2013, May 21-25, Ufa, Russia).

36. Seventh Czech-Slovak International Symposium on Graph Theory, Combinatorics, Algorithms and Applications. Koshice, July 7-13, 2013.

37. Workshop on Computer Science and Information Technologies (CSIT'2013), Vienna-Budapest-Bratislava, Sep. 15-21, 2013.

38. 5th International conference «Optimization and Applications» (Optima-2014, Petrovac, Montenegro, Sep. 27-Oct.4, 2014).

39. 2-nd International Conference «Inteligent Technologies for Information Processing and Management», Ufa, November 10-12, 2014.

Кроме того, результаты работы были представлены на ежегодных научно-практических конференциях Южно-Уральского государственного университета.

Публикации. По теме диссертационного исследования опубликовано 75 работ, из них 4 свидетельства о государственной регистрации программ для ЭВМ, 8 статей из перечня ВАК ведущих рецензируемых изданий (работы [1-8]), 4 статьи, индексируемые в SCOPUS (работы [8-11]). Статья [11] является переводом на английский язык статьи [2]. В работах, написанных в соавторстве, А.В. Па-нюкову принадлежит изначальная общая постановка задач, Э.А. Мухачевой - обзор методов составления раскройных планов, студентам Е.А. Савицкому, В.Ф. Мирасову, И.А. Сахарову и И.О. Алферову - технические аспекты программной реализации разработанных алгоритмов, а диссертанту - все основные полученные результаты.

Структура работы и объем работы. Диссертация состоит из введения, 6 глав, заключения и списка литературы. Объем диссертации составляет 236 страниц. Список литературы содержит 115 наименований.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В первой главе на основе аналитического обзора литературы, отражающего состояние проблемы применения графов в математическом моделировании, показано место решаемой в данной работе задачи относительно ранее опубликованных в научной литературе результатов. С тем, чтобы более четко очертить круг решаемых в данной работе задач и показать их место в общей теории графов, приведна историческая справка и краткое описание постановки задачи нахождения эйлеровых (обход по всем ребрам ровно по одному разу с возвратом в исходную вершину) маршрутов. Описаны известные алгоритмы построения эйлеровых цепей: расщепляющий алгоритм, алгоритм Хирхольцера и алгоритм Такера. Отмечено, что описанные выше алгоритмы находят в графе произвольную эйлерову цепь, на которую не наложено никаких ограничений.

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

Анализ публикаций показал, что большинство работ посвящено алгоритмам с локальными ограничениями на порядок обхода ребер (например, запрещение левых поворотов; маршруты без поворотов; использование в каждой вершине графа заданного циклического порядка включения ребер в маршрут и т.п.).

Обобщение большинства частных случаев задачи построения маршрутов с локальными ограничениями дано С.Зейдером. Им предложено представлять локальные ограничения в каждой вершине v исходного графа С? в виде грфа С\е(„) возможных переходов. Множеством вершин графа являются все

ребра, инцидентные вершине и; смежные вершины графа (?£(„) соответствуют разрешенным переходам. Показано, что если все графы допустимых переходов являются полными многодольными графами либо паросочетаниями, то соответствующая задача построения допустимой простой цепи между заданными вершинами разрешима за линейное время. В противном случае данная задача является ЛАР-трудной.

В диссертационной работе рассмотрен вопрос распознавания многодолыю-сти графов а также проблема построения допустимого маршрута или

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

Среди публикаций, посвященных задачам маршрутизации с глобальными ограничениями, не удалось найти каких-либо результатов о маршрутах с запрещенными последовательностями ребер. Задача построения маршрутов в плоских графах, у которых отсутствует пересечение внутренних граней пройденной части маршрута с ребрами его непройденной части в связных и несвязных графах не рассмотрена в исследованной автором литературе, то же самое можно сказать и про задачу построения Л-цепей, в которых отсутствует пересечение внутренних граней пройденной части с ребрами непройденной части.

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

Ограничимся рассмотрением конечных простых графов. Множество вершин и множество ребер графа б будем обозначать соответственно через У(С) и £(£?). Для вершины V £ У(С) определим Ес(у), множество всех ребер графа б, инцидентных вершине V. Степень вершины V будем обозначать как с^(г>); для <1 > 0 положим ^(С) := {и £ |с^(г>) = с£}. Будем писать Н < <3, если Н - вершинно-индуцированный подграф графа (3, т.е. подграф, полученный из графа С? отбрасыванием некоторого множества вершин и всех ребер, инцидентных вершинам этого множества, и только их.

Ограничения на маршруты в графе (3 можно сформулировать в терминах графа разрешенных переходов.

Определение 1. Пусть С? - граф. Графом переходов Тс (у) вершины V 6 будем называть граф, вершинами которого являются ребра, инцидентные вершине v, т.е. У(Тд(у)) = Еа(у), а множество ребер - допустимые переходы.

Определение 2. Системой разрешенных переходов (или короче, системой переходов) Та будем называть множество {Та(у) | V £ }, где Та{у) - граф переходов в вершине V.

Определение 3. Путь Р = г>о, е\, г^,..., е*., в графе С является Та-совмес-тимым, если е^ е;+1 €Е Е(Тс(у,)) для каждого г (1 < г < /с — 1 /

Теорема 1. [С. Зейдер]. Если все графы переходов принадлежат либо классу М полных многодольных графов, либо классу Р паросочетаний, то задача построения Та-совместимой цепи является разрешимой за время 0{\Е(С)\). В противном случае данная задача является МТ3-полной.

Если система переходов вершины V 6 У(С) является паросочетанием, то задача сводится к задаче для графа

С : У(С) = У(С)\М,

Е{&) = (Е(С)\Ес(ь)) и : {„4„, е Е(Тс(у))} .

Если для любой вершины v е ^(С?) граф Тс(у) является полным многодольным графом, то цепь можно построить с помощью алгоритмаТ'с-СОВМЕСТИ-МЫЙ ПУТЬ

Отмечена связь графов переходов с понятием системы разбиения графа, используемой Г.Фляйшнером. На основе установленной связи построен алгоритм «РАЗМЕТКА» для распознавания выполнения условий теоремы С. Зейдера и алгоритм «Рс-СОВМЕСТИМЫЙ ПУТЬ» для построения допустимого пути.

Показано, что возможно распознавание системы переходов, которая позволяет решить задачу построения допустимого пути за линейное время. Сложность алгоритмов не превосходит величины 0(|.Е|), где Е - число ребер графа б. Приведены примеры использования построенных алгоритмов, рассмотрена техника программной реализации данных алгоритмов.

Заметим, что с помощью алгоритма нахождения Р^-совместимого пути возможно построение только простой цепи между двумя различными вершинами (т.е. цепь, в которой любая ее вершина встречается в ней ровно один раз).

В эйлеровом графе (3 возможно отыскание -Рс-допустимого эйлерова цикла или установление его отсутствия за время 0{\У{0)\ • |Я(С)|) с помощью разработанного алгоритма Рс-СОВМЕСТИМАЯ ЭЙЛЕРОВА ЦЕПЬ.

Алгоритм Рс-СОВМЕСТИМАЯ ЭЙЛЕРОВА ЦЕПЬ

Входные данные:

• эйлеров граф С? = (У,Е), заданный списком смежности для каждой вершины;

• система переходов РсЬ') С У{С)\ в списке смежности вершины, относящиеся к одному элементу разбиения, имеют одинаковые пометки.

Выходные данные:

• допустимый эйлеров цикл С^+ь

Шаг 1. Положить к = О, О к = С?.

Шаг 2. Найти вершину V, у которой йик{у) > 2.

Шаг 3. Найти элемент разбиения, который содержит максимальное число ребер:

• просмотреть список смежности текущей вершины и;

• посчитать число вхождений в этот список каждого элемента разбиения;

• выбрать тот элемент, который встречается чаще: получим класс С\ €

Рск(у):\С1\ = {твх\С\\СеР0к(ь)}-

Шаг 4. Выбрать ребра ех(и) £ С\ и ег(«) £ Еск(у) — Сх. По возможности выбрать ребра ех и е2, инцидентные вершинам, степень которых больше двух. Если множество Еак(у) — Сх = 0, останов: Ре-совместимой эйлеровой цепи не существует. В противном случае перейти на шаг 5.

Шаг 5. Построить граф отщепив от вершины у вершину у, которой

инцидентны только ребра ех и е2. Остальные ребра оставить инцидентными вершине у. Так как новая вершина имеет степень 2, то она не рассматривается на последующих шагах работы алгоритма.

Шаг 6. Выбрать класс С2 £ Рак(у), которому принадлежит ребро е2(у). Исключить из системы разбиения вершины у классы С\ и С2. Для этого нужно найти Р^(у) := Р(ф) - {Сх,С2}.

Для дальнейшей модификации системы разбиений выполнить следующие действия.

Шаг 6.1. Системы разбиения, в которых отсутствует вершина v, перейдут в модифицированную систему полностью без изменений.

Шаг 6.2. Если системы С\ и С2 состояли из одного ребра: |С1| = |Сг| = 1, ТО Рск+М) = Р^(у).

Шаг 6.3. Если \Сг\ > \С2\ = 1, то P¿l+» = РВк{у) и {Сх - {ех(Щ)}}.

Шаг 6.4. Если |С2| > 1, то Р^(у) = и {Сх - {е^)}, С2 - {е2(г;)}}.

Шаг 6.5. Построить

Шаг 7. Определить значение х) = 2(|£(С*;+х)| — Заметим,

что количество ребер графа остается неизменным, а количество вершин на каждой итерации увеличивается на единицу.

Шаг 8. Если ст(С&+х) > 0, положить к = к+1, перейти на шаг 2, для графа В противном случае перейти на шаг 9.

Шаг 9. Выбрать любую вершину V и пометить все вершины достижимые из данной. Если остались непомеченные вершины перейти на шаг 10, иначе останов - построенный граф (3^+1 является эйлеровой цепью, не содержащей запрещенных переходов.

Шаг 10. Из списка помеченных и не помеченных вершин графа (З^+х найти вершины ух и у2, отщепленные от одной вершины у графа (Зо и объединить их в вершину г>х,2. Получим модифицированный граф (З^+х, положим к = к + 1.

Шаг 11. Выбрать ребра ех^г) £ Сх и е2(«х,2) £ Еак{у\^) — Сх, так чтобы {еье2} ф Е(ух) и {ех,ег} ф Е(у2). Если множество Еск{у\,2) — Сх = 0, останов: Рс-совместимой эйлеровой цепи не существует. В противном случае построить граф 6^+1, отщепив от вершины у^2 вершину 1)1,2, которой инцидентны только

ребра ei и с^. Остальные ребра оставить инцидентными вершине г;^ и перейти на шаг 9.

Теорема 2. Алгоритм Рс-СОВМЕСТИМАЯ ЭЙЛЕРОВА ЦЕПЬ корректно решает задачу построения P(G)-coeMecmuMou эйлеровой цепи.

Построен алгоритм ПОКРЫТИЕ Гс-ДОПУСТИМЫМИ ЦЕПЯМИ

для нахождения эйлерова покрытия графа G допустимыми маршрутами. Алгоритм имеет вычислительную сложность ОО-Е*! • IFI).

Алгоритм ПОКРЫТИЕ Та-ДОПУСТИМЫМИ ЦЕПЯМИ

Входные данные:

• граф G — (V, Е),

• графы переходов Tq{v) Vv е V(G). Выходные данные:

• набор маршрутов Т\ i = 1,2,..., к, покрывающих граф G, где ш = 2к -число вершин нечетной степени.

Шаг 1. Пусть U = {v G V(G) : TG(v) - паросочетание}. Сделать редукцию графа G до графа G':

V(G') = V(G)\U,

E(G') = ( E(G)\ U EG(v)\ (J { U : fa"> e TG{v)}\, \ veu J Uet/ J

графы Tq{v) редуцировать до графов Tg'(v) заменой всех вхождений вершин и е U: vu,wu 6 Ета(и) вершиной w.

Шаг 2. Достроить граф G' до G* введением дополнительной вершины v*, смежной всем вершинам нечетной степени графа G'. Систему переходов Tg>{v) модифицировать до системы переходов Tq- введением для всех v £ V"(G) : deg(w) = 1 (mod 2) в граф переходов Tq-(v) вершины vv*, смежной всем вершинам в графе Tc(v).

Шаг 3. Для всех таких вершин v £ V(G), что 3р е P(v): |р| > deg(v)/2, ввести 2|р|—deg(v) дополнительных ребер (yv*)it г = 1, 2,..., 2 [р|—deg(v) в граф G*. Модифицировать граф переходов Тс-(г)) введением вершин (vv*)i, смежных всем вершинам исходного графа Тс (v) и только им.

Шаг 4. Найти в G* Т^-совместимый эйлеров цикл Т*.

Шаг 5. Построить покрытие V графа G' цепями, удалив из Т* ребра (vv').

Шаг 6. Модифицировать маршруты из Т" до маршрутов из Т добавлением вершин и £ U, удаленных на шаге 1.

Шаг 7. Останов.

Теорема 3. Алгоритм ПОКРЫТИЕ Та-ДОПУСТИМЫМИ ЦЕПЯМИ

корректно решает задачу минимального покрытия графа Тс-допустимыми цепями. Его сложность не превосходит величины О(\E(G)\ ■ |V(G)|).

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

В третьей главе поставлена и решена задача построения в плоском графе эйлеровых покрытий, удовлетворяющих условию отсутствия пересечения внутренних граней любой его начальной части с ребрами его оставшейся части. Формально такие маршруты определены как маршруты с упорядоченным охватыванием (ОЕ-маршруты).

Введены определения и обозначения теории маршрутов с упорядоченным охватыванием (ОЕ-маршрутов).

Рассмотрим плоскость S, на которой задан плоский граф G с внешней гранью /о. Для любой части графа J С G обозначим через Int(J) теоретико-множественное объединение его внутренних граней (объединение всех связных компонент S\J, не содержащих внешней грани). Тогда Int(J) можно интерпретировать как отрезанную от листа часть. Множества вершин, ребер и граней графа J будем обозначать через V(J), E(J) и F( J) соответственно, а через \М\ - число элементов множества М.

Определение 4. Цепь С = г^е^ег ... г^ в плоском графе G имеет упорядоченное охватывание (является ОЕ-цепыо), если для любой его начальной части Ci = г^е^ег • • • ei, I < (|Е|) выполнено условие Int (Ci) П Е = 0.

Так, для случая плоских эйлеровых графов доказана следующая теорема.

Теорема 4. Пусть G - плоский эйлеров граф. Для любой вершины и 6 V(G), инцидентной границе внешней (бесконечной) грани графаС, существует эйлеров ОЕ-цикл С = veivie2v2 .. ■ v\e\-iC\e\v-

Также будем говорить, что Определение 5. Последовательность реберно-непересекающихся цепей

С0 = ЛЭДе»..«, C^i/V^M-«.--

с упорядоченным охватыванием, покрывающая граф (3 и такая, что (\/то : т <п), (и^1 П (Ц^ С") = 0

является покрытием с упорядоченным охватыванием (ОЕ-покрытием).

Построение О-Б-покрытия графа б решает поставленную задачу раскроя. Здесь представленная плоскость 5 рассматривается как раскройный лист, граф й представляет раскройный план, построенный маршрут С - траекторию движения режущего инструмента, а условие принадлежности маршрута к классу ОЕ - требование, чтобы отрезанная от листа часть не требовала дополнительных разрезаний. Наибольший интерес представляют покрытия с минимальным числом цепей, поскольку переход от одной цепи к другой соответствует холостому проходу режущего инструмента.

Определение 6. Минимальную по мощности последовательность реберно-непересекающихся цепей с упорядоченным охватыванием в плоском графе С будем называть эйлеровым покрытием с упорядоченным охватыванием (эйлеровым О Е-покрытием).

В случае плоского эйлерова графа С? искомый циклический маршрут представляет эйлеров цикл. Если соответствующий граф С? не является эйлеровым и содержит 2к вершин нечетной степени, то с помощью алгоритма Листинга-Люка возможно покрыть граф к цепями.

Показано, что алгоритм построения замкнутого маршрута Р в неэйлеровом графе б является алгоритмом построения эйлерова ОЕ-цикла С в эйлеровом графе (7, представляющего модификацию графа б, в которую добавлены дополнительные ребра. Множество этих ребер будем называть Я((7).

Теорема 5. Пусть (3 = (У,Е) - плоский связный граф на 5, не имеющий висячих вершин. Существует множество ребер Р : (Р П 5)\У = 0 такое, что граф б = - эйлеров, и в графе С? существует эйлеров цикл

С = У1е1Ь2е2...е„У1, гг = |£7| -Ь- для любой начальной части которого Сг = У1е1У2е2...У1, I < |.Е| + выполнено условие 1п^С{) П Е = Ф.

Можно считать, что маршруты, которые реализуют построенное покрытие, содержат дополнительные ребра между концом текущей цепи и началом последующей.

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

Теорема 6. Пусть G = (V, Е) - плоский связный граф на S, не имеющий висячих вершин. Для любого лтожества М, являющегося паросочетанием на множестве Vadd графа G, и такого, что М : (М П5)\У = 0, существует эйлеров цикл С = VieiV2e2...enVi, п = |.Е| + \М\, для любой начальной части которого Ci = у^^еч-.^, I < + \М\, выполнено условие Int(Ci) П Е = 0 .

Таким образом, имеется возможность минимизировать длину дополнительных построений за счет построения оптимального паросочетания. Разработаны алгоритмы решения задачи для разных случаев:

• плоский эйлеров граф (алгоритм 0E-CYCLE),

• произвольный связный плоский граф (задача китайского почтальона (алгоритм СРР_0Е) и задача построения О-Е-покрытия (алгоритмы M-C0VER и OPTIMAL-COVER),

• произвольный несвязный граф (алгоритм MultiComponent). Показано, что все разработанные алгоритмы имеют полиномиальную сложность.

Доказательство теоремы 5 дает результативность приведенного ниже алгоритма OECover (алг. 1), который строит покрытие плоского графа G последова-

Algorithm 1 OECover

Require: G = (V, E) - плоский граф; Vodd - множество вершин нечетной степени; Ensure: first е Е, last 6 Е, marki : Е Е-, 1: procedure OECovER(In: G = (V,E), Vodd', Out -.first € E, last e E, markj : E -У E) 2: Initiate();

3: OrderQ; t> Сортировка списка вершин нечетной степени по убыванию ранга SortOddQ;

4: while V^u ^ 0 do

5: i>° = arg max rank(u);

veV0dd

6: Vadd = V0dd\{v0}-,

7: v = FormChain{y°);

8: Voii = lUAM;

9: end while 10: FormChain(v o); 11: end procedure

тельностью ОЕ-цепей. Здесь и в последующих алгоритмах граф G представлен списком ребер с заданными на них функциями «¿(е), h{e), fk(e), k = 1,2 (рис.1).

Алгоритм OECycle состоит из последовательного выполнения процедур Initiate, Order, и FormChainO, соответствующих трем этапам: «Инициализация», «Упорядочение» и «Формрование».

В теле процедуры Initiate присваиваются начальные значения всех используемых переменных, а также определяется ребро ео G Е, принадлежащее границе внешней грани /о-

Функциональное назначение процедуры Order состоит в:

1. определении на каждом ребре е £ Е значения rank(e) (заметим, что ранг любого ребра плоского графа может быть определен за время 0(|Е|) с помощью данной процедуры;

2. в формировании для каждой вершины списка инцидентных ребер, упорядоченных в порядке убывания значения rankQ.

После выполнения процедур Initiate и Order выполняется упорядочение вершин нечетной степени v € V0m в порядке возрастания их ранга с помощью процедуры SortOdd. За ранг вершины v принимается значение функции rank(Siacfc(u)). Далее выполняетсяцикл while... do с использованием процедуры FormChain,B которой строится последовательность из H/0dd|/2 простых цепей между парами вершин нечетной степени.

Функциональное назначение процедуры состоит в формировании ОЕ-цепи, начинающейся в заданной вершине w £ V^ и заканчивающейся в некоторой вершине v £ Vadd, v ф w. В результате выполнения процедуры будет построена простая цепь С = v0eivie2--.ekvk, в которой

vuv2,...vk-i ф Vodd, v0,vkeVodd, ei = arg max rank(e), ty+i = Щ(еЛ, i = 1,2,..., к,

e€E{v,)\{e,\l<i}

кроме того, для любой начальной части С; = v°eiVie2V2 ... е/, I < к и для любой вершины у £ V имеет место неравенство

min rank(e) > max rank(e). ее£МГЩС() ееОДХОД)

Доказательство теоремы 6 конструктивно и состоит в доказательстве результативности следующего алгоритма.

Алгоритм M-Cover

Входные данные:

• плоский граф G, представленный списком ребер с заданными на них функциями ик{е), 1к(е), Д.(е), к = 1,2;

• паросочетание М на множестве вершин нечетной степени Vcdd-

Выходные данные: Cj, j = 1,..., |К<и|/2, - покрытие графа G ОР-цепями.

Шаг 1. Выполнить процедуры «Инициализация» и «Упорядочение» как

в алгоритме OE-Cover. В результате для Vw € V будет определено значение rank(u), численно равное ее уровню вложенности. Положить j = 1. Объявить вершину Vq € /о текущей, положить Vq = vo-

Шаг 2. Выполнять построение цепи Cj с помощью процедуры «Формирование» алгоритма OE-Cover до тех пор, пока вершина v2 € Vodd не станет текущей. Если вершина v2 является тупиковой, то 3(у2,уз) € М, перейти на шаг 4. Если г>2 является транзитной - перейти на шаг 3.

Шаг 3. Если гапк(г>з) < гапк(г>2), то перейти на шаг 2 (продолжить построение цепи Cj из текущей вершины).

Шаг 4. Закончить построение текущей цепи: v{ = v2, j = j +1, V0dd = V?dd \ {^2,^3}, M = M \ {(^2,^3)} принять г^ = г>з за текущую вершину следующей цепи и перейти на шаг 2 (начать построение новой цепи Cj из вершины Vq).

Шаг 5. Останов.

Вычислительная сложность алгоритма M-Cover не превосходит величины 0(\E\-log2\V\).

Для построения оптимального покрытия (т.е. покрытия с минимальной длиной дополнительных построений) достаточно в качестве М взять кратчайшее паросочетание на множестве V0dd с помощью алгоритма OptimalCover.

Алгоритм OptimalCover

Входные данные:

• плоский граф G, представленный списком ребер с заданными на них функциями vk(e), lk(e), fk(e), к = 1,2.

Выходные данные: Cj, j = 1,..., \V„di\/2, - покрытие графа G OS-цепями.

Шаг 1. Найти кратчайшее паросочетание М на множестве V„dd-

Шаг 2. Выполнить алгоритм M-Cover для графа G и паросочетания М.

Шаг 3. Останов.

Сложность алгоритма OptimalCover не превосходит величины 0(|У|4). Данная сложность достигается за счет решения задачи поиска кратчайшего паросочетания на полном графе.

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

• компоненты связности, состоящие из ребер более высокого ранга необходимо обходить раньше компонент, состоящих из ребер более низкого ранга;

• если компоненты образуют некоторые «сообщества», в которых некоторая компонента более низкого ранга охватывает одну или несколько компонент более высокого ранга, то обход компонент, не принадлежащих сообществу осуществляется только после обхода всего сообщества.

Для решения задачи с многосвязным графом построен

Алгоритм MultiComponent

Входные данные:

плоский граф G, заданный функциями Vk(e), k(e), к — 1,2, приведенными выше.

Выходные данные: Cj, j = 1,..., |V0Cm|/2, - покрытие графа G ОЕ-цепями, s = 1,2,... - номер компоненты связности.

Шаг 1. Выявить множество S всех компонент связности графа G и для каждой компоненты связности s £ S найти уровень вложенности K(s).

Шаг 2. Построить полный абстрактный граф Т, вершинами которого являются компоненты связности S графа G, а длины ребер равны расстоянию между ближайшими вершинами компонент связности.

Шаг 3. Найти остовное дерево минимального веса Т(Т) в Т.

Шаг 4. Добавить ребра найденного остовного дерева в граф G: Gj- = G U

Т(Т).

Шаг 5. Выполнить алгоритм OptimalCover для графа Gy.

Шаг 6. Конец алгоритма.

Предложенный алгоритм строит покрытие ОЕ-цепями за полиномиальное время 0(|У|4).

Теорема 7. Если в каждой компоненте связности Gk графа G степени вершин инцидентных внешней грани графа Gk четны, то алгоритм Multi-Component строит маршрут с минимальной длиной дополнительных построений.

Рассмотренные алгоритмы реализованы в виде; компьютерных программ. Анализ сложности построенных алгоритмов показывает, что поставленную задачу можно решить за полиномиальное время.

В четвертой главе решена задача построения Л-цепей с упорядоченным охватыванием для 4-регулярного плоского графа (АОЕ-цепи).

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

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

Т = и0, ки VI,..., кп, уп, уп = у0

в графе б = (У,Е). Предположим, что в каждой вершине V £ V задан циклический порядок 0±(у), определяющий систему переходов Ад{у) С 0±(«) в этой вершине. В случае, когда б Ас (у) = 0±(у), систему переходов

Аа(у) будем называть полной системой переходов.

Определение 7. Будем называть Т А-цепъю тогда и только тогда, когда она является Ас-совместимой цепью. Таким образом, последовательные ребра в цепи Т (инцидентные вершине у) являются соседями в циклическом порядке 0±(у).

Определение 8. Будем говорить, что цепь является АОЕ-цепью, если она одновременно является ОЕ-цепъю и А-цепъю.

Доказана следующая теорема.

Теорема 8. Пусть дан плоский эйлеров граф Оу,Е) с полной системой переходов Ао(у). Любая А-цепь Т, начинающаяся в вершине у £ /о и заканчивающаяся ребром е £ /о, является ОЕ-цепъю.

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

Следствие 1. В плоском 4-регулярном графе существует АОЕ-цепь.

Разработан и запрограммирован алгоритм АОЕ-ТИАН, поиска АОЕ-цетт в плоском 4-регулярном графе. Он позволяет построить АОЕ-цепь для любого 4-регулярного графа (либо для графа, степень каждой вершины которого не больше 4). Можно воспользоваться алгоритмом А0Е-ТЕА1Ь и для любого плоского эйлерова графа. Если граф, передаваемый в качестве входных данных,

Рис. 2. Представление графа для построения АОЕ-цепи

не имеет Л-цепи, то алгоритм построит цепь, содержащую I < \Е\ ребер. Эта цепь не будет ни Л-цепью, ни, возможно, цепью с упорядоченным охватыва-нием. Однако выполнения данного алгоритма не достаточно, чтобы ответить на вопрос о существовании Л-цепи в графе. Для графов, степени вершин которого превосходят 4, алгоритм может не построить Л-цепь, несмотря на ее существование.

Алгоритм АОЕ-ТЛАИ.

Входные данные: Граф С(У,Е), представленный шестью функциями:

• ^(е), к = 1,2 - вершины, инцидентные ребру е,

• 1к(е), к = 1,2- ребра, полученные вращением ребра е против часовой стрелки,

• гк(е), к = 1,2 - ребра, полученные вращением ребра е по часовой стрелке, (см. рис.2).

Выходные данные: АОЕ-цепь С.

РАЗМЕТКА

Шаг 1. Пусть к = 1 и (5 = Е).

Шаг 2. Построить цикл Ск из ребер, смежных внешней грани графа <5(£), £ = ^(ео). Пометить эти ребра числом к (т.е. Уе 6 Ск : гапк(е) = к). Положить к = к+1.

Шаг 3. Пусть 0 = в\Ск. Если не все ребра помечены (С ф 0), перейти на шаг 2. В противном случае перейти на шаг 4. ПОСТРОЕНИЕ

Шаг 4. Начать построение цепи из вершины г>о £ смежной внешней

грани /о. Выбрать первое ребро ео: которому инцидентна вершина г>о, максимально возможного ранга гапк(е). Положить г>о = г'1(ео). В противном случае поменять индексы функций Ук(е), 1к(е), и гк(е), к = 1,2. Пусть е = ео - текущее ребро, добавляемое к цепи. С = {е}.

Шаг 5. Положим, что движение по ребру е осуществляется из вершины ■^(е) в вершину ^(е). В противном случае изменим направление обхода заменой

индексов функций vk(e), ifc(e), и гк(е) на (3 — к), к — 1,2. Пусть

С = С U {е}.

Если |С| = \E(G)\, завершить выполнение алгоритма, ЛОЕ-цепь построена. В противном случае перейти на шаг 6.

Шаг 6. Для пострения Л-цепи, пройти по одному из двух смежных е ребер максимального ранга в соответствии с циклическим порядком обхода в текущей вершине. Таким образом, е = г2(е), если rank(r2(e)) > rank(i2(e)) или е = 12{е), если rank(r2(e)) < rank(i2(e)). Если rank(r2(e)) = rank(Z2(e)), выбрать любое ребро, при проходе по которому по возможности не увеличивается число компонент связности в подграфе, состоящем из непройденных ребер. Перейти на шаг 5.

Конец алгоритма.

Показано, что алгоритм A0E-TRAIL решает задачу за полиномиальное время. Доказано, что если существует цепь Т с упорядоченным охватыванием в графе G, соответствующая не пересекающейся системе переходов Xt{G), то существует ровно |К(/о)| (где |У(/о)| - число вершин смежных внешней грани) цепей с упорядоченным охватыванием.

В общем случае, когда в графе G имеются точки сочленения, справедливы следующие утверждения.

Следствие 2. Пусть в плоском графе G = (V,E) с К точками сочленения vi,...vk g /о существует А-цепь Т с системой переходов Xt(G), a V(f0) - множество вершин, смежных внешней грани, тогда существует ровно =i(deg(ut)/2— 1) цепей с упорядоченным охватыванием для Xt(G) .

Следствие 3. Пусть в плоском графеС — (V, Е) существует непересекающаяся цепь Т. Пусть Xt(G) - система переходов, соответствующая этой цепи Т. Пусть V(fo) - множества вершин, смежных внешней грани, av\,... vk £ /о - разделяющие вершины, смежные внешней грани. Тогда существует ров-

»о \V(fo)\ + Ei=i(deg(ui)/2 - 1)

цепей с упорядоченным охватыванием для

системы переходов Xt(G).

Если система переходов Xt(G), соответствующая построенной ОЕ-цепи, имеет пересечения, то число цепей с упорядоченным охватыванием, соответствующих ей, лежит в промежутке от 1 до |^(/о)|.

В пятой главе рассматриваются разработанные программные средства для построения OS-цепей и покрытий, а также АО Е- цепей для 4-регулярных графов.

Все представленное программное обеспечение разработано автором диссертационной работы, либо под ее руководством молодыми специалистами кафедры

«Экономико-математические методы и статистика» Южно-Уральского государственного университета.

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

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

В заключении перечислены основные результаты работы.

Публикации автора по теме диссертации

Статьи, опубликованные в научных журналах и изданиях, которые включены в перечень ВАК

1. Панюкова Т. А.1 Обходы с упорядоченным охватыванием в плоских графах // Дискретный анализ и исследование операций. Сер. 2. 2006. Т. 13, № 2. С. 31-43.

2. Панюкова Т.А. Последовательности цепей с упорядоченным охватыванием // Известия Академии наук. Теория и системы управления. 2007. № 1. С. 88-97.

3. Панюкова Т.А. Маршруты с локальными ограничениями // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование. 2010. Вып. 5. № 16(192). С. 58-67.

4. Панюкова Т.А. Оптимальные эйлеровы покрытия с упорядоченным охватыванием для плоских графов // Дискретный анализ и исследование операций. 2011. Том 18, № 2. С. 64-74.

5. Панюкова Т.А. Оптимизация использования ресурсов при технологической подготовке процессов раскроя // Прикладная информатика. 2012. jY« 3(39). С. 20-32.

6. Панюкова Т.А., Алферов И.О. Маршруты с локальными ограничениями: алгоритмы и программная реализация // Прикладная информатика. 2013. № 1(43). С. 80-90.

7. Панюкова Т.А., Савицкий Е.А. The Software for Algorithms of Ordered Enclosing Covering Constructing for Plane Graphs // Вестник УГАТУ. 2013. Vol. 17, no. 6 (59). P. 39-44.

'Смена фамилии на основании Свидетельства о заключении брака от 11.10.2014 г. II-I1B № 07829.

8. Panyukova Т.А. Constructing of OE-postman Path for a Planar Graph // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование. 2014. Т. 7, № 4. С. 90-101.

Статьи, опубликованные в научных журналах и изданиях, индексируемых в SCOPUS

9. Panyukova Т. Eulerian Cover with Ordered Enclosing for Flat Graphs// Electronic Notes in Discrete Mathematics. 2007. No. 28. P. 17-24.

10. Panyukova Т., Mukhacheva E.A. Mathematical Models for Cutting Process Design // IFAC Proceedings Volumes. 13th IFAC Symposium on Information Control Problems in Manufacturing, INCOM'09. Сер. «Proceedings of the 13th IFAC Symposium on Information Control Problems in Manufacturing, INCOM'09» sponsors: Honeywell. Moscow, 2009. P. 1085-1090.

11. Panyukova T. Chain Sequences with Ordered Enclosing // Journal of Computer and System Sciences International. 2007. Vol. 46, No. 1. P. 83-92.

Статьи в изданиях, индексируемых в РИНЦ

12. Panioukova Т.A., Panyukov A.V. The Algorithm for Tracing of Flat Euler Cycles with Ordered Enclosing // Известия Челябинского научного центра УрО РАН. 2000. № 4(9). Р. 18-22.

13. Панюкова Т.А., Алферов И.О. Техника программной реализации алгоритма построения допустимой эйлеровой цепи // Информационные технологии и системы: материалы Первой междунар.конф. (Банное, Россия, 28.024.03.2012) / отв.ред. В.А. Мельников. Челябинск: Изд-во Челяб.гос.ун-та, 2012. С. 32-34.

14. Панюкова Т.А. Об оптимальном эйлеровом покрытии плоских графов // Информационные технологии и системы: тр. Второй междунар. науч. конф. (Банное, Россия, 27 февр.-З марта 2013 г.): науч. электр. изд. / отв. ред. А. В. Мельников. Челябинск: Изд-во Челяб.гос.ун-та, 2013. С. 52-54.

15. Панюкова Т.А., Савицкий Е.А. Программное обеспечение для построения покрытия с упорядоченным охватыванием для многосвязных плоских графов // Вестник Южно-Уральского государственного университета: Серия "Вычислительная математика и информатика". 2013. Т. 2, № 2. С. 111-117.

16. Panyukova Т. On Algorithms for Eulerian Trails Constructing // Proceedings of the Workshop on Computer Science and Information Technologies (Vienna-Budapest-Bratislava, September 15-21, 2013). Ufa: USATU, 2013. Vol. 1. P. 176181.

17. Панюкова Т.А. Алгоритм построения оптимального эйлерова покрытия для многосвязного графа // Современные информационные технологии и ИТ-образование. Сборник избранных трудов VII Международной научно-практической конференции. Под ред. проф. В.А. Сухомлина. М.: ИНТУ-ИТ.РУ, 2012. - С. 706-713.

18. Патокова Т.А. Построение эйлеровых циклов с упорядоченным охватыва-нием как математическая модель решения задачи раскроя // Современные информационные технологии и ИТ-образование /Сборник избранных трудов VIII Международной научно-практической конференции. Под ред. проф. В.А. Сухомлина. М.: ИНТУИТ.РУ, 2013. С. 706-713.

19. Панюкова Т.А. О построении маршрута движения режущего инструмента при условии вырезания только соседних деталей // Информационные технологии и системы: тр. Третьей междунар. науч. конф. (Банное, Россия, 26 февр.-2 марта 2014 г.): науч. электр. изд. Отв. ред. Ю.С. Попков, A.B. Мельников. Челябинск: Изд-во Челяб. гос. ун-та, 2014. С. 41-42.

20. Панюкова Т.А., Савицкий Е.А. Алгоритм проверки маршрута реза в раскройном плане на сответствие условию упорядоченного охватывания // XII Всероссийское совещание по проблемам управления ВСПУ-2014. Институт проблем управления им. В.А. Трапезникова РАН. М.: Институт проблем управления им. В.А. Трапезникова РАН, 2014. С. 9315-9318.

21. Панюкова Т.А. Комбинаторика и теория графов: Учебное пособие. М.: Книжный дом «ЛЕНАНД», 2014. 208 с.

22. Панюкова, Т.А. Модель движения режущего инструмента при условии вырезаний только соседних деталей // «Информационно-телекоммуникационные системы и технологии» (ИТСиТ-2014) Материалы Всероссийской научно-практической конференции. Кемерово, 2014. С. 411-412.

Другие научные публикации

23. Панюкова Т.А. Построение эйлеровых циклов специального вида // Научные труды молодых исследователей программы «Шаг в будущее». М.: HTA «Актуальные проблемы фундаментальных наук», 1999. Т. 1. С. 108.

24. Панюкова Т.А. Информационная и технологическая поддержка процессов раскроя одежды // Научные труды молодых исследователей программы «Шаг в будущее». М.: HTA «Актуальные проблемы фундаментальных наук», 1999. Т. 2. С. 168.

25. Панюкова Т.А. Информационная и технологическая поддержка процессов раскроя одежды // Сборник материалов Российской молодежной научной и инженерной выставки «Шаг в будущее» ( Москва, 9-13 марта, 1999). М.: HTA «Актуальные проблемы фундаментальных наук», 1999. С. 48.

26. Панюкова Т.А., Потоков A.D. Эйлеровы циклы с упорядоченным охва-тыванием // Проблемы теоретической кибернетики. Тезисы докладов XII Международной конференции (Нижний Новгород, 17-22 мая, 1999 г.). Под ред. Лупанова О.Б. М.: Изд-во механико-математического факультета МГУ, 1999. Ч. II. С. 148.

27. Panyukova Т. Pattern Maker Project - from Doll to Reality. Informative and Technological Support for Clothes Cutting Process// 11th European Union

Contest for Young Scientists (19-26 September 1999, Thessaloniki, Greece). Documents of the Contest: European Commission, Brussels, Belgium, 1999. P. 130.

28. Панюкова Т.А. Синтез программ управления процессом раскроя // Обозрение прикладной и промышленной математики. Под ред. Прохорова Ю.В. М.: Научное изд-во «ТВП», 2001. Т. 8, Вып. 2. С. 664.

29. Панюкова Т.А. Построение эйлеровых циклов специального вида в пла-нарном графе // Материалы VII Международного семинара «Дискретная математика и ее приложения»; Ч. II. Под ред. О. Б. Лупанова. М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2001. С. 149.

30. Панюкова Т.А. К задаче об эйлеровых циклах с упорядоченным охва-тыванием/ Т.А. Панюкова//Тезисы Второго Международного конгресса студентов, молодых ученых и специалистов «Молодежь и наука - третье тысячелетие»/YSTM'02 (15-19 апреля 2002 г.). Часть 2. - М.: Издание региональной общественной организации научно-технической ассоциации «Актуальные проблемы фундаментальных наук», 2002. С. 33-34.

31. Панюкова Т.А. Алгоритм построения эйлеровых циклов специального вида // Проблемы теоретической кибернетики. Тезисы докладов XIII Международной конференции (Казань, 27-31 мая 2002 г.). Часть II. Под ред. О. В. Лупанова. М.: Изд-во механико-математического факультета МГУ, 2002. С. 142.

32. Panyukova Т., Panyukov A. The Algorithm for Construction of Euler Cycles with Ordered Enclosing// Российская конференция «Дискретный анализ и исследование операций»: Материалы конференции (Новосибирск, 24-28 июня, 2002). Новосибирск: Издательство Института математики СО РАН, 2002. С. 147.

33. Панюкова Т.А. Алгоритмы построения обходов с упорядоченным охваты-ванием в плоских эйлеровых графах //Материалы Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 15 июля 2003 г.). Омский филиал Института Математики СО РАН. Омск: Изд-во Наследие. Диалог Сибирь, 2003. С. 188.

34. Panioukova Т.A., Panyukov A.V. Algorithms for Construction of Ordered Enclosing Traces in Planar Eulerian Graphs // The International Workshop on Computer Science and Information Technologies' 2003, Proceedings of Workshop (Ufa, September 16-18, 2003). Ufa: USATU, 2003. Vol. 1. P. 134-138.

35. Панюкова Т.А. Рекурсивный алгоритм построения обходов с упорядоченным охватыванием в плоских неэйлеровых графах // Материалы VIII Международного семинара «Дискретная математика и ее приложения»

(Москва, 2-6 февраля, 2004 г.). М.: Изд-во механико-математического факультета МГУ, 2004. С. 444.

36. Панюкова Т.А. Эйлеровы циклы специального вида // Российская конференция «Дискретный анализ и исследование операций». Материалы конференции (Новосибирск, 28 июня-2 июля, 2004 г.). Новосибирск: Изд-во Ин-та математики, 2004. С. 147.

37. Панюкова Т.А. Маршруты манипулятора, не содержащие запрещенных переходов // Труды XXXIV Уральского семинара «Механика и процессы управления». Т. 2. Миасс, 2004. С. 556-564.

38. Панюкова Т.А. Построение маршрутов с упорядоченным охватыванием в плоских графах // Труды 36-й Региональной молодежной конференции «Проблемы теоретической и прикладной математики». Екатеринбург: УрО РАН, 2005. С. 61-66.

39. Панюкова Т.А. Маршруты с локальными ограничениями // Труды 37-й Региональной молодежной конференции «Проблемы теоретической и прикладной математики». Екатеринбург: УрО РАН, 2006. С. 66-70.

40. Панюкова Т.А. Маршруты с упорядоченным охватыванием // Труды VII международной конференции «Дискретные модели в теории управляющих систем» (Покровское, 4-6 марта, 2006 г.). М.: МАКС Пресс, 2006. С. 265271.

41. Panyukova Т. Eulerian Cover with Ordered Enclosing for Flat Graphs// Abstracts of Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications. Prague, Charles University, 2006. P. 103104.

42. Панюкова Т.А. Программное обеспечение для построения цепей с упорядоченным охватыванием // Труды 38-й Региональной молодежной конференции «Проблемы теоретической и прикладной математики». Екатеринбург: УрО РАН, 2008. С. 360-365.

43. Panyukova Т. The Special Routes in Plane Graphs// Abstracts for 6-th International Congress on Industrial and Applied Mathematics (Zurich, 16-20 July, 2007). 2007. P. 449-450.

44. Panyukova T. The special routes in plane graphs // PAMM. Special Issue: Sixth International Congress on Industrial Applied Mathematics (ICIAM07) and GAMM Annual Meeting, Zurich, 2007, Published Online: 12 Dec 2008. Vol. 7. Issue 1. P. 2070015-2070016. DOI: 10.1002/pamm.200701066.

URL: http://www3.interscience.wiley.com/journal/121560409/abstract (дата обращения: 13.12.2014).

45. Panyukova Т. Special Routes in Flat Graphs// Short abstracts of the international meeting "Euler and Modern Combinatorics" (St. Petersburg, June 1-7, 2007), 2007. P. 34-35.

46. Панюкова Т.Л. Маршруты с локальными ограничениями //Информационно-математические технологии в экономике, технике и образовании: сборник тезисов Международной научной конференции. Екатеринбург: УГТУ-УПИ, 2007. С. 303-305.

47. Панюкова Т.А., Мирасов В.Ф. Построение совместимых цепей в графах // Проблемы теоретической и прикладной математики: тр. 39-й Регион, молодеж. конф. Екатеринбург, 2008. С. 38-43.

48. Панюкова Т.А. Программное обеспечение для построения последовательностей цепей с упорядоченным охватыванием // Проблемы теоретической и прикладной математики: труды 39-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2008. С. 393-398.

49. Панюкова Т.А., Мухачева Э.А. Проблема рационального использования промышленных материалов: оптимизация обратного хода раскроя // Обратные задачи в приложениях. Сборник статей научно-практической конференции. Бирск: БирГСПА, 2008. С. 270-276.

50. Panyukova T. Routing problems for cutting processes // The International Workshop on Computer Science and Information Technologies' 2008. Proceedings of Workshop (Turkey, Antalya, September 15-17, 2008). Ufa: Ufa State Technical University, 2008. Vol. 2. P. 100-106.

51. Панюкова T.A. Построение эйлерова покрытия с упорядоченным охватыванием для плоского графа с прямоугольными гранями // X Белорусская математическая конференция: Тез. докл. междунар. науч. конф. (Минск, 3-7 ноября 2008 г.). Мн.: Институт математики НАН Беларуси, 2008. Ч. 5. С. 98.

52. Панюкова Т.А. Построение маршрута для оптимального хода режущего инструмента // Информационно-математические технологии в экономике, технике и образовании. Тезисы докладов 3-й Международной научной конференции. Екатеринбург: УГТУ-УПИ, 2008. Ч. 2. С. 12-13.

53. Панюкова Т.А., Савицкий Е. А. Композиция интерфейсов при технологической подготовке процессов раскроя // Труды 40-й Региональной молодежной конференции «Проблемы теоретической и прикладной математики». Екатеринбург: УрО РАН, 2009. С. 367-372.

54. Панюкова Т.А. Некоторые критерии оценки раскройных планов //IV Всероссийская конференция «Проблемы оптимизации и экономические приложения». Материалы конференции (Омск, 29 июня-4 июля, 2009). Омский филиал Института математики им. C.JI. Соболева СО РАН. Омск: Полиграфический центр КАН, 2009. С. 238. '

55. Панюкова Т. А., Панюков А.В. Decreasing of Length for Routes with Ordered Enclosing // Дискретная математика, алгебра и их приложения. Тез. Докл.

Междунар. науч. конф. (Минск, 19-22 октября, 2009 г.). Мн.: Институт математики НАН Беларуси, 2009. С. 155-157.

56. Панюкова Т.А., Савицкий Е.А.О некоторых критериях оценки покрытий с упорядоченным охватыванием // Материалы X Международного семинара «Дискретная математика и ее приложения» (1-6 февраля, 2010 г.). М.: Изд-во механико-математического факультета МГУ, 2010. С. 444.

57. Панюкова Т.А. Покрытия с упорядоченным охватыванием с минимальной длиной дополнительных построений // Российская конференция «Дискретная оптимизация и исследование операций»: Материалы конференции (Алтай, 27 июня - 3 июля, 2010). Новосибирск: Изд-во Ин-та математики.

2010. С. 98.

58. Panyukova Т. Ordered Enclosing Covers with Minimal Length of Additional Edges// Abstracts of 8th French Combinatorial Conference (Orsay, France, June,28-July,2, 2010). 2010. Abstract № 18.

59. Panyukova T., Savitskiy E. Optimization of Resources Usage for Technological Support of Cutting Processes // Proceedings of the Workshop on Computer Science and Information Technologies (Russia, Moscow-St.Petersburg, September 13-19, 2010). Ufa State Technical University, 2010. Vol. 1. P. 66-70.

60. Панюкова Т.А., Алферов И.О., Сахаров И.А. Об алгоритме построения совместимых путей в графе // Информационный бюллетень №12 Ассоциации математического программирования. XIV Всероссийская конференция «Математическое программирование и приложения». Екатеринбург, 2011. С. 120-121.

61. Panyukova Т. The Covering of Graphs by Trails with Local Restrictions// Proceedings oh the 13-th International Workshop on Computer Science and Information Technologies. Уфа: Издательство УГАТУ, 2011. T. 1. С. 202207.

62. Панюкова Т.А., Савицкий Е.А. Допустимые эйлеровы покрытия с упорядоченным охватыванием для мпогосиялюго графа // Статистика. Моделирование. Оптпмпмппн: сб. тр. Всероссийской конференции (Челябинск, 28 ноября - 3 декабря 2011 г.) Челябинск: Издательский центр ЮУрГУ,

2011. С. 154 158.

63. Панюкова Т.А. Эйлерово покрытие с упорядоченным охватыванием для многосвязного графа // Математическое моделирование, оптимизация и информационные технологии: сборник научных трудов 3-й Международной конференции. Кишинев, 2012. С. 429-437.

64. Панюкова Т.А. Эйлерово покрытие с упорядоченным охватыванием для многосвязного плоского графа // Материалы V Всероссийской конференции (Омск, 2-6 июля, 2012 г.). 2012. С. 154.

65. Panyukova T., Alferov I. The Software for Constructing Trails with Local Restrictions in Graphs // Open Journal of Discrete Mathematics. 2013. No. 3, Vol. 2. P. 86-92. DOl: 10.4236/ojdm.2013.32017.

66. Панюкова T.A. Алгоритм покрытия плоского графа последовательностью цепей с упорядоченным охватыванием // Материалы международной конференции «Дискретная оптимизация и исследование операций». Новосибирск: Изд-во ин-та математики, 2013. С. 110.

67. Panyukova T., Savitskiy Е. The Software for Algorithms of Ordered Enclosing Covering Constructing for Plane Graphs // The Proceedings of the International Conference "Information Technologies for Intelligent Decision Making Support" (2013, May 21-25, Ufa, Russia). Уфа: изд-во УГАТУ, 2013. С. 122-125.

68. Panyukova Т. Covering with ordered enclosing for a multiconnected graph // Abstracts of the Seventh Czech-Slovak International Symposium on Graph Theory, Combinatorics, Algorithms and Applications (Kosice, Slovakia, 7-13 July, 2013), 2013. P. 65.

69. Panyukova T. Covering with ordered enclosing for a disconnected graph // Proceedings of the Workshop on Computer Science and Information Technologies (Sheffield, England, September 16-22, 2014). Ufa: USATU, 2014. Vol. 1. P. 132-137.

70. Makarovskikh T.A. On the number of starting points for a fixed cutting plan and fixed cutter trajectory // Proceedings of the 2-nd International Conference «Inteligent Technologies for Information Processing and Management». Ufa: USATU, 2014. Vol. 1. P. 239-244.

71. Makarovskikh T.A. The Algorithm for Constructing of Cutter Optimal Path // Journal of Computational and Engineering Mathematics. 2014. Vol. 1, №2. P. 52-61.

Свидетельства о регистрации программ для ЭВМ

72. Панюкова Т.А. Свидетельство Роспатента о государственной регистрации программы построения эйлеровых циклов с упорядоченным охватыванием (Euler Cycles Constructor) №2004610785 от 3 февраля 2004, правообладатель: Панюкова Т.А.

73. Панюкова Т.А. Свидетельство Роспатента о государственной регистрации программы построения маршрутов с упорядоченным охватыванием (Ordered Routes Constructor) №2005612413 от 22 сентября 2005, правообладатель: Панюкова Т.А.

74. Панюкова Т.А., Савицкий Е.А. Свидетельство Роспатента о государственной регистрации программы построения оптимальных покрытий с упорядоченным охватыванием для многосвязных графов №2011617777 от 09 августа 2011, правообладатель: ФГБОУ ВПО «ЮУрГУ» (НИУ).

75. Панюкова Т.А., Алферов И.О. Свидетельство Роспатента о государственной регистрации программы построения эйлеровой цепи с запрещенными переходами в графе №2013661312 от 08 октября 2013, правообладатель: ФГБОУ ВПО «ЮУрГУ» (НИУ).

Издательский центр Южно-Уральского государственного университета

Подписано в печать 26.02.2015. Формат 60x84 1/16. Печать цифровая. Усл. печ. л. 1,63. Тираж 120 экз. Заказ 50/157.

Отпечатано в типографии Издательского центра ЮУрГУ. 454080, г. Челябинск, пр. им. В.И. Ленина, 76.