Введение
Глава 1. Задачи поиска гамильтоновых циклов экстремального реберного веса 20
1.1. Задачи коммивояжера в евклидовом пространстве 20
1.1.1. Постановка задачи 20
1.1.2. Алгоритм А. И. Сердюкова 20
1.1.3. Модифицированный алгоритм А 23
1.2. Задачи поиска двух реберно непересекающихся гамильтоновых циклов экстремального веса 28
1.2.1. Общая постановка задачи 28
1.2.2. Задача на максимум с одной весовой функцией 28
1.2.3. Метрическая задала на минимум с одной весовой функцией 37
1.2.4. Метрическая задача на минимум с двумя весовыми функциями 41
Глава 2. Задачи поиска связных подграфов с ограничениями на степени вершин 50
2.1. Задача поиска подграфа с заданными степенями вершин максимального реберного веса 50
2.1.1. Постановка задачи 50
2.1.2. Описание приближенного алгоритма 50
2.1.3. Анализ алгоритма 52
2.2. Задача поиска регулярного связного подграфа экстремального реберного веса 58
2.2.1. Постановка задачи 58
2.2.2. NP-трудность 58
2.2.3. Описание приближенного алгоритма решения задачи . 60
2.2.4. Вероятностный анализ алгоритма 65
2.2.5. Случай независимого равномерного распределения элементов матрицы расстояний 67
2.2.6. Случай минорирующей функции распределения элементов матрицы расстояний, заданных независимо 77
2.2.7. Некоторые обобщения 78
Глава 3. Задача разбиения множества векторов 80
3.1. Постановка задачи 80
3.2. Решения задачи в полиэдральном пространстве (Rk, с) с конечной нормой 80
3.3. Решение задачи в ft-мерном евклидовом пространстве 82
3.3.1. Области принадлежности решения 82
3.3.2. Описание алгоритма 86
Заключение 87
Список публикаций автора по теме диссертации 89
Благодарности 91
Литература 92
