Введение
Глава 1. Теоретико-графовая модель задачи проектирования оросительных сетей и оценки ее сложности 22
1.1. Содержательное описание задачи и соответствующая теоретико-графовая модель 22
1.2. Общая постановка векторной задачи об остовных деревьях 25
1.2.1. Топологические критерии оптимизации векторных задач об остовных деревьях 26
1.3. Оценка вычислительной сложности задачи об остовных деревьях 27
Глава 2. Алгоритмы с оценками для векторной задачи об остовных деревьях 30
2.1. Математическая постановка проблемы 30
2.2. Описание алгоритма аъ 31
2.3. Вероятностный анализ алгоритма аъ 34
2.4. Вероятностный анализ применения алгоритма а2 к множеству M{n,R,A) 41
2.5. Статистически эффективный алгоритм а0 45
2.6. Обоснование условий статистической эффективности алгоритма а0 .47
Глава 3. Интервальные задачи об остовных деревьях и их неразрешимость с помощью алгоритмов линейной свертки 53
3.1. Отображение неопределенности значений параметров моделей средствами интервальной математики 53
3.2. Сведение интервальной задачи к задаче многокритериальной оптимизации 56
3.3. Неразрешимость интервальных задач с помощью алгоритма линейной свертки 56
Глава 4. Полиномиально разрешимый класс задач об остовных деревьях с топологическим критерием 62
4.1. Математическая постановка задачи об остовных деревьях 62
4.2. Полиномиальная разрешимость однокритериальных задач об остовных деревьяях с топологическими критериями 62
4.3. Полиномиальная разрешимость 2-критериальных задач, в которых один критерий является топологическим 64
Глава 5. Математическая модель водопользования на гиперграфах с интервальными данными 69
5.1. Основные определения теории гиперграфов 69
5.2. Математическая постановка задачи 70
5.3. Сведение задачи с интервальными данными к многокритериальной задачи 74
5.4. Сведение задачи на гиперграфе к задаче на графе 78
5.5. Оценки вычислительной сложности исследуемых задач 81
5.6. Полиномиально разрешимые постановки 84
5.7. Исследование «задачи 3» 86
5.8. Иллюстративный пример решения конкретной 2-критериальной задачи водопользования 92
Заключение 95
Литература 96
Приложения 105
