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

• Автор: Панюкова, Татьяна Анатольевна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Челябинск
• Количество страниц: 127 с. : ил.

Оглавление
Введение.

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. Программное обеспечение задачи построения эйлерова цикла с
упорядоченным охватыванием
Основные результаты и выводы
4. Построение маршрутов с упорядоченным охватыванием в плоских графах
4.1. Модификация рекурсивного алгоритма.
4.2. Примеры использования алгоритма для плоских графов.
Ф Основные результаты и выводы
5. Эффективные алгоритмы для построения маршрутов с упорядоченным охватыванием
5.1. Описание алгоритма.
5.2. Построение покрытия плоского графа последовательностью маршрутов с упорядоченным охватыванием
5.3. Примеры использования алгоритмов.
Выводы
6. О возможных практических приложениях решаемой задачи
Заключение.
Литература


Структура и объем работы. Диссертация состоит из введения, шести глав, заключения, списка использованной литературы ( наименований) и 4 приложений. Приложения включают тексты программ и свидетельства об их регистрации. Основная часть работы содержит страниц машинописного текста, иллюстраций. В первой главе на основе аналитического обзора литературы, отражающего состояние проблемы применения графов в математическом моделировании, показано место решаемой в данной работе задачи относительно задач, ранее опубликованных в научной литературе. С тем, чтобы более четко очертить круг решаемых в данной работе задач и показать их место в общей теории графов, приведна историческая справка и краткое описание постановки задачи нахождения эйлеровых (обход по всем ребрам ровно по одному разу с возвратом в исходную вершину) и гамильтоновых циклов (обход по всем вершинам ровно по одному разу с возвратом в исходную). Описаны изветные классические алгоритмы построения эйлеровых цепей: алгоритм расщепления, алгоритм Хейерхольцера и алгоритм Такера. Отмечено, что описанные выше алгоритмы находят в графе произвольную эйлерову цепь, на которую не наложено никаких ограничений. А-цепи; прямолинейные цепи), и на глобальные (маршруты Петри, бинаправленные двойные обходы и т. Анализ публикаций показал, что большинство работ посвящено алгоритмам с локальными ограничениями на порядок обхода ребер (например, запрещение левых поворотов; маршруты без поворотов; использование в каждой вершине графа заданного циклического порядка включения ребер в маршрут и т. Обобщение большинства частных случаев задачи построения маршрутов с локальными ограничениями дано С. Зейдером []. Им предложено представлять локальные ограничения в каждой вершине V исходного графа С в виде грфа С? Множеством вершин графа С^у) являются все ребра, инцидентные вершине г; смежные вершины графа С^у) соответствуют разрешенным переходам. Показано, что если все графы допустимых переходов являются полными многодольными графами либо паросочетаниями, то соответствующая задача построения допустимой простой цени между заданными вершинами разрешима за линейное время. В противном случае данная задача является МР-трудной. Отметим, что открытым остался вопрос распознавания мпогодолыюсти графов у), а также проблема построения допустимого маршрута или множества маршрутов, покрывающих все ребра исходного графа. Среди публикаций, посвященных задачам маршрутизации с глобальными ограничениями, не удалось найти каких-либо результатов о маршрутах с запрещенными последовательностями ребер. Во второй главе проанализированы задачи построения допустимого маршрута или множества маршрутов, покрывающих все ребра исходного графа. Предполагается, что ограничения на маршруты удовлетворяют условиям теоремы С. Зейдера []. Отмечена связь графов переходов с понятием системы разбиения графа, используемой Г. Фляйшнсром []. С.Зейдера и алгоритм /^СОВМЕСТИМЫЙ ПУТЬ для построения допустимого пути. Сложность алгоритмов не превосходит величины 0(Е), где Е - число ребер графа С. Приведены примеры использования построенных алгоритмов. Построен также алгоритм Р^-СОВМЕСТИМЫЕ МАРШРУТЫ для нахождения эйлерова покрытия графа в допустимыми маршрутами. Алгоритм является рекурсивным и имеет вычислительную сложность 0(ЕЩ). ЭВМ и могут быть использованы для решения ряда практических задач. Однако, наложенные на порядок обхода ограничения носят локальный характер, т. Поэтому открытой остается задача построения маршрутов с ограничениями на использование в маршрутах более длинных последовательностей ребер. В третьей главе поставлена и решена задача построения в плоском эйлеровом графе эйлеровых циклов, удовлетворяющих условию отсутствия пересечения внутренних граней любой его начальной части с ребрами его оставшейся части. Сформулирована и доказана теорема существования цикла с упорядоченным охватыванисм. Доказательство данной теоремы конструктивно и фактически сводится к описанию и доказательству результативности рекурсивного алгоритма А1 построения искомого цикла.