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

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

ПАНЮКОВА Татьяна Анатольевна

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

Специальность 05.13.17 - «Теоретические основы информатики»

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

ОБЯЗАТЕЛЬНА ; БЕОЛ.ПА! Г'.

о ^ о с ¡^> г: - •

. ч О Г ! V I ! . ! . ' .

Москва, 2006

Работа выполнена в Южно-Уральском государственном университете и Вычислительном центре им. А.А. Дородницына РАН.

Научный руководитель -

Официальные оппоненты:

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

Цурков Владимир Иванович

доктор физико-математических наук, профессор Миронов Анатолий Анатольевич;

кандидат физико-математических наук, доцент Шпитонков Михаил Иванович.

Ведущая организация -

Уфимский государственный авиационно-технологический университет

Защита диссертации состоится.

2006 г., в

часов, на

заседании диссертационного совета Д002.017.02 Вычислительного центра им. А.А. Дородницына РАН по адресу: 119991, г. Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Вычислительного Центра им. А.А. Дородницына РАН.

Автореферат разослан

2006 г.

Ученый секретарь диссертационного совета, д.ф.-м.н.

В.В. Рязанов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. ХП1 Международная конференция «Проблемы теоретической кибернетики», Казань МГУ им.М.В.Ломоносова, Институт прикладной математики им.М.В.Келдыша РАН, ННГУ им. Н.И. Лобачевского, КГУ, 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 г.

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

Построен также алгоритм Рс-СОВМЕСТИМЫЕ МАРШРУТЫ для построения эйлерова покрытия графа С допустимыми маршрутами. Алгоритм имеет вычислительную сложность 0(|£|-|у|).

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

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

Пусть на плоскости 5 задан плоский граф С~(У,Е), и пусть /0 - внешняя (бесконечная) грань графа & Для любого подмножества ЯсО обозначим через \п\(Н) объединение всех связных компонент множества 5\Н, не содержащих внешней грани/0.

Определение. Будем говорить, что цикл С=У/е,у2е2-.-у* в плоском эйлеровом графе С имеет упорядоченное охватывание, если для любой его начальной части С,=У/е;У2е2...е,-, выполнено условие 1п(/С,)П Е- 0.

Сформулирована и доказана методом математической индукции теорема существования цикла с упорядоченным охватыванием.

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

Доказательство данной теоремы конструктивно и фактически сводится к описанию и доказательству результативности рекурсивного алгоритма А\ построения искомого цикла.

Алгоритм А1 реализован в виде компьютерной программы Е11Сус1е, в котором для представления заданного плоского графа б использовано задание для

каждого ребра ееЕ следующих функций: у,(е), у2(<?) - вершины, инцидентные ребру е\ 1{е), 1г(е) - ребра, следующие за е при его вращении против часовой стрелки вокруг вершин у,(е) и v2(e) соответственно. Иллюстрация введенных функций дана на рис. 1. Их построение не составляет проблем. Фактически они определяются и используются еще на этапе проектирования графа в.

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

Первая часть функции, соответствующая первой группе операторов do. . .while, предназначена для нахождения цикла из ребер, смежных внешней грани графа S(f), где f = G[First] .Vertexl. Данный цикл представляется заданием поля Mark для каждого его ребра.

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

Анализ сложности алгоритма А1 дает оценку 0([£|2).

I В четвертой главе решена задача построения маршрутов с упорядоченным

охватыванием для произвольного плоского графа G(V,E).

, В общем случае граф не является эйлеровым, поэтому невозможно построить

в нем замкнутый цикл. Для того чтобы получить замкнутый маршрут, покрывающий все ребра графа, необходимо некоторые ребра проходить дважды. В дальнейшем будем считать, что ребра, которые необходимо пройти дважды, дублируются дополнительными ребрами из множества F, так что граф G(V,£uF) остается плоским. Найти множество ребер, для которых требуются дубликаты можно с помощью подхода, аналогичного используемому для задачи китайского

почтальона. Очевидно, что в этом случае вычислительная сложность алгоритма может возрасти.

Построить маршрут с упорядоченным охватыванием Р в плоском неэйлеровом графе G можно за счет модификации алгоритма построения эйлерова цикла с упорядоченным охватыванием в модифицированном плоском эйлеровом графе б. Модификация алгоритма А\ состоит в следующем. В первой части алгоритма, когда требуется найти цикл из ребер подграфа, ограничивающих внешнюю грань текущего подграфа, возникает ситуация, когда только что помещенное в очередь Mark ребро указывает либо на само себя (висячая вершина текущей компоненты связности), либо это ребро не совпадает с начальным для данной компоненты связности, и указывает на уже помоченные ребра (мост). В обоих случаях необходимо продублировать только что пройденное ребро (в случае висячей вершины) или мост. Для этого необходимо ввести дополнительное ребро, что повлечет за собой изменение указателей, проиллюстрированное на рис. 2а для висячей вершины и на рис. 26 для моста.

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

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

Все сказанное выше обобщено в виде следующей теоремы.

Теорема 2. Маршрут, построенный в плоском графе с помощью алгорита В является маршрутом с упорядоченным охватыванием. Вычислительная сложность алгоритма не превосходит величины 0(|£|2).

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

Выполнение алгоритма А2 для плоского графа, представленного списком ребер с заданными на нем функциями ^ (), Ь 0, Л 0, к=1,2, можно разбить на три этапа: «Инициализация»; «Упорядочение»; «Формирование».

Начало каждого этапа в тексте алгоритма помечено соответствующей меткой. На этапах «Инициализация» и «Упорядочение» алгоритм использует процедуру Ю}РЬАСЕ(), которая переопределяет введенные функции у,(), 1к(), /40, к = 1,2, таким образом, чтобы движение по ребру ее Е в построенном алгоритмом цикле происходило бы от вершины у2(е) к вершине у,(е). Легко заметить, что данное переопределение, если оно необходимо, сводится к замене у функций уД), Ц)< АО, к=1,2 индекса к на индекс Ъ-к.

В зависимости от того, каким оператором определено последнее значение функции тагк(е) на ребре ее Е, будем различать четыре состояния ребра: непомеченное, М1-помеченное, М2-помеченное и МЗ-помеченное.

На этапе «Инициализация» присваиваются начальные значения 5(у) = 0, уе V, тагк(е) = 00, ее Е, а также определяется ребро еае Е, принадлежащее границе внешней грани /0. Функции на ребре е0 переопределяются таким образом, чтобы /,(е0) = /0, т.е. чтобы ребро ^(е0) принадлежало границе внешней грани.

АЛГОРИТМ »

Входят данные: C = (V,E) - плоский эйлеров граф Выходные данные: firsL6E, last6E, mark,(e): Е —» Е Инициализация:

(Vv€V) do Stack(v) = 0 od; (Ve£E) do

mark, (e) = mark2 (e) = °° ,- prev, (e) = prev2 (e) = 0 ;

od

first = last = e0; v0 = v = v,(e0)ne = l,(e0); /* ¡1 = 1; kmark(e0) Упорядочение < «Ы1е {first *<*>) do «bile (mark,(ne) = °° and to * ne) do Mli /* kmark(ne)-k */ mark, (last) = лг

if ( V2(ne) * V ) REPLACE ( n€ ) ;

v = v, (ne) ; tot = ne; ne-l, (ne);

od

e = first; _/?rsf = mark,(first) ; v = v2(e); ne = l2(e) ; H2: /* к = kmark(e)+\*/ mark,(e) = Stack(v,(e)) ,• mark2(e) = Stack(y) if (mart,(e)*0) do

if (v,(e) = v,(marfc,(e)) ) prev,(mark,(e)) = e else prev2 (mark, (e)) = e ;

od

if ( rnark2(e) Ф 0 ) do /*Помещение ребра в стеки вершин V,(e) и v2(e) */ if {v-v{(mark2(e))) prev,(mark2(e)) = e ; el»e prev2(mark2(e)) = e;

od

Stack(v) = e; Stack(v, (e))=e ■,

od

Формирование:

v = v0; e = Stack(v); ./¡Г5/ = last = e ,-do

if ( V, (e) = V ) REPLACE ( e ) ;

Stack(v)-mark2(e) ; /*Извлечение ребра из стека вершины v2(e) */ if ( v = v,(mark2(e))) prev,(mark2(e)) = 0; else prev2(mark2(e)) = 0,-v = v,(e),-if (prev,(e)*0)

if (e = mark,(prev,(e)) ) mark,(prev,(e)) = mark,(e) ; else mar&2 (prev, (e)) = mari, (e) •lee do

Stack(v) - mark, (e) ;

if (v = v,(mari,(e))) рггу, (тег*, (г)) = 0else prev2(mark,(e)) =0 ,•

e = Stack(v) ; /*Извлечение ребра из стека вершины V,(e) */

из: mark, (last) = е last = е ;

od while (last Ф 0 ) ; end.

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

Очередь Ml-помеченных ребер инициализируется как состоящая из единственного ребра е0. Переменные first и last используются для указания соответственно первого и последнего элементов очереди. Переменная пе используется для определения следующего кандидата для включения в список Ml-помеченных ребер. Переменная v0 используется для запоминания вершины, принадлежащей границе внешней грани, а переменная v - как текущая вершина для задания ориентации ребра, определяемого пе.

Этап «Упорядочение» выполняется следующим образом. На первой стадии в очередь Ml-помеченных ребер вводятся все ребра ее Е, ограничивающие внешнюю грань /0, а их ориентация задается так, чтобы /,(<?) = /0. На стадии к +1 каждое ребро ее Е, попавшее в очередь Ml-помеченных на стадии к, переводится в состояние М2-помеченного и помещается в стек вершины v2(e), а в очередь Ml-помеченных включаются все непомеченные ребра, ограничивающие грани, общие с выводимыми на данной стадии ребрами.

Для анализа результативности данного этапа использованы переменная к как счетчик стадий и функция hnarkQ: Е—> N, указывающая номер стадии, на которой ребро ставится в очередь Ml -помеченных ребер. В тексте алгоритма А2 (см. рис.3) операторы, определяющие значения к и kmarkQ, включены в скобки комментария /*...*/.

Положим также

Et = {ее Е:ктагк(е) = к], {7,(е),~г(е):ее £},

Е[ = {ее Е: ктагк(е)<к) , А'к = :ее £А'},

~Щ = Е\Е"к.

Пусть G(E') - плоский граф, порожденный множеством ребер Е'\Е, a G'(A) -орграф, порожденный множеством дуг А.

Лемма 1. Для любого Jt = 1,2,3,..., Af, где м - шах ктагк(е), имеют место следующие утверждения:

1. int(£t)эEj; S\int(£t)^>Е[\

2. G(Et ) - есть объединение реберно непересекающихся циклов;

3. G\\) - есть орграф, представляющий объединение непересекающихся по дугам орциклов.

Лемма 2. Если М = max ктагк(е), то Еи = 0.

В соответствии с описанием на этапе "Формирование" алгоритм строит максимальную по включению цепь

C = W2e2v3...etvi+,

е, = arg max kmark(e), v,., = v, (e,), / = 1,2.....L,

которая удовлетворяет также следующим условиям:

a) vi = vo _ вершина, ограничивающая внешнюю грань, найденная на этапе "Инициализация";

b) для любой начальной части

С, =vlelv2e2...en 1<L

и для любой вершины veV имеет место неравенство 1

min ктагк(е) > max ктагк(е).

Из эйлеровости орграфа G* следует, что С является циклом. Очевидно, что цикл содержит все ребра, инцидентные вершине v,, следовательно, и всем вершинам, принадлежащим границе внешней грани.

Лемма 3. Для любых z = l,2,..„L и it = 1,2,имеет место равенство im(C,)f]Et=0.

Теорема 3. Если G(V,E) - плоский эйлеров граф с множеством граней F, заданными на Е функциями vt :V ~уЕ, lk:E->E, fk:F->E, к=1,2, то алгоритм Ä2 находит в G эйлеров цикл с упорядоченным охватыванием. При завершении алгоритма переменные first и last определяют первое и последнее ребра найденного цикла, значение функции тагк(е) - ребро, следующее за ребром ее Е в найденном цикле. Вычислительная сложность алгоритма не превосходит величины 0(|£|).

На основе алгоритма А2 разработан алгоритм В2 построения в плоском гра- * фе, такой последовательности цепей, покрывающих все его ребра таким образом, что внутренние грани любой из этих цепей не пересекаются с ребрами последующих цепей. Фактически алгоритм В2 представляет модификацию алгоритма А2 и состоит из тех же этапов: «Инициализация», «Упорядочение», «Формирование». Первые два этапа повторяют соответствующие этапы алгоритма А2. Перед этапом «Формирование» выполняется сортировка вершин нечетной степени ve odd(V(G)) в порядке возрастания величины kmark(Stack(v)). На этапе «Формирование» алгоритм В2 вызывает две функции: FormOddiy) (построение про-

стой цепи между двумя вершинами нечетной степени) и Гогт(у). Вычисли 1ель-ная сложность алгоритма не более 0(\Е\).

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

В ЗАКЛЮЧЕНИИ перечислены основные результаты работы:

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

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

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

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

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

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

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

Основное содержение диссертации опубликовано в следующих работах:

1 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.

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

3. 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. Volume 1, Ufa State Technical University, 2003. -P. 134-138.

4. Panioukova T.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 - Greece / Documents of the Contest-:European Commission, Brussels, Belgium. - 130 p., with ill.-P. 53.

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

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

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

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

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

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

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

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

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

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

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

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

11. Панюкова Т.А. Рекурсивный алгоритм построения обходов с упорядоченным охватыванием в плоских неэйлеровых графах // Материалы VIII Международного семинара «Дискретная математика и ее приложения» (2-6 февраля, 2004 г.). - М.: Изд-во механико-математического факультета МГУ, 2004.-444 е. - С. 351-353.

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

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

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" "«•■енвияИД N 00510 от 01.12.99 г. Подшйшо к печати 16 02.2006 г. Формат 60x90 1/16. Усл.печл. 1,25. Тираж 100 экз. Заказ 099. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Z> С? V'C'

К 5532

Введение.

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(\Е\).

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 е., ил.