Задачи маршрутизации специального вида в плоских графах: Свойства, алгоритмы, программное обеспечение тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Панюкова, Татьяна Анатольевна

• Панюкова, Татьяна Анатольевна
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Панюкова, Татьяна Анатольевна

Введение.

1. Применение графов в математическом моделировании систем управления.

1.1. Основные понятия и определения.

1.1.1. Обыкновенные графы.

1.1.2. Мультиграфы.

1.1.3. Топологические графы.

1.2. Маршруты в графах.

1.2.1. Эйлеровы циклы. Задача о Кенигсбергских мостах.

1.2.2. Гамильтоиовы циклы. Задача коммивояжера.

1.3. Разложения графов на цепи.

1.4. Алгоритмы построения эйлеровых циклов.

1.5. Алгоритм построения допустимой цепи.

• Выводы.

2. Построение множества допустимых маршрутов, покрывающих граф.

2.1. Система разбиения.

2.2. Алгоритм построения допустимой эйлеровой цепи.

2.3. Алгоритм построения покрытия допустимыми цепями.

Выводы.

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

3.1. Определение и пример.

3.2. Существование решения.

3.3. Рекурсивный алгоритм построения эйлерова цикла с упорядоченным охватыванием.

3.4. Программное обеспечение задачи построения эйлерова цикла с упорядоченным охватыванием.

Введение диссертации (часть автореферата) на тему «Задачи маршрутизации специального вида в плоских графах: Свойства, алгоритмы, программное обеспечение»

Дискретная математика развивалась в связи с изучением законов и правил человеческого мышления, что и обусловило ее применение в тех областях техники, которые так или иначе связаны с моделированием мышления, и в первую очередь в вычислительной технике и программировании [19].

Теория графов - важный раздел современной дискретной математики, как с точки зрения внутренних стимулов ее развития, так и для разнообразных приложений. Практическая роль теории графов особенно возросла во второй половине 20-го века в связи с проектированием различных АСУ и вычислительных устройств дискретного действия. В теоретическом же плане, помимо давнишних связей с комбинаторной топологией и геометрией, наметились существенные сдвиги на стыке теории графов с алгеброй, математической логикой, лингвистикой, теорией игр, общей теорией систем [24] и др.

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

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

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

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

Имеется ряд журнальных публикаций других авторов, в которых также рассматриваются задачи, посвященные эйлеровым цепям специального вида, например, расширение класса запрещенных переходов [14], самонепересекающиеся и непересекающиеся цепи, бинаправленные двойные обходы [3, 46], маршруты Петри [17], прямолинейные маршруты [12], реберно-упорядоченные маршруты [2] и т.д.

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

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

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

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

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

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

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

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

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

• Разработан алгоритм построения в плоском графе маршрута, покрывающего все его ребра и принадлежащего классу С. Вычислительная сложность алгоритма не более 0(\Е\2).

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

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

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

Апробация работы. Результаты исследований докладывались и обсуждались на следующих конференциях:

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

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

3. XI Соревнование молодых ученых Европейского Союза, Греция, 1926 сентября, 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. Молодежная конференция «Проблемы теоретической и прикладной математики», Екатеринбург, ИММ, УрО РАН, 30 января - 4 февраля, 2005 г.

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

Публикации. По материалам проведенных исследований опубликовано 19 печатных работ, в числе которых 2 свидетельства о регистрации программного продукта.

Структура и объем работы. Диссертация состоит из введения, шести глав, заключения, списка использованной литературы (46 наименований) и 4 приложений. Приложения включают тексты программ и свидетельства об их регистрации. Основная часть работы содержит 95 страниц машинописного текста, 35 иллюстраций.

Заключение диссертации по теме «Теоретические основы информатики», Панюкова, Татьяна Анатольевна

Выводы

1. Задача построения эйлерова цикла с упорядоченным охватыванием в плоском эйлеровом графе имеет сложность не более 0(|E(G)|).

2. Проблема построения покрытия плоского графа последовательностью цепей с упорядоченным охватыванием также имеет сложность не более 0(|E(G)|).

3. Алгоритм В2, рассмотренный в данном разделе, решает задачи построения эйлерова цикла с упорядоченным охватыванием и построение последовательности цепей с упорядоченным охватыванием.

6. О возможных практических приложениях решаемой задачи

В настоящее время, в связи с широким развитием информационных технологий, отрасли науки, занимающиеся задачами автоматизации проектирования и конструкторско-технологической подготовки производства, переживают как бы второе рождение. С появлением рыночных отношений российский рынок оказался открытым для новых технологий, уникального импортного оборудования, предназначенного для автоматизации многих технологических процессов. Это коснулось и задач раскроя. Доступной стала информация о станках, например, всемирно известной немецкой фирмы GERBER. Причем, оказалось, что системы GGT Гербера широко используются во всем мире производителями одежды [5]. Более чем 2200 таких систем нашли свое применение во всем мире. Очевидно, что в силу своей универсальности и дороговизны такие системы, как правило, оказались не доступны многим отечественным производителям.

В последнее время и в нашей стране большое внимание уделяется вопросам создания высокоэффективных технологий развития социальной сферы, созданию гибких автоматизированных производств товаров народного потребления на базе информационных технологий, в частности, созданию компьютерного проектирования персонифицированной высококачественной одеэ/сды для индивидуальных потребителей. Направление, связанное с созданием гибких автоматизированных производств товаров народного потребления на базе информационных технологий, официально объявлено одним из приоритетных направлений развития науки (Поиск, №1, 2002).

Совсем недавно на российском рынке появился ряд отечественных разработок этого профиля, ориентированных на серийное производство продукции [16].

Другой пример можно привести из области рекламных технологий. Действительно, в настоящее время в связи с развитием рекламных технологий, в частности, с революционными изменениями, обусловленными применением виниловых технологий, стало возможным любому желающему увидеть воочию весь технологический процесс компьютерной подготовки к резке и самой резки с помощью плоттеров. Текст или графическая информация, обработанная известной программой Corel Draw, импортируется в соответствующий файловый формат специальных программ, обеспечивающих преобразование информации для управления режущим инструментом плоттера. Данная технология уже широко используется в большинстве как крупных, так и мелких рекламно-производственных компаний в столичных городах. Естественно, что алгоритмы, заложенные в программах управления раскроем, являются коммерческой тайной фирмы-изготовителя, поэтому сделанные ниже выводы основаны только на наблюдениях и контактах автора (в качестве заказчика) с персоналом. Плоттеры, эксплуатируемые в рекламных фирмах, производят вырезание объектов не в том порядке, в каком объекты геометрически расположены на листе, а в том порядке, который определяется временем размещения их на листе. Таким образом, штатной является ситуация, когда два объекта, размещенные на листе в непосредственной близости друг от друга, вырезаются не последовательно один за другим, а после нескольких объектов, размещенных совсем на другом конце листа. Даже если предположить, что этот факт не влияет на качество вырезанных деталей, затраты времени на выполнение этого процесса могли бы быть намного меньше, если бы алгоритм резки при прочих равных условиях учитывал, например, не время занесения объекта на раскройный план, а его геометрическое положение относительно других вырезаемых объектов. При выполнении вырезания в порядке, определяемом временем создания объекта, имеет место большое число холостых прогонов материала или резца.

Более того, при вырезании из виниловой пленки букв, состоящих более чем из одного контура (например, «О», «Р», «В»), не уделяется внимания порядку вырезания этих контуров. На первый взгляд, может показаться, что порядок не принципиален. Однако практика показала, что, если внутренние контуры вырезаются после того, как прорезаны внешние, при малых размерах букв (менее 15 мм), зачастую возникает брак. Например, при вырезании мелкого текста из виниловой пленки не очень острым ножом (пригодным, между тем, для выполнения достаточно крупных объектов) возможно смещение вырезанных объектов на еще не прорезанные участки пленки, что приводит к порче и вырезанного объекта, и того объекта, который геометрически находится на том месте, куда сместился вырезанный объект.

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

Крупнейшие рекламно-производственные компании, специализирующиеся на изготовлении наружной рекламы, в настоящее время активно внедряют современное высоко-технологичное оборудование и компьютерные технологии. На российском рынке недавно появились фрезеровалыю-гравировальные станки известной канадской фирмы PRTCIX, режущие плоттеры IOLINE (США), фрезеро-вально-гравировальные станки Multi-Cam (используемые в том числе и для раскроя листовых материалов) и др. До недавнего времени автору работы не удавалось найти информации по наличию отечественных аналогов.

Тем не менее, появились разработки отечественных авторов, работающих в области создания комплексов программ для оснащения процессов раскроя. Например, на сайте АО «Топ Системы» [15,16], который дает информацию о лучших российских программных продуктах для решения задач автоматизации проектирования и конструкторско-технологической подготовки производства (авторы разработок - Московский государственный технологический университет «СТАНКИН» и Акционерное общество «Топ Системы») заявлено о разработке Российского интегрированного комплекса программных продуктов T-FLEX СAD/CАМ/СAE/PDM для Windows 9x/NT/2000/XP, охватывающих все области сквозного компьютерного проектирования [1]:

• управления проектами;

• автоматизации черчения;

• автоматизации проектирования;

• трехмерного параметрического моделирования;

• технологической подготовки производства;

• подготовки программ для станков с ЧПУ;

• системы имитации процесса обработки детали на станке с ЧПУ по готовой управляющей программе и т.п.

Так, подсистема T-FLEX предназначена для расчета и построения эскизов оптимальных схем раскроя листового материала и решает следующие задачи[16]:

• раскрой листов на карты и/ или полосы;

• раскрой произвольной плоской детали в полосе и/ или листе, так называемый регулярный раскрой;

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

Автоматический раскрой расширил сферы своего действия, внедряясь в отрасли легкой промышленности. Разработка и производство моделей одежды на основе новых технологий объединяет в себе целый комплекс разных вопросов [43,44]:

1) применение компьютерных технологий для задач построения лекал, раскладки лекал, составления раскройных планов, построения алгоритмов управления процессом раскроя;

2) составление автоматизированных баз данных, облегчающих работу модельера;

3) использование компьютерных технологий для ряда расчетов (определение расхода ткани, расчетной длины раскройного плана, анализ качества кроя и т.п.);

4) поиск инженерных методов конструирования разверток по заданной поверхности.

Известное во всем мире оборудование GGT (ТЕХНОЛОГИЯ ОДЕЖДЫ ГЕРБЕРА) помогает работникам швейной промышленности экономить время, снижать расходы, выпускать больше продукции значительно лучшего качества. Компьютерные системы компании ТЕХНОЛОГИЯ ОДЕЖДЫ ГЕРБЕРА - это сортировка, маркировка, моделирование и конструирование. Системы автоматизированы, они значительно сокращают расход времени, повышают производительность, и при этом позволяют максимально использовать ткань. Запатентованные компьютерные устройства для раскроя режут многослойную ткань с чрезвычайной скоростью и точностью.

Имеются сообщения об отечественных разработках, описывающих опыт использования методов автоматизированного конструирования одежды, возможности компьютерного редактора лекал [43,44]. Так, в [43] отмечается использование двух подсистем проектирования базовых основ конструкции изделия: по стандартным методикам и путем развертки трехмерной модели манекена. В основу этих подсистем легли инструментальные средства AutoCAD и, естественно, они требуют некоторой подготовки пользователя, так как предназначены в первую очередь для конструкторов и модельеров.

Завершается создание отечественной системы «T-FLEX/Одежда» [15] предназначенной для автоматизации процессов конструирования и моделирования, раскладки на ткани деталей одежды, расчета материала и процента отхода, а также получения готовых лекал любых моделей одежды по типовым или индивидуальным размерам. Возможен вывод лекал на принтер или плоттер в натуральную величину или в любом масштабе. Если ширина принтера не позволяет выводить лекала целиком, то программа автоматически разрежет лекала на листы и даст линии соединения.

Заключение

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

2. Исследована задача построения обходов, избегающих запрещенных переходов. Построены алгоритмы отыскания обходов, избегающих запрещенных переходов. Сделан анализ сложности построенных алгоритмов.

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

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

5. Разработаны алгоритмы А1 и А2 нахождения в плоском эйлеровом графе G=(V,E) эйлеровых циклов введенного класса, имеющие вычислительную сложность 0(\Е\2) и 0(\Е\) соответственно.

6. Разработан алгоритм построения в плоском графе маршрута, покрываю-^ щего все его ребра и принадлежащего классу С. Вычислительная сложность алгоритма не более 0(\Е\2).

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

Список литературы диссертационного исследования кандидат физико-математических наук Панюкова, Татьяна Анатольевна, 2006 год

1. ALGOR1.HM Press Room// http://pressroom.ru/

2. Chebikin D. On k-edge-ordered graphs. Discrete Mathematics 281 (2004). P. • 115-128.

3. Fleischner H. Eulerian Graphs and Related Topics. Part 1, Vol.2 Ann. Discrete Mathematics (no. 50), 1991.

4. Fleichner H. Eulerian Graphs, in: Beineke L.W., Wilson R.J. (eds.); Selected Topics in Graph Theory 2 (Academic Press, London-New York, 1983), P. 17-53.

5. Gerber Garment Technology/ www.zebra.ru/zebrR GE.html

6. Hierholzer C. Uber die Moglichkeit, einen Linienzung ohne Wiederholung undohne Unterbrechung zu umfahren, Math. Annalen VI (1873). P.30-32.V

7. Kotzig A. Moves Without Forbidden Transitions in a Graph, Mat.-Fiz. Casopis 18 (1968). no.l, P.76-80.

8. Panyukov A.V., Panioukova T.A. The Algorithm for Tracing of Flat Euler Cycles with Ordered Enclosing // Proceedings of Chelyabinsk Scientific Center, 4(9), 2000. P. 18-22. - http://www.sci.urc.ac.ru/news/2000 4/2000 4 1 4.pdf.

9. Panioukova Tatiana A. 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

10. Greece/ Documents of the Contest-:European Commission, Brussels, Belgium-130 p.,with ill., p. 53.

11. Pisanski Т., Tucker T.W., Zitnik A. Straight-ahead walks in Eulerian graphs, Discrete Mathematics 281 (2004. P. 237-246.

12. Syslo M.M., Deo N., Kowalik J.S. Discrete optimization with PASCAL Programs (Prentice Hall Inc., New Jersey, 1983).

13. Szeider S. Finding paths in graphs avoiding forbidden transitions// Discrete Applied Mathematics, 2003. 126. - P. 261-273.

14. T-FLEX / Одежда система моделирования одеждыhttp://www.topsystems.ru/products/tfdres01.htm

15. Т-FLEX/ Раскрой оптимизация раскроя листового материала // http://www.topsystems.ru/products/tfraskr.htm

16. Zitnik A. Plane graphs with Eulerian Petrie walks // Diskrete Mathematics, 2002. 244. - P. 539-549.

17. Андерсон Дж.А. Дискретная математика и комбинаторика.: Пер. с англ. -М.: Издательский дом «Вильяме», 2004. 960 е.: ил.

18. Белоусов А.И., Ткачев С.Б. Дискретная математика / Под ред. B.C. Зарубина, А.П. Крищенко. 2-е изд., стереотип. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. - 744 с.

19. Белый С.Б. О самонепересекающихся и непересекающихся цепях // Математические заметки, 1983. Т.34. - №4. - С. 625-628.

20. Болл У., Коксетер Г. Математические эссе и развлечения: Пер. с англ./ Под ред. С предисл. и примеч. И.М. Яглома. М.: Мир, 1986.-474 е., ил.

21. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. М.: Мир, 1982. - 416 е., ил.

22. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука. Гл. ред. Физ.-мат. Лит., 1990. - 384 с.

23. Зыков А.А. Основы теории графов / А.А. Зыков. М.: Вузовская книга, 2004.-664 е.: ил.

24. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. 960 е., 263 ил.

25. Кристофидес Н. Теория графов. М.: Мир, 1978. - 432 с.

26. Панюкова Т.А. Алгоритмы формирования программы управления раскроем // Четвертая всероссийская научно-практическая «Иформационные технологии и электроника», Екатеринбург, 15-16 декабря 1999 г. http://www/rtf.ustu.ru/science/1999/AUTS/panioukova2.htm

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

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

29. Панюкова Т.А. Программа построения маршрутов с упорядоченным охватыванием (Ordered Routes Constructor) // Свидетельство об официальной регистрации программы для ЭВМ №2005612413.- М.: РОСПАТЕНТ, 22 сентября 2005.

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

31. Панюкова Т.А. Построение эйлеровых циклов специального вида //Научные труды молодых исследователей программы «Шаг в будущее».

32. М.: НТА «Актуальные проблемы фундаментальных наук», (Сер. Профессионал).- 1999, Т.1.-108 е., с илл., С. 74-75.

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

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

35. Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ. М.: Мир, 1984.-455 е., ил.

36. Сигал И.Х., Иванов А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М.: ФИЗМАТЛИТ, 2002. -240 с.

37. Токарев Ю.П. Опыт использования методов автоматизированного конструирования одежды // Тезисы докладов Международной конференции, -Омск. 1997.

38. Ультан А.Е., Ревякина О.В. Компьютерный редактор лекал одежды. Проблемы оптимизации и экономические приложения // Тез. докл. Международной конф. Омск. - 1997.

39. Фляйшнер Г. Эйлеровы графы и смежные вопросы: Пер. с англ. М.: Мир, 2002. - 335 е., ил.