Содержание к диссертации
Введение
1. Применение графов в математическом моделировании систем управления 13
1.1. Основные понятия и определения 13
1.1.1. Обыкновенные графы 13
1.1.2. Мультиграфы 14
1.1.3. Топологические графы 15
1.2. Маршруты в графах 17
1.2.1. Эйлеровы циклы. Задача о Кенигсбергских мостах 18
1.2.2. Гамильтоновы циклы. Задача коммивояжера 19
1.3. Разложения графов на цепи 21
1.4. Алгоритмы построения эйлеровых циклов 23
1.5. Алгоритм построения допустимой цепи 28
Выводы 34
2. Построение множества допустимых маршрутов, покрывающих граф 36
2.1. Система разбиения 36
2.2. Алгоритм построения допустимой эйлеровой цепи 38
2.3. Алгоритм построения покрытия допустимыми цепями 40
Выводы 43
3. Эйлеровы циклы с упорядоченным охватыванием 44
3.1. Определение и пример 44
3.2. Существование решения 45
3.3. Рекурсивный алгоритм построения эйлерова цикла с упорядоченным охватыванием 47
3.4. Программное обеспечение задачи построения эйлерова цикла с упорядоченным охватыванием 50
Основные результаты и выводы 54
4. Построение маршрутов с упорядоченным охватыванием в плоских графах 55
4.1. Модификация рекурсивного алгоритма 55
4.2. Примеры использования алгоритма для плоских графов 61
Основные результаты и выводы 65
5. Эффективные алгоритмы для построения маршрутов с упорядоченным охватыванием 66
5.1. Описание алгоритма 66
5.2. Построение покрытия плоского графа последовательностью маршрутов с упорядоченным охватыванием 76
5.3. Примеры использования алгоритмов 80
Выводы 84
6. О возможных практических приложениях решаемой задачи... 85
Заключение 90
Литература
- Эйлеровы циклы. Задача о Кенигсбергских мостах
- Алгоритм построения допустимой эйлеровой цепи
- Примеры использования алгоритма для плоских графов
- Построение покрытия плоского графа последовательностью маршрутов с упорядоченным охватыванием
Введение к работе
Дискретная математика развивалась в связи с изучением законов и правил человеческого мышления, что и обусловило ее применение в тех областях техники, которые так или иначе связаны с моделированием мышления, и в первую очередь в вычислительной технике и программировании [19].
Теория графов - важный раздел современной дискретной математики, как с точки зрения внутренних стимулов ее развития, так и для разнообразных приложений. Практическая роль теории графов особенно возросла во второй половине 20-го века в связи с проектированием различных АСУ и вычислительных устройств дискретного действия. В теоретическом же плане, помимо давнишних связей с комбинаторной топологией и геометрией, наметились существенные сдвиги на стыке теории графов с алгеброй, математической логикой, лингвистикой, теорией игр, общей теорией систем [24] и др.
Известно, что первой работой теории графов как математической дисциплины считается статья Эйлера (1736 г.), в которой рассматривалась задача о Кё-нигсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Следующий импульс теория графов получила лишь спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.
В настоящее время интенсивно развивается раздел теории графов, касающийся построения маршрутов, удовлетворяющих специальным ограничениям: эйлеровы и гамильтоновы циклы; маршруты, избегающие запрещенных переходов; самонепересекающиеся и непересекающиеся цепи; бинаправленные двойные обходы и т.д.
Интерес к задачам маршрутизации объясняется их использованием в качестве математических моделей многих проблем управления и автоматизации проектирования. В частности, в автоматизированной системе технологической подготовки процессов раскроя листового материала математической моделью рас кройного плана является плоский граф. Целью моделирования является определение такой кратчайшей траектории режущего инструмента, чтобы отрезанная от листа часть не требовала дополнительных разрезаний. Однако для решения данной проблемы отсутствуют соответствующая формальная постановка в терминах задачи построения маршрута в плоском графе и, как следствие, эффективные алгоритмы определения рациональных траекторий.
Одной из работ по специальным вопросам эйлеровых графов является монография Г.Фляшнера «Эйлеровы графы и смежные вопросы» [3,46], где систематизировано и достаточно подробно рассмотрены некоторые виды эйлеровых цепей, например, цепи, не содержащие запрещенных переходов, попарно-совместимые эйлеровы цепи, А -цепи в графах.
Имеется ряд журнальных публикаций других авторов, в которых также рассматриваются задачи, посвященные эйлеровым цепям специального вида, например, расширение класса запрещенных переходов [14], самонепересекающиеся и непересекающиеся цепи, бинаправленные двойные обходы [3,46], маршруты Петри [17], прямолинейные маршруты [12], реберно-упорядоченные маршруты [2] и т.д.
Целью диссертационного исследования является постановка и исследование задач маршрутизации специального вида в плоских графах, являющихся математическими моделями проблем управления и проектирования. Для достижения поставленной цели были поставлены и решались следующие задачи.
1. Аналитический обзор научной литературы по проблеме построения в графах маршрутов специального вида. Классификация существующих задач маршрутизации и методов их решения.
2. Формальная постановка ряда задач управления робототехническими комплексами в виде задачи построения маршрутов специального вида.
3. Анализ полученных задач, разработка алгоритмов их решения, анализ разработанных алгоритмов.
4. Программная реализация разработанных алгоритмов
Научная новизна полученных в диссертации результатов заключается в следующем:
• Введен класс С маршрутов в плоских графах. Маршруты введенного класса удовлетворяют требованию отсутствия пересечения внутренних граней пройденной части маршрута с ребрами его непройденной части.
• Доказано, что плоские эйлеровы графы имеют эйлеровы циклы, принадлежащие классу С.
• Разработаны алгоритмы А1 и А2 нахождения в плоском эйлеровом графе G=(V,E) эйлеровых циклов введенного класса, имеющие вычислительную сложность 0(1 12) и 0(\Е\) соответственно.
• Разработан алгоритм построения в плоском графе маршрута, покрывающего все его ребра и принадлежащего классу С. Вычислительная сложность алгоритма не более 0(\Е\2).
• Разработан алгоритм построения в плоском графе, не содержащем висячих вершин, такой последовательности цепей, покрывающих все его ребра и принадлежащих классу С, что внутренние грани любой из этих цепей не пересе-каются с реберами последующих цепей. Вычислительная сложность алгоритма не более 0(Е).
Практическая ценность. Расширен класс задач построения маршрутов специального вида. Предложены эффективные алгоритмы построения таких маршрутов. Использование разработанных алгоритмов, например, в системах технологической подготовки процессов раскроя, позволит значительно повысить эффективность использования оборудования. Новизна и результативность предложенных алгоритмов подтверждены сви детельствами о регистрации программ в РоСАПО.
Апробация работы. Результаты исследований докладывались и обсуждались на следующих конференциях:
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. Молодежная конференция «Проблемы теоретической и прикладной математики», Екатеринбург, ИММ, УрО РАН, 30 января - 4 февраля, 2005 г.
Кроме того, результаты работы были представлены на ежегодных научно-практических конференциях Южно-Уральского государственного университета.
Публикации. По материалам проведенных исследований опубликовано 19 печатных работ, в числе которых 2 свидетельства о регистрации программного продукта.
Структура и объем работы. Диссертация состоит из введения, шести глав, заключения, списка использованной литературы (46 наименований) и 4 приложений. Приложения включают тексты программ и свидетельства об их регистрации. Основная часть работы содержит 95 страниц машинописного текста, 35 иллюстраций.
В первой главе на основе аналитического обзора литературы, отражающего состояние проблемы применения графов в математическом моделировании, показано место решаемой в данной работе задачи относительно задач, ранее опубликованных в научной литературе.
С тем, чтобы более четко очертить круг решаемых в данной работе задач и показать их место в общей теории графов, приведна историческая справка и краткое описание постановки задачи нахождения эйлеровых (обход по всем ребрам ровно по одному разу с возвратом в исходную вершину) и гамильтоновых циклов (обход по всем вершинам ровно по одному разу с возвратом в исходную).
Описаны извстные классические алгоритмы построения эйлеровых цепей: алгоритм расщепления, алгоритм Хейерхольцера и алгоритм Такера. Отмечено, что описанные выше алгоритмы находят в графе произвольную эйлерову цепь, на которую не наложено никаких ограничений.
Результаты анализа ограничений различных задач маршрутизации дают возможность классифицировать их на локальные, когда следующее ребро в маршруте определяется условиями, заданными в текущей вершине или на текущем ребре (цепи, избегающие запрещенных переходов; А-цепи; прямолинейные цепи), и на глобальные (маршруты Петри, бинаправленные двойные обходы и т.п.).
Анализ публикаций показал, что большинство работ посвящено алгоритмам с локальными ограничениями на порядок обхода ребер (например, запрещение левых поворотов; маршруты без поворотов; использование в каждой вершине графа заданного циклического порядка включения ребер в маршрут и т.п.).
Обобщение большинства частных случаев задачи построения маршрутов с локальными ограничениями дано С.Зейдером [14]. Им предложено представлять локальные ограничения в каждой вершине v исходного графа G в виде грфа GE(V) возможных переходов. Множеством вершин графа G v) являются все ребра, инцидентные вершине v; смежные вершины графа Gb{v) соответствуют разрешенным переходам. Показано, что если все графы допустимых переходов являются полными многодольными графами либо паросочетаниями, то соответствующая задача построения допустимой простой цепи между заданными вершинами разрешима за линейное время. В противном случае данная задача является TVP-трудной.
Отметим, что открытым остался вопрос распознавания многодольности графов GE(V), а также проблема построения допустимого маршрута или множества маршрутов, покрывающих все ребра исходного графа.
Среди публикаций, посвященных задачам маршрутизации с глобальными ограничениями, не удалось найти каких-либо результатов о маршрутах с запрещенными последовательностями ребер.
Во второй главе проанализированы задачи построения допустимого маршрута или множества маршрутов, покрывающих все ребра исходного графа. Предполагается, что ограничения на маршруты удовлетворяют условиям теоремы С.Зейдера [14]. Отмечена связь графов переходов с понятием системы разбиения графа, используемой Г.Фляйшнером [46]. На основе установленной связи построен алгоритм РАЗМЕТКА для распознавания выполнения условий теоремы С.Зейдера и алгоритм Рс-СОВМЕСТИМЫЙ ПУТЬ для построения допустимого пути. Сложность алгоритмов не превосходит величины 0(,), где Е - число ребер графа G. Приведены примеры использования построенных алгоритмов.
Заметим, что с помощью алгоритма нахождения PQ -совместимого пути возможно построение только простой цепи между двумя различными вершинами (т.е. цепь, в которой любая ее вершина встречается в ней ровно один раз).
Построен также алгоритм Рс-СОВМЕСТИМЫЕ МАРШРУТЫ для нахождения эйлерова покрытия графа G допустимыми маршрутами. Алгоритм является рекурсивным и имеет вычислительную сложность 0( - Vp.
Алгоритмы, рассмотренные во второй главе, имеют самостоятетьный теоретический интерес, легко реализуются на ЭВМ и могут быть использованы для решения ряда практических задач. Однако, наложенные на порядок обхода ограничения носят локальный характер, т.е. присутствуют ограничения на последовательности из двух ребер, инцидентных общей вершине. Поэтому открытой остается задача построения маршрутов с ограничениями на использование в маршрутах более длинных последовательностей ребер. По-видимому, алгоритмы решения таких задач должны существенным образом использовать их специфику.
В третьей главе поставлена и решена задача построения в плоском эйлеровом графе эйлеровых циклов, удовлетворяющих условию отсутствия пересечения внутренних граней любой его начальной части с ребрами его оставшейся части. Формально такие циклы определены как циклы с v -упорядоченным охва-тыванием, где v - вершина, инцидентная внешней (бесконечной) грани графа.
Сформулирована и доказана теорема существования цикла с упорядоченным охватыванием. Доказательство данной теоремы конструктивно и фактически сводится к описанию и доказательству результативности рекурсивного алгоритма А1 построения искомого цикла.
Алгоритм А1 реализован в виде компьютерной программы EUCycle, в котором для представления заданного плоского графа G использовано задание для каждого ребра ееЕ следующих функций: v,0), v2(e) - вершины, инцидентные ребру е; /, (е), 12 (е) - ребра, следующие за е при его вращении против часовой стрелки вокруг вершин v,(e) и v2(e) соответственно.
Анализ сложности алгоритма А1 дает оценку 0(Е2).
В четвертой главе решена задача построения маршрутов с упорядоченным охватыванием для произвольного плоского графа G(V, Е).
В общем случае граф не является эйлеровым, поэтому невозможно построить в нем замкнутый цикл. Для того чтобы получить замкнутый маршрут, необходимо некоторые ребра проходить дважды. В дальнейшем принято, что ребра, которые необходимо пройти дважды, дублируются дополнительными ребрами из множества F таким образом, что граф G(V,uF) остается плоским. Найти множество ребер, для которых требуются дубликаты, можно с помощью подхода, аналогичного используемому для задачи китайского почтальона. Очевидно, что в этом случае вычислительная сложность алгоритма может возрасти.
Показано, что построить маршрут с упорядоченным охватыванием Р в плоском неэйлеровом графе G можно за счет модификации алгоритма построения эйлерова цикла с упорядоченным охватыванием в модифицированном плоском эйлеровом графе G.
Маршрут, построенный в плоском графе с помощью модифицированного алгоритма, является маршрутом с упорядоченным охватыванием. Вычислительная сложность алгоритма не превосходит величины 0( ).
В пятой главе рассматриваются вопросы, связанные с повышением эффективности алгоритмов построения в плоском графе маршрутов с упорядоченным охватыванием. Резерв для повышения эффективности дает отказ от использования рекурсии и формирование алгоритма А2, не содержащего рекурсию в чистом виде.
Показано, что если G(V,E) - плоский эйлеров граф с множеством граней F, заданными на Е функциями vk\V- E, lt:E- E, fk:F-$E, = 1,2, то алгоритм А2 находит в G эйлеров цикл с упорядоченным охватыванием. При завершении алгоритма переменные first и last определяют первое и последнее ребра найденного цикла, значение функции тагк(ё) - ребро, следующее за ребром ее Е в найденном цикле. Вычислительная сложность алгоритма А2 не превосходит величины 0(\Е\).
На основе алгоритма А2 разработан алгоритм В2 построения в плоском графе, не содержащем висячих вершин, такой последовательности цепей, покрывающих все его ребра и принадлежащих классу С, что внутренние грани любой из этих цепей не пересекаются с ребрами последующих цепей. Вычислительная сложность алгоритма не более 0().
В шестой главе описаны некоторые из возможных практических приложений решаемой задачи.
В заключении перечислены основные результаты работы.
Работа выполнялась в соответствии с планами госбюджетных НИР ЮУрГУ (номер гос. регистрации 01.2001 05137). Работа поддерживалась грантами РФФИ «Урал» (проект 01-01-96401), Губернаторским грантом Челябинской области р2001урчел-01-04 и грантами губернатора Челябинской области для студентов, аспирантов и молодых ученых в 2002 и 2003 гг.
Эйлеровы циклы. Задача о Кенигсбергских мостах
Задача Эйлера впервые упоминалась в его мемуаре в 1736 г. Оригинальный текст статьи и ее перевод приведены в [46]. Мемуар был представлен в 1736 г. Санкт-Петербургской академии наук, в котором содержался ответ на широко обсуждавшийся тогда вопрос: можно ли совершить прогулку по Кенигсбергу таким образом, чтобы, выйдя из произвольного пункта, пройти ровно один раз по каждому из городских мостов и вернуться в исходный пункт [26].
Город Кенигсберг (ныне Калининград) стоит близ устья реки Преголь (ныне Преголя); река огибает остров Кнейпхоф (рис. 1.2). В XVIII веке в городе было семь мостов, расположенных так, как показано на рисунке. Эйлер писал: «Конечно, можно решить кенигсбергскую задачу о семи мостах, составив полный список всех маршрутов, какие только можно себе представить, и тогда станет ясно, годится ли некоторый маршрут или такого маршрута нет. Однако из-за боль шого числа комбинаций этот способ решения задачи представляется слишком трудным и громоздким» [43].
Формализация задачи вылядела следующим образом: каждый берег реки и острова будем считать вершиной графа, а каждый мост - ребром. Тогда карту, представленную на рис. 1.2, можно представить в виде графа, изображенного на рис. 1.3. Каждому острову и участку суши в соответствие ставится вершина, каждому мосту - ребро. В результате формализации получаем связный граф с четырьмя вершинами и семью ребрами.
Ответ на поставленный в задаче вопрос зависит от существования эйлерова цикла в этом графе. Эйлер установил, что указанный граф не содержит эйлерова цикла, и этот результат ознаменовал рождение теории графов. Основная теорема о существовании эйлеровых циклов формулируется следующим образом [24].
Данная задача появилась не более чем на столетие позже задачи Эйлера. Га-мильтонова игра (так она называлась в 1884 г.) заключается в нахождении такого маршрута по ребрам правильного додекаэдра, который проходит ровно один раз через каждую вершину додекаэдра (рис. 1.4). Уильям Гамильтон, который изобрел эту игру, обозначал двадцать вершин додекаэдра буквами, которые симво лизировали названия разных городов. Тридцать ребер додекаэдра - все возможные пути между городами. Бытовой смысл задачи - объехать «весь мир», а именно: начиная от какого-либо города, побывать в каждом городе один и только один раз и вернуться в начальный пункт, причем задан порядок, в котором следует посетить первые п городов, где п 5 [21].
Если ребрам графа приписаны некоторые веса и граф содержит несколько гамильтоновых циклов, то большой интерес представляет также задача нахождения гамильтонова цикла с минимальным общим весом, названная задачей коммивояжера.
Представление о непосредственных применениях гамильтоновых цепей дает следующая ситуация [23]. Имеется машина и п заданий, каждое из которых она способна выполнить после соответствующей настройки. При этом необходимо затратить на переналадку tl} единиц времени для того, чтобы после выполнения і -го задания выполнить / -е. В предположении, что ,} = //Y, требуется найти последовательность выполнения заданий, при которой время каждой переналадки не превосходит величины t. Если построить граф G, у которого V = {1,2,...,«}, Рис. 1.4. Изображение графа, соответствующего додекаэдру, в виде укладки на плоскости E = {ij\ty }, то описанная задача сводится к отысканию гамильтоновой цепи в этом графе.
Алгоритм построения допустимой эйлеровой цепи
Как было отмечено в п. 1.5 алгоритм С.Зейдера в общем случае не позволяет строить допустимые цепи максимальной длины. Особый интерес представляют собой допустимые эйлеровы цепи.. Необходимое и достаточное условие существования PG -совместимых цепей дает следующая теорема [7]. Теорема 2.1 (А.Коциг). Связный эйлеров граф G имеет PG -совместимую эйлерову цепь тогда и только тогда, когда {\/veV)(\/pePG(v))(\p\ ±dG(v) .
Очевидно, что сложность проверки условия существования Рс-совместимой эйлеровой цепи не превосходит величины 0(Zi(G)). Ниже приведен алгоритм построения совместимой цепи.
Алгоритм 2.2 (PG -СОВМЕСТИМАЯ ЭЙЛЕРОВА ЦЕПЬ [31]). Входные данные: эйлеров граф G = (V, Е); система переходов PG{v) VVG V(G). Выходные данные: допустимый эйлеров цикл Gk+l. Шаг 1.Положить к = 0, Gk=G. Шаг 2. Найти вершину v, у которой dG (v) 2. Шаг 3. Найти класс С, є Рс (v): С, = {maxC С є Pat (v)}. Шаг 4. Найти любые ребра е,(у)є С, и e2(v)G (v) - С,. Если множество EG (v) - С, = 0, останов: PG -совместимой эйлеровой цепи не существует. В противном случае перейти на шаг 5. Шаг 5. Построить граф Gk+l, отщепив от вершины v вершину v , которой инцидентны только ребра ех и е2. Остальные ребра оставить инцидентными вершине v. Шаг 6. Пусть класс С2е PG (v) содержит ребро e2(v). Найти p-k(v):=PGk(v)-{CvC2}. Pc,Av)--=\ [ск. PGSv)U{Cx-{e,{v)},C2-{e2(v)}}, если С2 1, МІКС.- ДУ)}}, если С, С2 = 1, P"(v), если с, = С2 = 1, рс„= U 1,« xeV(GU2)
Шаг 7. Определить значение 0-(0 ,) = 2(1 (0 ,)1- (0 ,)1). Шаг 8. Если cr(Gk+l) 0, положить к = к + \, перейти на шаг 2, для графа Gk+l. В противном случае - останов: построенный граф GkH является эйлеровой цепью, не содержащей запрещенных переходов. Теорема 2.2. Алгоритм PG -СОВМЕСТИМАЯ ЭЙЛЕРОВА ЦЕПЬ корректно решает задачу построения P(G) -совместимой эйлеровой цепи.
Доказательство. Если для некоторого к, такого что С" є (v), выполнено неравенство c1 c;-{e,(v)}, то C"ePCtJv) и C2 C" = C, -dCt(v)-l = - Cui(v). На основании этого факта можно заключить, что c - iCti(v) для каждой вершины VEV(GM) И каждого класса CePC(i(v)cPCw. При этом величина &(GM)-\E(Gkn)\-\v(Gk+\}\ v k)- Если граф GM является циклом, то число ребер в нем и число вершин совпадают, т.е. в данном случае cr(Gi+1) = 0. Если же граф Gi+1 является цепью, то число вершин превышает число ребер на 2, следовательно, в данном случае a(Gk+l) = -2. Если же на некотором этапе для el(v)e Сх не удалось найти e2(v)e EG (v)-Cp это значит, что \Cx\ d{v)l2, т.е. не выполнены необходимые и достаточные условия существования эйлерова цикла (теорема 2.1). Из этих фактов следует корректность выполнения алгоритма. Теорема доказана.
Оценим вычислительную сложность предложенного алгоритма. Выполнения шагов 2, 5, 6 и 7 можно организовать с использованием не более (9(1) операций (за счет специальных структур данных). Выполнение же шагов 3 и 4 можно организовать с использованием не более 0(dG (v)) операций. Цикл алгоритма будет повторен не более чем cr(G) раз. В итоге имеем, что алгоритм потребует число операций не менее ( \ О Е dCt(yt) =0(\E(G)\-\V(G)\). \k=0,\...(T(G) J
Таким образом, приведенные алгоритмы разрешимы за полиномиальное время и могут быть легко реализованы с помощью стандартных вычислительных средств.
Примеры использования алгоритма для плоских графов
Приведем несколько примеров, демонстрирующих работу программы с неэйлеровыми графами. На рис.4.8 приведен простейший пример, когда граф содержит только две вершины нечетной степени (вершины 2 и 4) и они смежны одной грани. Euler CyclesConstructor 2.0 - ПЦ XI
Дополнительные ребра достраиваются красным цветом. Смысл, который вкладывается в дополнительные ребра, заложен на этапе конструирования модели (в терминах задачи раскроя они понимаются, например, как холостые проходы режущего инструмента), а не на этапе отыскания решения. В нижней части окна, как и в случае эйлерова графа, выводится найденный маршрут с заключенными в скобки номерами вершин, так как маршрут в данном случае содержит и дополнительные ребра.
Для графа с рис.4.8 в процессе выполнения алгоритма достраивается дополнительное ребро с номером 6, соединяющее вершины 2 и 4. Рассмотрим теперь пример графа, не имеющего ни одной вершины четной степени (см. рис.4.9).
Очевидно, что после пометки внешнего цикла из ребер 1, 3 и 6, остается подграф с тремя висячими вершинами. Чтобы получить внутренний цикл, необходимо достроить три дополнительных ребра 7, 8 и 9. Такое вспомогательное построение не является оптимальным по числу введенных ребер, т.к. для графа с четырьмя вершинами нечетной степени достаточно ввести два дополнительных ребра, для преобразования графа до эйлерова. Тем не менее, проведенное построение позволяет свести граф к эйлерову в процессе работы алгоритма В\.
Приведем более сложный пример (см. рис.4.10), для которого необходимо на втором уровне вложенности дублировать ребра-мосты. Euler Cycles Constructor 2.0
Заметим, что условие упорядоченного охватывания выполняется, так как дополнительные ребра являются недостающими звеньями во вложенных циклах, а т.к. полученный эйлеров граф имеет цикл с упорядоченным охватыванием, то и маршрут, в котором некоторые ребра заменяются фиктивным переходом из вершины в вершину, будет иметь упорядоченное охватывание.
Итак, мы рассмотрели несколько часто встречающихся на практике случаев с произвольными плоскими графами. Во всех этих случаях произведена оптимальная достройка исходного графа до эйлерова с помощью описанных выше функций и найден маршрут в исходном графе, удовлетворяющий условию упорядоченного охватывания.
Основные результаты и выводы
1. За счет дополнительных построений можно свести задачу построения маршрута с упорядоченным охватыванием в плоском графе к задаче построения цикла с упорядоченным охватыванием в плоском эйлеровом графе.
2. Построенный алгоритм ЛІ в результате проведенной модификации позволил разработь полиномиальный алгоритм В1 для нахождения обходов с упорядоченным охватыванием в произвольном плоском графе.
3. Разработанное программное обеспечение и проведенные вычислительные эксперименты подтверждают правильность приведенных выше выводов.
Построение покрытия плоского графа последовательностью маршрутов с упорядоченным охватыванием
Известно, что любой граф можно достроить до эйлерова добавлением п ребер, где 2п - число вершин нечетной степени. При условии сохранения планар-ности данного представления графа дополнительное построение из п ребер возможно лишь в случае, когда в графе найдется такое разбиение вершин нечетной степени на пары, что они попарно будут смежны одной грани. На рис.5.5 этому требованию удовлетворяют вершины v,, v2 и v3.
Для вершины v9 такой пары не существует, следовательно, для общего случая нужно искать другие решения.
В работе [25] был анонсирован следующий результат. Теорема 5.2. Пусть G = (V,E) - плоский граф на S. Существует множество ребер F: (F П S) W — 0 такое, что граф G = (V, Е U F) - эйлеров, и в гра л I I I I фе G существует эйлеров цикл С -vlelv2e2...envl, n = \E\+\F\, для любой начальной части которого Cl = v,e1v2e2...v/, / ZS + F, выполнено условие 1ш(С,)П = 0.
Фактически алгоритм 52 представляет модификацию алгоритма Л2 и состоит из тех же этапов: «Инициализация», «Упорядочение», «Формирование». Первые два этапа повторяют соответствующие этапы алгоритма А2. Перед этапом «Формирование» выполняется сортировка вершин нечетной степени VG odd(V(G)) в порядке возрастания величины kmark(Stack(v)). На этапе «Формирование» алгоритм 52 вызывает две функции: FormOddiy) (рис. 5.6) и Form(v) (рис.5.7).
В соответствии с леммой 5.3 Int(C,)plE = 0, 1 = 1,2,...,к. Таким образом, построенная цепь удовлетворяет условию упорядоченного охватывания.
После того, как цепь C,=velvle2v2...el, 1 к сформирована, вершины v и vk удаляются из множества odd(V(G)). Если множество odd(V(G)) не пусто, то описанный процесс повторяется. В результате выполнения цикла while...do алгоритм строит последовательность цепей с упорядоченным охватыванием CQ =vexvxe2...ekvko,Cx =vxexvxe2...ekvk{,..., Cn-l=vn-lelvle2...ekn_vkii, в которой odd(V(G)) = {v,vkoy,vki,...,vn-l,vkJ, к (Vk 2n,\/l k) Int(JC )nC/=0.
После окончания этого цикла while...do выполняется функция Form(v0), где У0 - вершина, смежная внешней грани, которая строит цикл с упорядоченным охватыванием С, состоящий из ребер, не охваченных цепями С, і = 0,...,п-\.
Результативность алгоритма следует из способа построения функции ктагк{е) и леммы 5.3. Легко заметить, что вычислительная сложность алгоритма В2 такая же, как и у алгоритма А2, т.е. не более 9((G)) операций.
Как видно из полученной последовательности ребер, в первую очередь проходятся ребра, имеющие большие значения функции kmark(e). В отличие от рекурсивного алгоритма А1, для неркурсивного алгоритма А2 существуют примеры (рис.5.8), когда он не проходит по циклам на каждом уровне вложенности, а выбирает последовательность пройденных ребер по принципу «отрезания» циклов из ребер разного уровня вложенности. Несмотря на такой порядок обхода ребер, условие упорядоченного охватывания сохраняется, а сложность работы алгоритма А2 на порядок меньше сложности алгоритма А1.
В случае плоских неэйлеровых графов алгоритм В2 выполняет построение эйлеровой цепи с помощью тг-1 дополнительных построений, где к - число вершин нечетной степени. Дополнительные ребра отображаются красным цветом (см. рис. 5.9-5.11). После полученных дополнительных построений не обязательно модифицированный граф останется плоским (например, см. рис. 5.11). Легко видеть, что полученные с помощью алгоритма В2 эйлеровы цепи удовлетворяют условию упорядоченного охватывания.
