Мощностная задача Штейнера на ориентированном градуированном графе тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Уральский государственный университет им.А.М.Горького

УДК 519.1 На правах рукописи

Щербакова Валентина Александровна

Мощностная задача Штейнера на ориентированном градуированном графе

01.01.09 - математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Екатеринбург - 1998

Работа выполнена на кафедре алгебры и дискретной математики матсматико-механического факультета Уральского государственного университета в г.Екатеринбурге.

Научный руководитель:

доктор физико-математических наук, профессор Баранский В.А.

Официальные оппоненты:

доктор физико-математических наук, профессор Егорычев Г.П.

кандидат физико-математических наук, Матвеев А .О.

Ведущая организация:

Уральский государственный технический университет - УПИ

Защита диссертации состоится " ЛЛОьЯ 1998

г. в

часов на засе-

дании диссертационного совета К 002.07.01 в Институте математики и механики УрО РАН по адресу:

620219, г.Екатеринбург, ул.Софьи Ковалевской, д.16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан СКпрал^ 1998 г.

Ученый секретарь диссертационного сонета кандидат физ.-мат. наук,

старший научный сотрудник

Общая характеристика работы

Актуальность работы. Мощностная задача Штейнера на ориентированном градуированном графе служит моделью многих реальных проблем, возникающих в различных сферах хозяйственной дсятельности(см., например, [1]),

Исследуемая задача является частным случаем проблемы Штейнера на ориентированном графе, которую формулируют как обобщение широко известной проблемы Штейнера на неориентированном графе. Однако, общая задача Штейнера на орграфах мало исследовалась математиками. Она кратко упоминается в книге [2] (стр.221), формулируется в обзорах [3], [4], [5], посвященных,вообще говоря, задаче Штейнера на неориентированном графе. Имеются статьи [6], [7], [8), [9], [10] о задаче Штейнера на орграфе, и статья (11) для орграфа без контуров. Во всех этих работах предлагается решать задачу методом целочисленного программирования, т.е. путем минимизации целевой функции с ограничениями в виде системы линейных уравнений и неравенств с целыми коэффициентами, переменные которых принимают значения 0 или 1. Нами был выбрап подход исследования рассматриваемой задачи непосредственно на графе.

Цель работы. Применить для решения мощностной задачи Штейнера на ориентированном градуированном графе весь спектр методов, использующихся для исследования КР-трудных задач на графах. Научная новизна.

В диссертации впервые рассмотрена задача, названная мощностной задачей Штейнера на ориентированом градуированном графе. Для ее решения был применен весь спектр методов, использующихся для исследования №-трудных задач. Разработаны алгоритмы, соответствующие следующей классификации: 1 .Алгоритмы уменьшения размера задачи.

2.Точные алгоритмы, использующие

а)метод ветвей и границ,

б)метод динамического программирования.

3.Выделение полиномиально-разрешимых классов задач.

"¡.Приближенные алгоритмы.

Практическая ценность. Разработанные алгоритмы можно применять при решения любых практических задач, для которых математической моделью является исследуемая в диссертации задача.

Следующие алгоритмы решения проблемы были реализованы в виде компьютерных программ и опробованы на серии случайных графов: поглощение вершин, поиск доминаторов, выделение областей, метод ветвей и границ, метод динамического программирования.

Некоторые из предлагаемых алгоритмов применимы для решения задачи Штейнера на градуированном графе с весами на дугах, эквивалентной задаче Штейнера на орграфе без контуров, являющейся ближайшим обобщением нашей задачи.

Апробация результатов. Основные результаты диссертации опубликованы в работах [1-4]. Результаты диссертации докладывались на Всесоюзном семинаре "Дискретная оптимизация и исследование опреаций (Новосибирск, 1990 г.), Одесском научно-исследовательском семинаре но дискретной математике ЮНЦ АН СССР (Одесса, 1991), Втором Сибирском Конгрессе по Прикладной и Индустриальной Математике (Новосибирск, 1996), семинаре в Институте математики и механики УрО РАН, семинарах Уральского госуниверситета.

Структура и объем диссертации. Диссертация состоит из введения и пяти глав, разделенных на дпа параграфа каждая. Общий объем диссертации соста-

вляет 120 страниц. Библиография содержит 46 наименований. Используется сквозная нумерация параграфов и составная нумерация рисунков и утверждений.

Содержание работы

Пусть С - ориентированный граф с корнем г. Граф С называется связным по корню г. если каждая его вершина V достижима из корня г, т.е. существует путь из г в и. Граф б называется градуированным, если он связей по корню г и для каждой вершины V длина всех путей из г в и одинакова.

Мощностная задача Штейнера на ориентированном градуированном графе формулируется следующим образом:

Дано: й = (V, Е) - ориентированный, связный по корню г, градуированный граф; Н подмножество вершин графа в, называемых помеченными. Найти: Т «= (V, Е1) - дерево Штейнера. т.е. подграф графа <7, связный по корню г, содержащий все вершины из Н, такой, что мощность \Е'\ минимальна.

Очевидно, искомый подграф Т обязательно будет деревом. Следовательно, мощность \У\ также будет минимальной.

Глава 1 посвящена исследованию вычислительной сложности нашей проблемы. В §1 рассмотрены взаимосвязи различных случаев задачи Штейнера на графах. В §2 приводится доказательство следующей теоремы.

Теорема 2.1. Мощностная задача Штейнера на ориентированном градуированном графе является КР-трудной.

Эта теорема является одним из принципиально важных результатов диссертации, так как, при предположении о несовпадении классов Р и из теоремы 2.1 следует , что не существует полиномиального алгоритма решения исследуемой

задачи.

В главе 2 приведены алгоритмы уменьшения размера задачи. В §3 изложены два простых алгоритма, позволяющих уменьшить количество непомеченных вершин и увеличить число помеченных вершин в графе. Первый из них - алгоритм "поглощения" вершин, а второй - алгоритм поиска доминаторов для каждой помеченной вершины V, т.е. вершин, лежащих на любом пути из корня г в V.

В §4 изложен более сложный алгоритм - алгоритм выделения областей, разбивающий исходный граф на части, таким образом, что дерево Штейнера для всего графа получается объединением деревьев Штейнера в каждой области. Если выделено больше одной области, то размер задачи Штейнера в каждой области меньше размера исходной задачи.

Алгоритмы, изложенные в главе 2, используются в качестве предварительной обработки графа перед применением последующих алгоритмов. В некоторых случаях, после такой предварительной обработки полученное множество помеченных вершин порождает связный по корню г граф. Тогда любое остовное дерево в таком графе является искомым деревом Штейнера.

В главе 3 предлагаются точные алгоритмы решения проблемы, являющиеся одними из главных результатов исследования. В §5 изложен алгоритм, основанный на методе ветвей и границ. Алгоритм осуществляет сокращенный перебор подмножеств непомеченных вершин. Наименьший по мощности из перебираемых вариантов, объединенный с множеством помеченных вершин, образует множество вершин искомого дерева Штейнера, при условии, что что множество порождает связный но корню г граф. Алгоритм, предложенный в §5, идейно аналогичен алгоритму для задачи ШггПпгра на неориентированном графе.

В §6 дается алгоритм на основе метода динамического программирования.

Алгоритм использует следующее рекуррентное соотношение:

|Г,(Я)| = тш (р(г,и) + |Т„(Я,)| + |Т„(Я2)|) ,

где ТГ(Я) - дерево Штейнера, соединяющее корень г с множеством Я помеченных вершин, ТДЯ]) и Т„{Нг) - деревья Штейнера, соединяющие вершину V в качестве корня с множеством помеченных вершин и Я3, соответственно; минимум берется по всем вершинам V и всем разбиениям (ЯЬЯ2) множества Н на непустые множества.

Алгоритмы из §5 и §6 имеют сложности 0(|У| • 21пя') и 0(|У|а + |У|2 • 3!я|), соответственно. Следовательно, в зависимости от количества помеченых вершин, эффективен либо первый, либо второй алгоритм, т.е. они дополняют друг друга по сложности.

Глава 4 посвящена полиномиально-разрешимым случаям исследуемой задачи. В параграфах 7 и 8, содержащих одни из главных результатов диссертации, описаны два полиномиально-разрешимых класса задач Штейнера К(ТРг) и К(Т32), в каждом из которых ограничения накладываются на вид графа £7 и на расположение помеченных вершин.

Определение 7.1. Назовем классом ТР2 наименьший класс ориентированных графов, содержащий в себе все ориентированные деревья с корнем г, удовлетворяющий свойству: для любого графа С из ТР2, граф С = (V и {!)}, Е и {(и,и),(и,ш)}), где и и ш лежат вС, новая вершина, не принадлежащая (7 и р(и,«!) = 2 в графе й, тоже принадлежит классу ТР2.

Определение 8.1. Назовем классом Твг наименьший класс ориентированных графов, содержащий в себе все ориентированные деревья с корнем г, удовлетворяющий свойству: для любого графа С из ТЭ2, граф С = (Уи{1>}, £и{(и, и)|и е I/} и {(и, ш)|ш 6 IV}), где V - новая вершина, не принадлежащая в, I/ С /п(и'),

V Ф 0, И' С Ои1(и'), IV ф 0 для некоторой у' из <7, тоже принадлежит классу ТЭц.

Приведем формулировки правил исключения вершин, используемых в определениях классов К(ТР2) и К(Т32).

Правило 1 (исключение вершин). Вершина V в графе С удовлетворяет правилу

1, если ее полустепени захода и исхода равны 1, и существует вершина V1, такая, что /п(ь') Э 1п(и), Ои¿(1/') Э Оыг(у).

Правило 2 (исключение вершин). Вершина и в графе С? удовлетворяет правилу

2, если выполняются |/п(и)| > 0, |Ои<(и)| > 0 и существует вершина и', такая, что /п(и') Э 1п(ь), ОиЦу') Э Оиг(ь).

Определение 7.2. Граф б и множество помеченных вершин Н в нем задают мощностиую задачу Штейнера из класса К(ТР2), если С принадлежит ТР2, и граф С можно разобрать до дерева последовательным удалением непомеченных вершин, удовлетворяющих правилу 1.

Определение 8.2. Граф в и множество помеченных вершин Н в нем задают мощностиую задачу Штейнера из класса К(Т32), если б принадлежит ТБ2, и граф (7 можно разобрать до дерева последовательным удалением непомеченных вершин, удовлетворяющих правилу 2.

Для классов графов ТР2 и Т32, и для классов задач К(ТР2) и К(ТЭ2) получены описания в терминах запрещенных-разрешенных подграфов, изложенные п нижеследующих теоремах.

Дадим определения подграфов особого вида, используемых в формулировках теорем.

Определение 7.3. Обручем длины п будем называть градуированный граф из п вершин, составленный из двух путей р|(и,г) и р-2{и,ь), не пересекающихся по

внутренним вершинам, таких, что не существует путей между вершинами путей Рг и р2, кроме, быть может, из и в V.

Определения 7.4. КопоноИ длины п будем называть граф С = {V, Е). где V = {»О, ••■,»„-!} и {и0,...,и„_,}, Е = {(«¡,и,),(и„и(1+1)га^ „)|г = 0, ... ,71 - 1}.

Определенно 7.5. ¿/-конфигурацией в графе будем называть пять вершин {мь "ь ><■.!, "зЬ между которыми существуют только следующие пути: р(и,, и,), г)> /'("2."г), р("2)«з)- Вершины И], и3 будем называть крайними в М-коифигурации, а вершину и2 - средней.

Определение 7.6. /У-конфигураписй в графе будем называть четыре вершины {"]> "2, «1> "г}, между которыми существуют только следующие путч: р(1'ь«)), >из). Вершины «), «2 будем называть крайними, соответственно, и, - нижней, V? - верхней.

Теорема 7.1. Граф С принадлежит классу ТР2 тогда и только тогда, когда й удовлетворяет следующим условиям:

1) Граф й является ориентированным, градуированным, связным по корню г.

2) В графе <3 нет подграфов - обручей длины больше 4.

3) В графе С нет подграфов - корон длины п, для любого п > 2.

4) В графе (7 нет М-конфигураций с висячими в б крайними вершинами.

Теорема 8.1. Граф С принадлежит классу Твг тогда и только тогда, когда С

удовлетворяет следующим условиям:

1) Граф С является ориентированным, градуированным, связным по корню г.

2) В графе (7 нет подграфов - обручей длины больше 4.

3) Если в С еегь корона длины п, то имеется общая заходящая вершина для всех нижних вершин короны.

4) Если в С есть Л/-конфигурация с висячими, крайними вершинами, то су-

шествует вершина и>, из которой достижимы средняя и обе крайние вершины М-конфигурации, такая, что р(г, ю) > гпш(р(г,и,), р(г,и2)).

Теорема 7.2. Граф С и множество Н помеченных вершин в нем задают мощ-ностиую задачу Штейнсра из класса К(ТР2) тогда и только тогда, когда выполняются следующие условия:

1) Граф й принадлежит классу ТР2.

2) Для каждой вершины V графа С, в множестве входящих в нее вершин 1п(ч) содержится не более одной помеченной вершины.

3) В графе нет ^-конфигурации, в которой крайние вершины являются помеченными или листьями.

Теорема 8.2. Граф <3 и множество Н помеченных вершин в нем задают ыощ-ностную задачу Штейнера из класса К(Т32) тогда и только тогда, когда выполняются следующие условия:

1) Граф £7 принадлежит классу ТБг.

2) Для каждой вершины V графа С, в множестве входящих в нее вершин /п(и) содержится не более одной помеченной вершины.

3) В графе й нет Л'-конфигуращш, в которой крайние вершины являются помеченными или листьями.

Глава 5 посвящена приближенным алгоритмам решения задачи. В §9 дается алализ некоторых приближенных алгоритмов, использующих естественные стратегии поиска, таких, как алгоритм "минимальных соседних покрытий" и алгоритм "минимальных целевых путей". Идея второго алгоритма близка к алгоритму для задачи Штейнера на неориентированном графе. Однако, в отличие от случая неориентированного графа, алгоритм "минимальных целевых путей", как и алгоритм "минимальных соседних покрытий", имеет "неограниченную погрет-

ность", что показано в предложениях 9.1 и 9.2. В формулировках предложений АРРС0„ и АРР^ц, обозначают стоимости решения, полученного, соответственно, первым или вторым алгоритмом; ОРТ - стоимость оптимального решения.

Предложение 9.1. Для любого числа а > 1 найдутся граф й и множество помеченных вершин Н, для которых выполняется АоРт' >

Предложение 9.2. Для любого числа а > 1 найдутся граф б и множество помеченных вершин Н, для которых выполняется > <*■

В §10 изложен приближенный алгоритм "минимального среднего расстояния", аналогичный алгоритму для случая неориентированных графов. На всех примерах общего вида, рассмотренных в §9, выполняется < 2, где АРРтеап -стоимость решения, полученного алгоритмом "минимального среднего расстояния". Для произвольного графа такой хорошей оценки погрешности не найдено.

Для всех алгоритмов решения нашей задачи найдены оценки сложности по времени, они приведены в таблице 1. При этом предполагается, что вставка и удаление одной вершины или ребра занимает постоянное время, а списки 1п(у) и Ои((у) для каждой вершины V графа вычисляются один раз и хранятся до конца работы алгоритма.

Название Сложность Обобщенная оценка сложности

Алгоритмы уменьшения размера задачи: Поглощение верши» (§3) Поиск ламинаторов (ЦЗ) Выделение областей (§4) 0(52 • к2) O(h-i-P) 0(S ■ n* + h2 ■ n2) 0( n<) 0(n*) 0(n*)

Точные алгоритмы: Ме тод ветвей и границ (§5) Метод динамического программирования (§6) 0(n • 2S) 0(n3 + n2-3h)

Полиномиально-разрешимые классы: Класс ориентированных деревьев и распознавание принадлежности (§7) Класс К(ТР2) и распознавание принадлежности (§7) Класс К(Т82) и распознавание принадлежности (§8) 0{ n) 0(n2 • k2) 0(n2 • k1) 0(n<) 0(n4)

Приближенные алгоритмы: Алгоритм "минимального среднего расстояния" (§10) 0(n5)

Таблица 1. Сложность по времени алгоритмов решения задачи; п = ) V], Л. = |Н|,5 = [V \ Я|, ( - число уровней вершин в графе, к - наибольшее число вершин на одном уровне

Заключение

Основные результаты диссертации, выносимые на защиту:

1. Доказана КР-трудпость мошностной задачи Штейнера на ориентированном градуированном графе.

2. Разработан комплекс алгоритмов, соответствующих следующей классификации:

— алгоритмы уменьшения размера задачи;

— точные алгоритмы решения задачи (реализующие метод ветвей и границ и метод динамического программирования);

— приближенный алгоритм.

3. Описаны дна класса ориентированных градуированных графов, где, при подходящем расположении помеченных вершин, мощностная задача Шгейнера полиномиально разрешима. Разработаны алгоритмы решения исследуемой задачи в этих классах.

Список литературы

1.Гусев А. А. Разработка методов технологических расчетов при проектировании с применением ЭВМ сортопрокатных станов: Диссертация на соискание ученой степени кандидата технических наук.- Свердловск, 1987,- 131 с.

2.Михалевич B.C., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-транспортного планирования: Модели, методы, алгоритмы.- М.: Наука, 1986.- 2G4 с.

3.Гордеев Э.Н., Тарасцов О.Г. Задача Штейнера. Обзор//Дискретная математика,- 1993, № 2,- С.3-28.

4.Winter P. Steiner Problem in Networks: A Survey //Networks, 17(1987).- C.129-167.

5.Maculan N. The Steiner problem in graphs //Annals of Discrete Mathematics.-31(1987).- C.185-212.

6.Duiu C.W., Volgenant A. Some generalization of the Steiner problem in graphs //Networks.- 17(1987), .V 3,- C.353-364.

7.Liu W. A lower bound for the Steiner tree problem in directed graphs //Networks.-

20(1990), № 6,- С.765-778.

8.Maculan N., Arpin D., Nguyen S. Le problem de Steiner sur un graphs orienté: formulations et relaxations // Matemática Aplicada e Coinputacional.- 7(1988), № 2,-C.109-118.

9.Maculan N., Souza P., Candia V.A. An approach for the Steiner problem in directed graphs //Annals Operations Research.- 33(1991).- C.471-480.

10.Wong R.T. A dual ascent approach for Steiner tree problems on a directed graph //Mathematical Programming.- 28(1984).- C.27I-287.

11.Nastansky L., Selkow S.M., Stewart N.F. Cost-Minimal Trees in Directed Acyclic Graphs //Zeitschrift für Operations Research.- 18(1974).- С.5Э-67.

Список работ автора по теме диссертации

1.Щербакова В.А. Минимальные деревья, связывающие заданное подмножество вершин в ориентированном градуированном графе //Урал.гос.ун-т.-Екате-ринбург,1994.-27с., Депонир. в ВИНИТИ 21.10.94 № 2391-В94.

2.Щербакова В.А. Алгоритм решения мощностной задачи Штейнера на ориентированном градуированном графе методом динамического программирования //Урал.гос.ун-т.-Екатеринбург,1995.-12с., Депонир. в ВИНИТИ 14.04.95 JV° 1052-В95.

3.Щербакова В.А. Классы ориентированных градуированных графов с полиномиально-разрешимой мощностной задачей Штейнера //Второй Сибирский Конгресс по Прикладной и Индустриальной Математике, посвященный памяти А.А.Ляпунова (1911-1973), А.П.Ершова (1931-1988) и И.А.Полетаева (1915-1983). Тезисы докладов, часть II. Новосибирск, ИМ СО РАН, 1996, С.128-129.

4.Щербакова 13.А. Классы ориентированных градуированных графов с ноли-номиально-рач]>ешимой мощностной задачей Штейнера //Дискретная математика,- 1997, № 4,- С.73-85.

Подписано к печати 0(Г.0Й.98. Заказ 39 • Тираж 100 экз. Бесплатно. Объем 1.0 п.л. Печать плоская. Бумага газетная. Формат 60x84/16

620083, г.Екатеринбург, пр.Ленина, 51

Типолаборатория Уральского госуниверситета им. А.М.Горького