Введение
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
Литература
