Введение к работе
І
Актуальность работы. Мощностная задача Штейнера на ориентированном градуированном графе служит моделью многих реальных проблем, возникающих в различных сферах хозяйственной дсятельности(см., например, [1)).
Исследуемая задача является частным случаем проблемы Штейнера на ориентированном графе, которую формулируют как обобщение широко известной проблемы Штейнера на неориентированном графе. Однако, общая задача Штейнера на орграфах мало исследовалась математиками. Она кратко упоминается в книге [2] (стр.221), формулируется в обзорах [3], [4], [5], посвященных,вообще говоря, задаче Штейнера на неориентированном графе. Имеются статьи [6], [7], [8), [9], [10] о задаче Штейнера на орграфе, и статья [11] для орграфа без контуров. Во всех этих работах предлагается решать задачу методом целочисленного программирования, т.е. путем минимизации целевой функции с ограничениями в виде системы линейных уравнений и неравенств с целыми коэффициентами, переменные которых принимают значения 0 или 1. Нами был выбрап подход исследования рассматриваемой задачи непосредственно на графе.
Цель работы. Применить для решения мощностной задачи Штейнера на ориентированном градуированном графе весь спектр методов, использующихся для исследования NP-трудных задач на графах.
Научная новизна.
В диссертации впервые рассмотрена задача, названная мощностной задачей Штейнера на ориентированом градуированном графе. Для ее решения был применен весь спектр методов, использующихся для исследования NP-трудных задач. Разработаны алгоритмы, соответствующие следующей классификации:
1 .Алгоритмы уменьшения размера задачи.
2.Точные алгоритмы, использующие
а)метод ветвей и границ,
б)метод динамического программирования.
3.Выделение полиномиально-разрешимых классов задач.
"(.Приближенные алгоритмы.
Практическая ценность. Разработанные алгоритмы можно применять при решения любых практических задач, для которых математической моделью является исследуемая в диссертации задача.
Следующие алгоритмы решения проблемы были реализованы в виде компьютерных программ и опробованы на серии случайных графов: поглощение вершин, поиск доминаторов, выделение областей, метод ветвей и границ, метод динамического программирования.
Некоторые из предлагаемых алгоритмов применимы для решения задачи Штейнера на градуированном графе с весами на дугах, эквивалентной задаче Штейнера на орграфе без контуров, являющейся ближайшим обобщением нашей задачи.
Апробация результатов. Основные результаты диссертации опубликованы в работах [1-4]. Результаты диссертации докладывались на Всесоюзном семинаре "Дискретная оптимизация и исследование опреаций (Новосибирск, 1990 г.), Одесском научно-исследовательском семинаре но дискретной математике ЮНЦ АН СССР (Одесса, 1991), Втором Сибирском Конгрессе по Прикладной и Индустриальной Математике (Новосибирск, 1996), семинаре в Институте математики и механики УрО РАН, семинарах Уральского госуниверситета.
Структура и объем диссертации. Диссертация состоит из введения и пяти глав, разделенных на два параграфа каждая. Общий объем диссертации соста-