Введение
Глава 1. Применение графов в математическом моде лировании систем управления 27
1.1. Основные понятия и определения 28
1.2. Маршруты в графах 33
1.3. Разложения графов на цепи 38
1.4. Алгоритмы построения эйлеровых циклов без огра
ничений на порядок обхода ребер 43
Глава 2. Маршруты с локальными ограничениями 53
2.1. Алгоритм построения допустимой цепи 54
2.2. Алгоритм построения допустимой эйлеровой цепи 64
2.3. Покрытие графа допустимыми цепями 76
Глава 3. Маршруты с упорядоченным охватыванием 81
3.1. Представление плоского графа 84
3.2. Существование эйлеровых ОЕ-циклов 86
3.3. Рекурсивный алгоритм построения эйлеровых ОЕ циклов 89
3.4. Результативность рекурсивного алгоритма 93
3.5. Нерекурсивный алгоритм построения эйлерова
ОЕ -цикла 96
3.6. Эффективный алгоритм построения ОЕ -маршрута в произвольном связном плоском графе 111
3.6.1. ОЕ -маршрут китайского почтальона 111
3.6.2. Задача построения покрытия
с упорядоченным охватыванием 120
3.7. Оптимальное покрытие плоского графа последовательностью ОЕ -цепей 130
3.8. Построение Oi -покрытия
для многосвязного графа 136
Глава 4. AOi -маршруты 144
4.1. О существовании системы переходов, допускающей АОЕ-цеиь 147
4.2. АОЕ-цеїт для 4-регулярных графов 148
4.2.1. Пример 152
4.3. О числе эйлеровых ОЕ -цепей для заданной систе мы переходов 154
4.3.1. Число ОЕ -цепей для системы переходов, соответствующей А-цепи 157
4.3.2. Число ОЕ -цепей для непересекающейся системы переходов 160
4.3.3. Необходимое условие существования ОЕ -цепи для фиксированной системы переходов 162
4.3.4. Некоторые замечания и критерии 169
Глава 5. Программное обеспечение для построения ОЕ-цепей и Oi -покрытий 172
5.1. Программное обеспечение задачи построения эйлерова ОЕ -цикла 173
5.1.1. Рекурсивный алгоритм построения эйлерова ОЕ -цикла 173
5.1.2. ОЕ -маршрут китайского почтальона 178
5.1.3. Эффективный алгоритм построения покрытия 181
5.2. Программное обеспечение для построения ОЕ -покрытия несвязного графа 183
5.3. Алгоритм тестирования. Критерий соответствия цепи условию упорядоченного охватывания 186
5.4. Программа для построения АОЕ-цеїт 189
Глава 6. О возможных практических приложениях решаемой задачи 192
6.1. Задача прямоугольного раскроя и ОЕ -покрытия 198
6.1.1. Алгоритмы для кодирования раскройного плана 200
6.1.2. Выбор оптимальной укладки деталей 206
Выводы и основные результаты 210
Литература
