Общая задача синтеза надежных сетей

Общая задача синтеза надежных сетей

Розглядається важлива для розвитку теорії та практики задача проектування мережі мінімальної вартості, що продовжує функціонувати навіть при виході з ладу окремих її компонент. Кількість обмежень в моделі з потоковими змінними 0 та 1 експоненційно залежить від кількості вузлів; показано, що LP -ре...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Advances in Astronomy and Space Physics
Datum:2011
Hauptverfasser: Шор, Н.З., Шарифов, Ф.А.
Format: Artikel
Sprache:English
Veröffentlicht: Головна астрономічна обсерваторія НАН України 2011
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/206763
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:Общая задача синтеза надежных сетей / Н.З. Шор, Ф.А. Шарифов // Проблемы управления и информатики. — 2006. — № 1-2. — С. 184-202. — Бібліогр.: 32 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-206763
record_format dspace
spelling Шор, Н.З.
Шарифов, Ф.А.
2025-09-22T09:00:46Z
2011
Общая задача синтеза надежных сетей / Н.З. Шор, Ф.А. Шарифов // Проблемы управления и информатики. — 2006. — № 1-2. — С. 184-202. — Бібліогр.: 32 назв. — рос.
2227-1481
https://nasplib.isofts.kiev.ua/handle/123456789/206763
519.8
Розглядається важлива для розвитку теорії та практики задача проектування мережі мінімальної вартості, що продовжує функціонувати навіть при виході з ладу окремих її компонент. Кількість обмежень в моделі з потоковими змінними 0 та 1 експоненційно залежить від кількості вузлів; показано, що LP -релаксація цієї задачі NP -складна. Для окремих випадків доведено, що розв’язок відповідної LP -релаксації цієї задачі можна знайти за допомогою поліноміального алгоритму. Запропоновано ефективні алгоритми обчислення верхньої та нижньої границь для двозв’язної задачі Штейнера. Для розв’язання цієї задачі застосовується метод гілок та границь; наведено також результати обчислювальних експериментів.
We consider the important practical and theoretical problem of designing communications network with a minimum total cost under condition that an optimal network must survive with respect to failures of certain its components. The model with 0, 1 — flow variables contains a number of constraints that is exponential in the number of nodes and we show that its LP -relaxation is NP -complete problem. For some particular cases, we prove that a solution of LP -relaxation problem can be found by polynomial time algorithm. We propose effective algorithms to compute lower and upper bounds for the two connected Steiner problem. For finding a solution of this problem we implement the branch and bound algorithm and we also report on some computational results.
en
Головна астрономічна обсерваторія НАН України
Advances in Astronomy and Space Physics
Общая задача синтеза надежных сетей
Загальна задача синтезу надійних мереж
General Reliability Problems in Network Design
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Общая задача синтеза надежных сетей
spellingShingle Общая задача синтеза надежных сетей
Шор, Н.З.
Шарифов, Ф.А.
title_short Общая задача синтеза надежных сетей
title_full Общая задача синтеза надежных сетей
title_fullStr Общая задача синтеза надежных сетей
title_full_unstemmed Общая задача синтеза надежных сетей
title_sort общая задача синтеза надежных сетей
author Шор, Н.З.
Шарифов, Ф.А.
author_facet Шор, Н.З.
Шарифов, Ф.А.
publishDate 2011
language English
container_title Advances in Astronomy and Space Physics
publisher Головна астрономічна обсерваторія НАН України
format Article
title_alt Загальна задача синтезу надійних мереж
General Reliability Problems in Network Design
description Розглядається важлива для розвитку теорії та практики задача проектування мережі мінімальної вартості, що продовжує функціонувати навіть при виході з ладу окремих її компонент. Кількість обмежень в моделі з потоковими змінними 0 та 1 експоненційно залежить від кількості вузлів; показано, що LP -релаксація цієї задачі NP -складна. Для окремих випадків доведено, що розв’язок відповідної LP -релаксації цієї задачі можна знайти за допомогою поліноміального алгоритму. Запропоновано ефективні алгоритми обчислення верхньої та нижньої границь для двозв’язної задачі Штейнера. Для розв’язання цієї задачі застосовується метод гілок та границь; наведено також результати обчислювальних експериментів. We consider the important practical and theoretical problem of designing communications network with a minimum total cost under condition that an optimal network must survive with respect to failures of certain its components. The model with 0, 1 — flow variables contains a number of constraints that is exponential in the number of nodes and we show that its LP -relaxation is NP -complete problem. For some particular cases, we prove that a solution of LP -relaxation problem can be found by polynomial time algorithm. We propose effective algorithms to compute lower and upper bounds for the two connected Steiner problem. For finding a solution of this problem we implement the branch and bound algorithm and we also report on some computational results.
issn 2227-1481
url https://nasplib.isofts.kiev.ua/handle/123456789/206763
citation_txt Общая задача синтеза надежных сетей / Н.З. Шор, Ф.А. Шарифов // Проблемы управления и информатики. — 2006. — № 1-2. — С. 184-202. — Бібліогр.: 32 назв. — рос.
work_keys_str_mv AT šornz obŝaâzadačasintezanadežnyhsetei
AT šarifovfa obŝaâzadačasintezanadežnyhsetei
AT šornz zagalʹnazadačasintezunadíinihmerež
AT šarifovfa zagalʹnazadačasintezunadíinihmerež
AT šornz generalreliabilityproblemsinnetworkdesign
AT šarifovfa generalreliabilityproblemsinnetworkdesign
first_indexed 2025-11-24T03:11:22Z
last_indexed 2025-11-24T03:11:22Z
_version_ 1850840537143181312
fulltext © Н.З. ШОР, Ф.А. ШАРИФОВ, 2006 184 ISSN 0572-2691 УДК 519.8 Н.З. Шор, Ф.А. Шарифов ОБЩАЯ ЗАДАЧА СИНТЕЗА НАДЕЖНЫХ СЕТЕЙ В данной статье рассматриваются задачи синтеза надежных сетей, которые возникают в таких областях науки, как дискретная оптимизация, вычислительная геометрия, молекулярная биология, а также при проектировании сверхбольших интегральных схем (СБИС), телекоммуникационных, транспортных, механиче- ских, электрических систем и т.д. 1. Постановка общей задачи синтеза надежных сетей В задачах синтеза надежных сетей предполагается, что элементы системы могут выходить из строя, нарушая нормальное функционирование всей системы или ее части. Основное требование к создаваемой системе коммуникации — ее нормальное функционирование в аварийном режиме. Удобное средство пред- ставления подобных систем — неориентированный граф, и выход элементов из строя может рассматриваться как удаление ребер произвольного подграфа, изо- морфного некоторому заранее заданному графу. Два графа называются изо- морфными, если они идентичны с точностью до перенумераций их вершин. Мно- жества вершин и ребер произвольного графа G обозначаются соответственно )(GV и .)(GE Сам граф обозначается как ))(),(( GEGVG = или )).(),(( GEGV Удаления произвольного подмножества ребер A из G означает, что получен подграф ).\)(),(( AGEGV Ребро с конечными вершинами ,0v 1v обозначается .),( 10 vv Последовательность rvvvvvvvs lll == − ),,(,,),,(, 11100  вершин из )(GV и ребер из ),(GE такая что каждая вершина и каждое ребро в ней появляют- ся один раз, называется путем, соединяющим вершины s и .r Если s и r — одна и та же вершина, то этот путь называется простым циклом, или просто циклом. Пусть заданы множество вершин )(GV и множество ребер )(GE неориенти- рованного графа ,),( EVG = где )(GVV = и .)(GEE = Задано множество узлов (терминальные вершин) VN ⊆ и неотрицательные веса ec для всех ребер e из .E С помощью одного из следующих способов также заданы множества вершин и множества ребер другого неориентированного графа :))(,)(( HEHVH = 1) заданы множества )(HV и ,)(HE или в явном виде они не заданы, но ука- зано число ребер и вершин графа H с выделенной структурой; 2) множества )(HV и )(HE в явном виде не заданы, а также не указано чис- ло ребер и вершин графа ,H но известно, что граф H может быт произвольным графом с выделенной структурой. Вес произвольного подграфа графа G определяется как сумма весов его ребер. Подграф 0G графа G определяется подмножеством ребер ,0E если 00 )( EGE = и множество его вершин )( 0GV содержит обе конечные вершины всех ребер из .0E Общая задача синтеза надежных сетей (ОЗСС) состоит в нахождении под- графа ))(,)(( *** GEGVG = с минимальным весом при условии, что подграф, определенный множеством ребер ,)(\)( * ΓEGE содержит хотя бы один путь между произвольными парами узлов из ,N где Γ — произвольный подграф гра- фа ,G изоморфного заданному графу .H Проблемы управления и информатики, 2006, № 1–2 185 Из способов задания графа H следует, что надо рассматривать графы H, для которых VHV ≤)( и .)( EHE ≤ Например, пусть H — связный простой граф без циклов с двумя висячими вер- шинами, т.е. граф H — простой путь и задан вторым способом. По постановке ОЗСС следует рассматривать только те графы, которые имеют не больше 1)( −HV ребер. Отметим, что если H — тривиальный граф ,))(( ∅=HE то ОЗСС эквива- лентна задаче Штейнера на графе G (ЗШГ), которая состоит в нахождении дере- ва, связывающего все узлы из N и имеющего минимальный вес среди подобных деревьев. В ЗШГ узлы из N называются основными, а вершины из NV \ — вер- шинами Штейнера. Так как ЗШГ NP-полная, то ОЗСС — тоже NP-полная задача. Другой вырожденный случай ОЗСС соответствует тому, что в графе G не суще- ствует ни одного подграфа, изоморфного .H Тогда по условиям ОЗСС ни одно ребро произвольного подграфа не может быть удалено из графа .G Таким обра- зом, и в этом случае ОЗСС и ЗШГ эквивалентны. Вырожденные случаи ОЗСС также возникают на практике. В следующих разделах рассматриваются невырож- денные случаи ОЗСС, поэтому здесь рассмотрим одну задачу из молекулярной биологии, которая является вырожденным случаем ОЗСС. B [1] сформулирована задача о возможных соединениях в допустимых кон- фигурациях химических компонентов генов. Если такими компонентами являют- ся трехмерные молекулы, то они могут быть соединены вместе в соответствии с определенной структурой. Это объединение можно представить в трехмерном пространстве, если каждой молекуле соответствует некоторая вершина и верши- ны соединены прямыми линиями при наличии связи между соответствующими молекулами. Возникает вопрос, можно ли расположить молекулы на одной и той же прямой линии так, чтобы они сохранили прежние связи? Каждая молекула представляется при этом отрезком прямой. Если пара молекул связана, то соот- ветствующие им отрезки взаимно перекрываются. Таким образом, задача состоит в нахождении условий, при которых граф связей можно представить с помощью пересекающихся определенным образом отрезков одной прямой линии, т.е. необ- ходимо так сопоставить отрезки с вершинами, чтобы два отрезка пересекались тог- да и только тогда, когда они соответствуют смежным вершинам. Граф, который может быть представлен таким образом, называется графом отрезков. Для сведения этой задачи к решению вырожденного случая ОЗСС отметим, что если граф не содержит ни одного подграфа, изоморфного одному из пяти гра- фов, представленных на рис. 1, то его можно изобразить с помощью отрезков на линии (см. [2]). Следовательно, если для произвольного графа ,H представленно- го на рис. 1, решение ОЗСС при VN = — дерево Штейнера (определение дерева Штейнера см. ниже), то ребра этого дерева не являются ребрами подграфов, изо- морфных .H Поэтому можно удалить ребра этого дерева из G и снова найти ре- шения ОЗСС на полученном графе. Повторяя этот способ, на некотором шаге находим, что либо ОЗСС не имеет древовидного решения, в этом случае в графе G существует подграф, изоморфный H, либо полученный граф несвязный, в этом случае граф G не содержит подграфа, изоморфного .H Ясно, что ЗШГ со множествами основных вершин N и вершин Штейнера NV \ имеет решение на графе G тогда и только тогда, когда в графе G суще- ствует связный подграф, множество вершин которого содержит N. Таким обра- 186 ISSN 0572-2691 зом, если H — тривиальный граф, то имеем достаточное и необходимое условие существования решения ОЗСС. Для общего случая ОЗСС условия существования ее решения также можно сформулировать. Проверка их выполнимости сводится к решению )2( )(HEO задач нахождения подграфа в G (см. ниже), изоморфного H. Рис. 1 Рассмотрим следующую задачу о допустимости: существует ли среди ком- понент связности графа ,G полученных после удаления из G множества ре- бер )(ΓE подграфа ,Γ изоморфного H, такая, что все узлы из N — ее вершины. Для произвольного подмножества вершин A множество ребер с одной ко- нечной вершиной в ,A а другой — в ,\ AV называется разрезом, определенным подмножеством VA ⊂ и обозначается .)(Aδ Условия существования решения ОЗСС (первым способом задания графа )H формулируются следующим образом. Утверждение 1. Задача о допустимости имеет решения тогда и только тогда, когда множество ребер )( 0GE произвольного подграфа )),,)(( 000 E(GGVG = изоморфного H, не образует разреза, отделяющего хотя бы один узел из N от остальных узлов ,N в графе .G Доказательство утверждения следует из известного факта: если в графе имеются пути, связывающие одну вершину с остальными, то этот граф связный и обратное утверждение также верно. По утверждению 1 для решения задачи о допустимости требуется найти в G некоторый подграф ,0G изоморфный .H Если найден такой подграф ,0G то после удаления из G всех подмножеств )( 00 GEE ⊆ таких, что ,)(...,,1 00 GEE = на полученных графах каждый раз нужно найти подграф, изоморфный графу .H Ес- ли на некотором шаге граф G распадается на несколько компонент связности, то задача о допустимости не имеет решения. В противном случае после удаления из G всех ребер подмножества )( 0GE на полученном графе снова определяется подграф, изоморфный графу H, и относительно этого подграфа процесс повторя- ется. Если на каждом шаге полученные графы связные, то задача о допустимости имеет решения; в противном случае не имеет. 2. Потоковая модель OЗCС Пусть Ω — множество подграфов графа G, изоморфных .H По указанному факту в доказательстве утверждения 1 для формулировки математической модели ОЗСС в терминах потоковых переменных произвольный узел Ns∈ можно выде- лить в качестве источника, а остальные узлы из }{0 s N \N = рассматривать как Проблемы управления и информатики, 2006, № 1–2 187 стоки сети .G В постановке ОЗСС условие существования пути между произ- вольными парами узлов в подграфе, полученном после удаления из G множества ребер )(ΓE подграфа ,Ω∈Γ эквивалентно тому, что в этом подграфе существует путь, соединяющий узлы s и r для всех r из .0N После удаления множества ребер Ω∈Γ из графа G в полученном подграфе r ijx — неизвестное количество потока на ребре ),,( ji идущего от источника в сток r. Математическая модель ОЗСС с этими переменными имеет следующий вид: найти xc Ee ee∑ ∈ min (1) при ограничениях ∑∑ Γ−Γ− ∈∈      =− Ω∈Γ∈∈≠ = =− )(δ 0 )(δ ,при1 ,,,,,при0 ,при1 i j r ji ij r ij GG ri NrVirsi si x x (2) ,),(,,0 0 EejiNrxx e r ij ∈=∈≤≤ (3) .,10 Eexe ∈∨= (4) Здесь )(δ iG Γ− — множество ребер, соединяющих вершины i с вершинами из }{i\V на графе, полученном после удаления из графа G всех ребер подграфа .Γ Ограничения (2) избыточны в том смысле, что можно определить некоторое подмножество 0Ω подграфов из Ω такое, что после замены условия Ω∈Γ на 0Ω∈Γ в ограничениях (2) решение ОЗСС не будет меняться и при этом 0Ω — минимальное по мощности подмножество. Число 0Ω назовем точным числом ограничений (2). Утверждение 2. Задача определения точного числа ограничений (2) NP-полная. Доказательство. Рассмотрим задачу Штейнера на графе G с множеством основных вершин N и вершин Штейнера .N\V Допустим, что *T — оптималь- ное решение этой задачи или, как его называют, оптимальное дерево Штейнера, т.е. в оптимальном решения ЗШГ значения переменных, соответствующих ребрам дерева ,*T равны единице, а значения остальных переменных — нулю. Рассмот- рим ОЗСС для графа ,H где }{)( gHE = и g — некоторое фиксированное ребро графа .G Допустим, что g не является ребром дерева .*T Тогда ОЗСС на графе G и ОЗСС на графе }){\,( gEV эквивалентны. Отсюда следует, что огра- ничение в (2), написанное относительно ребра g, избыточное. В этом случае нахождение избыточных ограничений сводится к проверке, является ли ребро g ребром дерева ,*T что невозможно осуществить за полиномиальное время, так как ЗШГ — NP-полная задача. Аналогично доказывается и следующее утверждение. Утверждение 3. Если в Ω не существует подграфа, который не содержит ни одного ребра оптимального дерева Штейнера ,*T то *T )( ** TG = — оптималь- ное решение ОЗСС. 188 ISSN 0572-2691 Согласно утверждению 3 получаем, что среди ограничений (2), написанных относительно подграфов из ,0Ω найдется такое, что множество ребер )(ΓE подграфа 0Ω∈Γ содержит хотя бы одно ребро оптимального дерева Штейне- ра (рис. 2). 1 5 4 6 3 2 3 3 3 3 3 2 2 2 2 2 Рис. 2 Пусть граф H состоит из двух вершин и одного ребра. Иначе говоря, граф *G должен быть связным при удалении из G произвольного ребра e из .E В этом случае ОЗСС эквивалентна задаче построения двухсвязной сети мини- мальной стоимости, множество вершин которой содержит .N В этом примере числа внутри кругов и рядом с ребрами — номера вершин и веса ребер соответственно. Множество узлов }.5,4,3,2,1{=N Легко проверить, что )}6,5(),6,4(),6,3(),6,2(),6,1{()( =*TE — множество ребер оптимального де- рева Штейнера .*T Оптимальным решением ОЗСС является подграф ,*G опреде- ленный множеством ребер )}.1,5(),5,4(),4,3(),3,2(),2,1{()( * =GE В ограниче- ниях (2), если учесть удаления только ребер оптимального дерева Штейнера ,*T решением ОЗСС является простой путь, соединяющий два любых узла из ,N например путь из ребер )4,3(),3,2(),2,1( и .)5,4( Если же учесть удаления толь- ко ребер из ),( *GE то решением ОЗСС является *T . Этот пример согласуется с утверждением 2 и показывает, что нахождение из- быточных ограничений в (2) затруднительно. Так как число ограничений (2) экс- поненциально выражается от числа вершин графа, то по утверждению 2 получа- ем, что задача линейного программирования (1)–(3), являющаяся LP-релаксацией ОЗСС (оценочная задача), в общем случае принадлежит классу NP-полных задач. Во многих случаях для ОЗСС можно предполагать, что .10 −≤Ω V Далее по- кажем, что решения оценочных задач можно найти за полиномиальное время при некоторых частных случаях графа H для каждого способа его задания. Пусть )( ijH — множество подграфов, изоморфных графу ,H которые со- держат ребро ),( ji и .)()( ijH\ijH Ω= Рассмотрим задачу, двойственную (1)–(3): найти ))()((max 0 Γ−Γ∑ ∑ ∈ Ω∈Γ r s r r Nr uu при ограничениях ,),(,,))()(( 0 )( EjiNrwuu r ij r i ijH r j ∈∈≤Γ−Γ∑ ∈Γ ,),(, 0 Ejicw ij Nr r ij ∈≤∑ ∈ .),(,,0 0 EjiNrwr ij ∈∈≥ Проблемы управления и информатики, 2006, № 1–2 189 Число переменных этой задачи оценивается экспоненциально от числа вершин графа .G Заменив )(Γ∑ Ω∈Γ r iu на ,r iu двойственную задачу представим в следую- щем виде: найти )(max 0 r s r r Nr uu −∑ ∈ (5) при ограничениях ,),(,,))()(( 0 )( EjiNruuwuu r i r j ijH r ij r i r j ∈∈Γ−Γ+≤− ∑ ∈Γ (6) ,),(, 0 Ejicw ij Nr r ij ∈≤∑ ∈ (7) .),(,,0 0 EjiNrwr ij ∈∈≥ (8) Утверждение 4. Существует оптимальное решение задачи (5)–(8) такое, что 0)()( ≠Γ−Γ r i r j uu только для одного подграфа ).( jiH∈Γ Доказательство. Допустим, что существуют хотя бы два подграфа ,1Γ )(2 jiH∈Γ такие, что ,0)()( ≠Γ−Γ k r ik r j uu где .2,1=k Переопределим значения для разницы двойственных переменных )( k r vu Γ следующим образом: ,)()()()(:)()( 111111 Γ−Γ+Γ−Γ=Γ−Γ r i r j r i r j r i r j uuuuuu .0:)()( 22 =Γ−Γ r i r j uu Нетрудно видеть, что после этих переопределений оптимальное значение целевой функции (5) не изменится, ограничения (6) также выполняются. Анало- гичным образом, переопределив значения для разницы двойственных переменных при 0)()( ≠Γ−Γ k r wk r v uu для Ewv ∈),( и ,2≥k доказываем справедливость утверждения. По утверждению 4 ограничение (6) можно заменить на следующее: ,),(,,))(())(( 0 EjiNrjiujiuwuu r i r j r ij r i r j ∈∈Γ−Γ+≤− (9) где )( jiΓ — изоморфный графу H произвольный подграф, содержащий реб- ро ).,( ji Следовательно, если граф H имеет простую структуру, то )( jiΓ можно определить за полиномиальное время, и в этом случае получим задачу линейно- го программирования (5), (7)–(9), для которой число переменных оценивается как .)( 2 EVO Так как прямая задача (1)–(4) является линейной релаксацией ОЗСС, то, решив задачу (5), (7)–(9) с помощью одного из существующих мето- дов решения общей задачи линейного программирования можно определить нижнюю оценку для функционала ОЗСС за полиномиальное время. Вычислительная сложность различных NP-полных задач на общих графах выражается как полином от их размерности при решении этих задач на специаль- ных графах, например на планарных. В [3] также предложен алгоритм с трудоем- 190 ISSN 0572-2691 костью )log( VVO для установления изоморфизма планарных графов. Легко показать, что задача нахождения подграфа графа ,G изоморфного планарному графу H, NP-полная. Действительно, пусть H — простой цикл, имеющий V вершин, т.е. H — планарный граф. Тогда нахождение в графе G подграфа, изо- морфного H, эквивалентно задаче определения гамильтонова цикла в ,G т.е. NP-полной задаче. Для первого способа задания графа H можно доказать следующий резуль- тат, когда H — полный двудольный граф с 6 вершинами ,)( 3,3K полный граф с 4 вершинами ,)( 4K простой цикл длины три (H-треугольный граф )3C или па- росочетание. Теорема 1. Нижняя оценка относительно оптимального значения зада- чи (1)–(4) определяется за полиномиальное время в случаях, когда ,3,3KH = ,4KH = 3CH = или H — паросочетание, мощностью .Vk ≤ Доказательство. Пусть ),( uve = — некоторое ребро графа .G После удале- ния ребра ),( uve = из G на полученном графе }){\,( eEV рассмотрим множе- ство ребер ,)(vδ )(uδ и зафиксируем все различные ребра ,),( 1vv ),( 2vv из .)(vδ Если граф }){\,( eEV содержит ребра ,),( 1vr ,),( 2vr где ,1ur = 2u и ,1u 2u — конечные вершины некоторых ребер из ,)(uδ то легко видеть, что множе- ство ребер ,),( uve = ,),( 1vv ),( 2vv и ,),( 1vr ),( 2vr при ,1ur = 2u образует 3,3K в .G Поскольку ,)(vδ ,)( Vu ≤δ то время перебора всех различных пар ребер из )(vδ и )(uδ оценивается как .)( 4VO Таким образом, либо находим подграф, изоморфный 3,3K и содержащий ребро ,e либо утверждаем, что его нет. Пусть теперь 4KH = и ребро ),( trg = не имеет общих вершин с ребром .),( uve = Если граф G содержит ребра ),,( rv ),,( tv а также ),,( ru ),,( tu то эти ребра вместе с ,e g образуют подграф, изоморфный .4K Таким образом, за вре- мя )( 2EO либо находим подграф, изоморфный 4K и содержащий ребро ,e ли- бо утверждаем, что в G его нет. При 3CH = доказательство теоремы тривиаль- но. Если H — паросочетание, мощностью ,k то для доказательства теоремы тре- буется найти максимальное паросочетание на графе ,)(eG применяя любой известный полиномиальный алгоритм [4–7], где граф )(eG получается удалением из G всех ребер из )(vδ и .)(uδ Для улучшения времени определения подграфа графа ,G изоморфного за- данному графу ,H при 3,3KH = или 4KH = можно использовать известные по- линомиальные алгоритмы [8–13] решения задачи нахождения подграфа, гомео- морфного заданному графу. Напомним, что два графа гомеоморфны, если их можно получить из одного графа с помощью последовательности подразбиений ребер. В этой задаче требуется найти подграф заданного входного графа ,0G го- меоморфного другому заданному графу .0H В случае, когда 0H — треугольный граф, полиномиальный алгоритм для решения этой задачи предложен в [8]. Если 0H — K-несмежные ребра, полиномиальные алгоритмы решения этой задачи предложены в [8–12]. Нахождение подграфа, изоморфного треугольному графу, Проблемы управления и информатики, 2006, № 1–2 191 или K-несмежных ребер — простая и известная задача, интерес вызывает алго- ритм [13] с временнóй сложностью )( 2VO для решения задачи нахождения подграфа, гомеоморфного заданному графу в случаях, когда 3,30 KH = или .40 KH = Для ускорения процедуры нахождения подграфа, изоморфного ,H при 3,3KH = или 4KH = этот алгоритм можно использовать следующим образом. Пусть в ОЗСС граф H задан первым способом и 3,3KH = или .4KH = В этом случае, не нарушая общности, можно предположить, что граф G не имеет вершин из ,\ NV степени которых равны двум. Действительно, допустим, что G содержит вершины v из NV \ со степенью два. Тогда в G существует только два ребра: ),( vu и ),( wv с конечной вершиной .v Так как 3,3K и 4K не имеют вер- шин со степенью два, то в этом случае можно удалить вершину v из графа G и ребра ),,( vu ),( wv заменить ребром ),,( vu длина которого определяется как сумма длин ребер ),( vu и .),( wv После этой операции в графе G могут быть па- раллельные ребра, образующие цикл длины два. Поскольку 3,3K и 4K не содер- жат цикл длины два, среди параллельных ребер, оставив ребро минимальной дли- ны, остальные ребра можно удалить. Понятно, что решение ОЗСС на полученном графе также является ее решением на .G Теперь с помощью алгоритма [13] находим подграф K графа G, гомеоморф- ного H. Ясно, что если K не содержит подразбиений ребер графа G, то найден подграф, изоморфный .H Если K содержит хотя бы одну вершину, которая раз- бивает ребра графа ,G то она принадлежит множеству N и ее степень равна двум, т.е. она инцидентна двум ребрам. После удаления одного из них снова решаем за- дачу нахождения подграфа, гомеоморфного H, в полученном графе. Так как число узлов не больше 2 ,V то, удаляя максимально V ребер и применяя алго- ритм [13] максимально V раз, либо находим подграф K, изоморфный H, либо утверждаем, что граф G не содержит подграфа, изоморфного .H Если 3,3KH = или ,4KH = то для ускорения процедуры нахождения подграфа, изоморфного H, содержащего фиксированные ребра, сначала указанным путем, применяя алго- ритм [13], находим гомеоморфный графу H подграф K графа ,G и тем самым за время )( 2VO определяем )(eΓ для всех ребер e подграфа .K После удаления всех ребер подграфа K из G на полученном графе снова находим новый подграф, гомеоморфный H, и т.д. Таким образом, за время )( 2VO определяем )(eΓ для всех ребер e найденных подграфов. Если найденные подграфы содержат все ребра G, то определены подграфы )(eΓ для всех ребер e. Иначе для остальных ре- бер e так же, как и в доказательстве теоремы 1, указанным способом находим изоморфный графу H подграф ),(eΓ содержащий ребро e. Рассмотрим второй способ задания графа H в ОЗСС. Пусть H — граф типа дерева или паросочетания. Допустим, что H — древовидный граф. В этом случае для определения )(eΓ из )(eH для всех Ee∈ сначала находится остовное дерево T в G за время .)( 2VO Далее находятся остовные деревья в отдельных компо- нентах связности графа ,G которые получаются в результате удаления из G ребер деревьев, и т.д. Ясно, что этим способом за время )( 3VO определяется )(eΓ для 192 ISSN 0572-2691 всех .Ee∈ Если H — паросочетание, то задача нахождения изоморфных H под- графов ,G содержащих ребро ,e сводится к нахождению паросочетаний на гра- фе, полученном после удаления ребра e и всех инцидентных ему ребер из .G Таким образом, для каждого способа заданного графа H показаны случаи, при которых подграф )(eΓ из множества )(eH определяется за полиномиальное время. 3. Частные случаи ОЗСС при первом способе задания графа H Существование решения ОЗСС тесно связано со структурами графов G и H. В утверждении 1 сформулировано необходимое и достаточное условие существо- вания решения задачи о допустимости для общего случая графа H. Покажем, что проверка существования решения ОЗСС для первого способа заданий графа H осуществляется за полиномиальное время для некоторых частных случаев графа H. 1. Пусть H имеет 2p вершин и p ребер, т.е. граф H является паросочетанием с числом ребер p. Обозначим srp максимальное число вершинно-непересекаю- щихся путей, связывающих узлы ,, rs для всех ., Nrs ∈ В [14] показано, что если ,1},;{min +≥∈ pNrspsr то решение ОЗСС на графе G существует. 2. Пусть H — некоторое дерево с числом вершин q и minδ — минимальный разрез в графе G с единичными весами ребер для всех ребер Ee∈ такой, что minδ отделяет хотя бы один узел из N от остальных узлов. Теорема 2 [14]. Если мощность разреза minδ больше ,1−q то ОЗСС имеет решение. 3. Пусть теперь H — некоторый лес и .1)( ≥= kHE Рассмотрим следую- щую задачу: найти xc Ee ee∑ ∈ min (10) при ограничениях ∑∑ δ∈δ∈      =+− ∈∈≠ =+ =− )( 0 )( ,при)1( ,,,,при0 ,при1 ij r ji ij r ij rik NrVirsi sik xx (11) ,),(,,0 0 EejiNrxx e r ij ∈=∈≤≤ (12) .,10 Eexe ∈∨= (13) В отличие от (1)–(4) размер этой задачи оценивается как полином третьей степени от числа вершины графа .G Для этого случая ОЗСС легко доказывается следую- щий нужный нам результат. Теорема 3. Если H — лес и ,)( kHE = то ОЗСС эквивалентна зада- че (10)–(13). В разд. 7 и 8 предложены алгоритмы нахождения нижней и верхней оценок для задачи (10)–(13) при ,1=k .2 VN ≤≤ Они используются в общей схеме метода ветвей и границ, с помощью которого находится решение этой задачи. Для рассмотренных случаев ОЗСС проверку существования решения ОЗСС можно осуществлять за время )log( 2 VVEVO + (см. [15–17]). Проблемы управления и информатики, 2006, № 1–2 193 При }),{(2 rsNN == решение ОЗСС можно найти одним из полиноми- альных алгоритмов [18–21] решения задачи нахождения потока минимальной стоимости. 4. Частные случаи ОЗСС при втором способе задания графа H Рассмотрим эти случаи ОЗСС со вторым способом задания графа H и пока- жем, что проверить, имеется ли решение ОЗСС, невозможно за полиномиальное время, если .NPP ≠ 1. Пусть 2=N }),{( rsN = и H — лес деревьев с двумя висячими верши- нами, т.е. каждое дерево — это простая цепь. В этом случае задача существования решения ОЗСС эквивалентна следующей игре Шеннона [2], которая проводится на графе двумя игроками. Оба игрока по договоренности выделяют две вершины (узлы s и )r и называют их конечными. Затем по очереди делают ходы. В соот- ветствии с правилами игры один из игроков на каждом своем ходе удаляет одно ребро из графа и стремится в конечном итоге разорвать все цепи, связывающие вершины s и .r Другой игрок на каждом ходе помечает одно из ребер. При этом помеченное ребро не может быть удалено из графа. Цель второго игрока — со- хранить хотя бы одну цепь, связывающую вершины s и .r Игра, в которой может выиграть второй игрок, называется игрой Шеннона второго типа. Теорема 4 [14]. Если 2=N и H — лес, состоящий из цепей, задача: суще- ствует ли решение ОЗСС, эквивалентное игре Шеннона второго типа. По теореме 6.8 [2] игра принадлежит второму типу тогда и только тогда, ко- гда граф G содержит два дерева без общих ребер, все вершины которых одина- ковы и имеют в своем составе s и r. Покажем, что задача определения деревья 1T и 2T в графе ,G таких, что )()( 21 TVTV = и ,)()( 21 ∅=∩ TETE NP-полная. Пусть 1T — некоторое дерево в графе G и всем ребрам подграфа ))(\,( 1TEEV приписаны единичные веса. Допустим, что T — минимальное дере- во Штейнера в этом подграфе, которое связывает вершины из ).( 1TV Ясно, что ,)()( 1TVTV ≥ поэтому в графе G можно положить TT =2 тогда и только то- гда, когда .)()( 1TVTV = Отсюда следует, что задача определения деревьев 1T и 2T NP-полная. 2. Пусть 2≥N и граф H — некоторое паросочетание, т.е. каждая вершина графа H инцидентна только одному ребру этого графа. Теорема 5 [14]. Когда H — произвольное паросочетание, решение ОЗСС су- ществует, если G содержит некоторый планарный подграф, для которого все внутренние грани — треугольники и множество вершин этого подграфа имеет в своем составе .N Пусть pG — связный плоский подграф графа ,G все внутренние грани pG — треугольники, а множество вершин )( pGV содержит все узлы из .N Сначала покажем, что задача определения в графе G максимального плоского графа ,maxG в котором каждый треугольник ограничивает некоторую область, не содержащую ребер, сводится к задаче нахождения pG в G для произвольно- го .VN ⊆ 194 ISSN 0572-2691 Допустим, что в графе G можно найти связный плоский подграф pG при VGV p =)( такой, что все внутренние грани — треугольники и не содержат ребра с висячей вершиной. Понятно, что если pG — не максимальный граф, то, соеди- няя две несмежные вершины внешней грани ребром из ),(\ pGEE можно увели- чивать число ребер подграфа pG до тех пор пока он остается плоским. Таким способом получим, что либо pG — максимальный плоский граф, либо граф G не содержит подграфа ,maxG т.е. при VN = задача нахождения maxG в G сводится к нахождению .pG Известно, что если maxG — максимальный плоский граф, в котором каждый треугольник ограничивает некоторую область, не содержащую ребер, то maxG — гамильтонов граф (см. [22]). Отсюда следует, что задача нахож- дения подграфа maxG в G более общая, чем задача определения гамильтонова цикла в .G Так как задача нахождения неориентированного гамильтонова цикла NP-полная, то задача нахождения maxG в графе G тоже NP-полная. Следова- тельно, для произвольного VN ⊆ задача нахождения pG на графе G — тоже NP-полная задача. Например, если плоский граф pG состоит из двух цепей с одинаковыми вершинами и без общих ребер, то все его внутренние грани являются треугольни- ками. Поэтому при VN = нахождение подграфа pG эквивалентно проверке, со- держит ли граф G гамильтонов путь. 3. Рассмотрим ОЗСС, когда VN = и множество ребер )(HE графа H содер- жит по одному ребру в каждом из реберно-непересекающихся простых циклов в .G Этот случай ОЗСС интересен тем, что для защиты информационного потока в телекоммуникационных сетях связи каждая линия должна лежать на замкнутой части сети и обычно максимальное число реберно-непересекающихся простых циклов в сети заранее неизвестно. Допустим, что существуют максимум ϕ ре- берно-непересекающихся простых циклов в графе ,G т.е. .)( VHE ≤ϕ= От- носительно этого случая ОЗСС докажем следующее утверждение. Теорема 6. Когда множество )(HE содержит по одному ребру из каждого реберно-непересекающегося простого цикла в ,G решение ОЗСС существует, если реберная связность графа G равна 4. Доказательство. В [23] доказано, что если реберная связность графа G рав- на 4, то в G существует два реберно-непересекающихся остовных дерева. Допу- стим, что из каждого ϕ реберно-непересекающегося простого цикла удалено од- но ребро. Пусть остовные деревья 1T и 2T не имеют общих ребер в графе .G По- нятно, что ребра деревьев 1T и 2T образуют простые циклы в графе ,G одни из них могут иметь общие ребра, другие — нет. Поэтому при удалении по одному ребру из каждого простого цикла, не имеющего общих ребер с другими циклами, оставшиеся ребра этого цикла лежат на путях, соединяющих концевые вершины удаленных ребер. Так как произвольное остовное дерево содержит хотя бы одно ребро из каждого реберно-непересекающегося простого цикла, то удаленное реб- ро может быть ребром либо ,1T либо .2T Поэтому после удаления ребра множе- ства )(HE из графа G в полученном графе существует хотя бы один путь между всеми парами узлов из N, что и доказывает теорему. Проблемы управления и информатики, 2006, № 1–2 195 5. Задача проектирования надежных сетей В этом и последующих разделах рассматривается частный случай ОЗСС, ког- да граф H имеет две вершины и одно ребро, т.е. граф H — простое ребро. В этом случае ОЗСС эквивалентна тому, что в проектируемой сети должен существо- вать хотя бы один путь между произвольными парами узлов из N при удалении произвольного ребра из сети .G Для рассмотренного случая графа H зада- ча (10)–(13) при 1=k — математическая модель ОЗСС, обобщающая задачу Штейнера на графе ,G и называется задачей двухсвязной сети Штейнера. Она возникает при транспортировке вредных экологических веществ по трубопрово- дам, при проектировании телекоммуникационных сетей связи. Поскольку вероят- ность одновременного выхода из строя двух и больше ребер очень мала, эта зада- ча имеет большое практическое значение. Задачу (10)–(13) при 1=k назовем за- дачей проектирования надежных сетей (ЗПНС). В обычных ситуациях авария в продуктопроводных сетях происходит из-за коррозии материалов конструкции линий коммуникации. Поэтому как вероят- ность аварии лучше использовать степень разрушения материалов конструкции (прочность) линии коммуникации за определенный период. В этом случае вес ec произвольного ребра e сети можно измерить величиной ,0≥µ= eee rc где µ — прочность предлагаемого материала для создания коммуникации, er — реальная длина участка (ребра). В [24] авторы отмечают, что в некоторых приложениях задачи проектирова- ния телекоммуникационных и транспортных сетей взаимодействие различных типов информационных потоков весьма сложно и стоимость увеличения объема потока на ребре нелинейно зависит от значения существующего потока и пропус- кной способности этого ребра. Эти факторы тоже важны, но их следует учитывать в математической модели оптимизационной задачи на втором этапе, после того как спроектирована сеть оптимальной стоимости. В [25] предложен алгоритм нахождения оптимальных путей для передачи информационного потока между двумя узлами на проектируемой сети. В задаче синтеза прочных сетей (ЗСПС) на полном графе можно считать, что веса ребер удовлетворяют неравенству треугольника [26]. Поскольку ЗШГ и задача синтеза k-связанной сети — частные случаи ЗСПС, то это же верно и при рассмотрении этих задач на полном графе. Таким образом, если веса некоторых ребер не удовлетворяют неравенству треугольника, то их веса заменяются длина- ми кратчайших путей, соединяющих их конечные вершины. При этом решения перечисленных задач не изменяются. При VN = ЗПНС эквивалентна задаче син- теза двухсвязной сети минимальной стоимости (minimum cost two-connected net- work design problem). Если G — полный граф и веса его ребер удовлетворяют не- равенству треугольника, то LP-релаксации задачи коммивояжера (ЗКГ) и ЗПНС эквивалентны (см. [26]). Поэтому при решении ЗПНС могут использоваться мето- ды нахождения нижних оценок для ЗКГ. Если },,{ rsN = то ЗПНС эквивалентна задаче нахождения потока мини- мальной стоимости с величиной два, на сети G с источником s и стоком r при единичных пропускных способностях всех ребер G. В этом случае алгоритм ре- шения задачи (1)–(3), которая получается отбрасыванием требования целочислен- ности переменных (LP-релаксации ЗПНС), имеет трудоемкость )( 2 EnO [25], которая больше O (n3)-трудоемкости решения самой ЗПНС. В случае },{)( gHE = где g — фиксированное ребро из E, ЗПНС эквива- лентна ЗШГ на графе .}){\,( gEV Поэтому ЗПНС NP-полная. В этом случае для решения ЗПНС можно применять алгоритмы нахождения оптимального дерева 196 ISSN 0572-2691 Штейнера *T [27], а также за время )log/( 2 NNnO + можно найти прибли- женное решение ЗПНС, вес которого не больше веса ,*T умноженного на ),/11(2 l− где l — число висячих вершин (листьев) дерева *T [28]. Другими классами задач, близкими к ЗПНС, являются задачи синтеза древовид- ных сетей или задачи синтеза с одним источником и многими стоками (ЗСДС) [29]. Для решения ЗСДС применяется общая схема метода ветвей и границ, в которой для нахождения нижней оценки методом динамической декомпозиции решается задача LP-релаксации ЗСДС. В этом методе, как и в симплекс–методе, на каждой итерации определяются переменные для ввода в базис и вывода из базиса. Трудо- емкости отдельных итераций этого метода на порядок меньше, чем в симплекс- методе. Несмотря на это, трудоемкость метода динамической декомпозиции оста- ется высокой даже для сети с относительно небольшим числом вершин. В [29–31] предложены алгоритмы нахождения нижней оценки путем приближенного реше- ния двойственной задачи к LP-релаксации ЗСДС. Приведены результаты числен- ного эксперимента решения ЗСДС методом ветвей и границ, подтверждающие высокую эффективность предложенных алгоритмов нахождения нижней и верх- ней оценок. 6. Численные методы решения ЗПНС Для решения ЗПНС применяется общая схема метода ветвей и границ. Для улучшения эффективности этого метода в следующих разделах предложены эф- фективные алгоритмы нахождения нижней )lower(F и верхней )upper(F оценок для целевой функции ЗПНС. В методе ветвей и границ при решении подобных задач используются раз- личные правила ветвления для того, чтобы отбросить большое количество непер- спективных ветвлений из дерева решения. В предыдущих разделах показано, что ЗПНС, ЗШГ, ЗКГ и ЗСДС — родственные задачи; поэтому, применяя к решению ЗПНС метод ветвей и границ, целесообразно применить правило ветвления, в ко- тором используются идеи ветвления, изложенные в [29] при решении ЗШГ, ЗСДС, и в [18] — при решении ЗКГ. Во время решения ЗПНС, зная структуру графа G, можно построить эффек- тивные правила ветвления. При определении значения верхней оценки ),upper(F строится двухсвязная сеть, соединяющая все узлы из N. На этой сети можно вы- числять степень каждой вершины и максимальное число реберно-непересекаю- щихся путей между всеми парами узлов из N. Тогда для получения подзадачи на шаге ветвления текущей итерации алгоритма ветвей и границ можно фиксировать значения переменной 0=ex или 1=ex для ребра e: 1) если хотя бы одна из ко- нечных вершин ребра e имеет максимальную степень; 2) если ребро e является ребром максимального числа путей между некоторыми парами узлов из N. Пер- вое правило ветвления эквивалентно принципу штрафования вершин, применя- емому для нахождения приближенного решения ЗКГ (см. [18]), и правилу ветв- ления, используемому при решении ЗСДС (см. [29]). При решении представлен- ных задач в табл. (см. разд. 9) второе правило более эффективно. 7. Алгоритм нахождения нижней оценки Рассмотрим LP-релаксацию задачи (10)–(13), т.е. задачу, полученную заме- ной ограничений (13) на 10 ≤≤ ex для всех .Ee∈ Как уже отмечалось, нижнюю оценку будем находить путем решения LP-релаксации задачи (10)–(13). При 1=k двойственную задачу к LP-релаксации задачи (10)–(13) можно записать так: найти Проблемы управления и информатики, 2006, № 1–2 197 ,)(2max ),(0 ∑∑ ∈∈ −− Eji ij r s Nr r r zuu (14) при ограничениях ,,),( 0NrEjiwuu r ij r i r j ∈∈≤− (15) ,),( 0 Ejizcw ijij Nr r ij ∈+≤∑ ∈ (16) .,),(0,0 0NrEjizw ij r ij ∈∈≥≥ (17) Для нахождения нижней оценки предложим простой строго полиномиальный алгоритм решения этой задачи. Сначала отметим следующее простое свойство за- дачи (14)–(17). Утверждение 5. Существует оптимальное решение ,, r ij r v wu ,Vv∈ ,0Nr ∈ Eji ∈),( задачи (14)–(17), для которого },,0{max r i r j r ij uuw −= где Eji ∈),( и .0Nr ∈ Доказательство. Допустим, что для некоторых Eji ∈),( и 0Nr∈ −< r ju0 .r ij r i wu <− В этом случае, уменьшая значение r ijw до величины ,r i r j uu − получим .r ij r i r j wuu =− Если же ,0r ij r i r j uu <− то положим .0=r ijw Ясно, что при этом значение целевой функции (14) не уменьшится. Поэтому можно предположить, что },0{max r i r j r ij uuw −= для всех Eji ∈),( и ,0Nr ∈ что и доказывает утвер- ждение. В силу утверждения 5 решение задачи (14)–(17) можно найти с помощью следующего алгоритма, весьма близкого к алгоритмам, применяемым при реше- нии ЗСДС [29, 30]. Для некоторого фиксированного узла 0Nr∈ сначала определяются значения переменных r vu для всех вершин ,Vv∈ потом по утверждению 5 для всех Eji ∈),( и для фиксированной вершины r значения переменных r ijw вычисляют- ся из равенства }.,0{max r i r j r ij uuw −= Для определения значения переменных r vu решаем задачу нахождения потока (с величиной, равной 2) минимальной стоимо- сти на графе G с источником s и стоком r с единичными пропускными способ- ностями и с весами ijc для всех ребер .),( Eji ∈ Тем самым определяем значение потенциалов vy для вершин v из V и два реберно-непересекающихся пути. Яс- но, что 0=sy и ry — длина второго кратчайшего пути, соединяющего s и .r По значениям vy находим значения переменных ,r vu r ijw для всех Eji ∈),( сле- дующим образом. Сначала положим ,0=r su r r r yu = и будем считать, что вершины ,s r про- смотрены и проанализированы. Пусть )(r+δ — множество вершин, смежных с r. Для вершины v из )(r+δ определим значения переменных :r vu если ,rv yy ≥ то ,r r r v uu = и если ,rv yy < то .v r v yu = Считаем, что вершины из 0},{\)( Vrsr =δ+ просмотрены, но не проанализи- рованы, а вершины из 0\VV не просмотрены и не проанализированы. Среди про- 198 ISSN 0572-2691 смотренных и не проанализированных вершин находим 00 Vv ∈ такую, что }.;{max 0 Vvuu r v r v ∈= Заменив r на ,0v указанным выше способом определяем значения переменных r vu для всех вершин из }.{\ 00 vVV +δ∩ После этого счита- ем, что вершина 0v просмотрена и проанализирована. Если ,\ 0 ∅≠VV то среди просмотренных и не проанализированных снова находим вершину ,1v для кото- рой }.;{max 01 Vvuu r v r v ∈= Таким же способом определяем значения переменных r vu для всех v из }.{\ 10 vVV +δ∩ Если ,\ 0 ∅=VV то все вершины V просмотрены и проанализированы. В этом случае по утверждению 5 положим },0{max r i r j r ij uuw −= для всех .),( Eji ∈ Из теории двойственности линейного программирования ясно, что неравен- ство r i r jij uuc −≤ может выполняться только для ребер первого кратчайшего пути. Поэтому положим },0{max ij r i r j r ij cuuz −−= для ребер этого пути, а затем моди- фицируем значения весов },0{max r ijijij wcc −= для всех ребер .),( Eji ∈ Произ- вольным образом выбираем ранее не фиксированную вершину t из 0N и изло- женным выше способом снова определяем значения переменных t vu и t ijw для всех v из .V После того как все вершины из 0N фиксированы, алгоритм завершает свою работу. Нетрудно понять, что таким образом определенные значения переменных ,r vu ,r ijw ijz удовлетворяют ограничениям задачи (14)–(17) и поэтому соответ- ствующее значение целевой функции (14) — нижняя оценка для ЗПНС. Трудоемкость описанного алгоритма в основном определяется трудоемко- стью )( 2nO построения дерева кратчайших путей в графе G с неотрицательными весами ребер при фиксированной вершине r из .0N Определение значения пе- ременных ,r vu r ijw требует )(mO или )( 2nO времени, поэтому временнáя слож- ность алгоритма оценивается как .)())()(( 322 nOnOnON ≅+ 8. Алгоритм нахождения верхней оценки В этом разделе предлагается алгоритм нахождения верхней оценки для ЗПНС путем определения допустимого решения задачи (10)–(13) при .1=k Каждому решению ЗПНС можно сопоставить подсеть исходной сети, которая содержит ре- бра, соответствующие переменным с положительными значениями в этом решении. Такую подсеть будем называть допустимой сетью. Сначала алгоритм определяет некоторую допустимую сеть, затем локальным поиском улучшаем ее структуру, т.е. уменьшаем стоимость. Таким образом находим допустимое реше- ние ЗПНС, и соответствующее значение целевой функции (10) — верхняя оценка для ЗПНС. На базе полученной информации при вычислении )lower(F этот алго- ритм определяет допустимую сеть следующим образом. Пусть ,r ijw ,),( Eji ∈ ,Nr∈ — значения соответствующих переменных, ко- торые определены при нахождении нижней оценки .)lower(F Рассмотрим под- граф ))(),(( 000 GEGVG = графа G со множествами ребер )( 0GE и вершин ),( 0GV где Проблемы управления и информатики, 2006, № 1–2 199         ∈== ∑ ∈ EjicwjiGE ij Nr r ij ),(,);,()( 0 и )( 0GV содержит все концевые вершины из множества ).( 0GE Веса ребер под- графа 0G такие же, как и у соответствующих ребер графа .G Легко показать, что реберная связность 0G не меньше двух. Теперь предложим алгоритм нахождения допустимой сети G на базе полу- ченной информации при вычислении .)lower(F Вначале )(GV и )(GE — пустые множества. На сети 0G находим кратчайшие пути между всеми парами узлов из множества .N Пусть L — список этих путей. В этом списке находим путь мини- мальной длины — ,1P который соединяет вершины 1v и .1w Из списка L удаля- ем путь 1P и все его вершины и ребра включаем во множества )(GV и )(GE со- ответственно. Снова в списке L находим путь минимальной длины, пусть это бу- дет ,2P и он соединяет вершины 2v и .2w Если степени вершин 2v и 2w в сети G не большее единицы, то вершины и ребра пути 2P включаем во множество )(GV и )(GE соответственно; в противном случае не включаем. Удалив путь 2P из списка L, повторяем этот процесс до тех пор, пока L не станет пустым списком. Таким образом, построим некоторую сеть и снова обозначим ее .G Для того чтобы построить сеть G со степенью вершин, большей или равной двум, найдем вершину v из )(GV со степенью один (если такая вершина суще- ствует). Удалив ребра )(GE из сети ,0G находим кратчайший путь, соединяю- щий v с некоторой вершиной из ).(GV Поскольку реберная связность 0G не меньше двух, то после удаления ребер множества )(GE из 0G в сети 0G обяза- тельно найдется кратчайший путь, соединяющий v с некоторой вершиной из ).(GV Таким образом, построим сеть (снова обозначим ее ),G степени вершин которой не меньше двух. Применяя алгоритм Гомори и Ху, проверяем двухсвязность сети .G Если мощность некоторого разреза меньше двух, удалив из сети 0G ребра, принадле- жащие ),(GE находим кратчайший путь, соединяющий вершины v и ,w которые отделены разрезом. Однако сеть G может содержать пути между некоторыми двумя узлами, такие, что после удаления ребер этих путей из сети G она остается допустимой. Для нахождения этих путей применяем следующую процедуру. Пусть ,vd wd — степени вершин ,v w в G и ,2>wd ,2>vd где ., Nwv ∈ На сети G известными способами находим не больше },{min wv ddk ≤ реберно-непересекающихся путей .,,1 kPP  Допустим, что эти пути упорядоче- ны по возрастанию их длины. Если 2>k и путь kP такой, что, за исключением вершин ,v w, все остальные его вершины принадлежат множеству ,\ NV то все ребра пути kP удаляем из .G Положив ,1: −= kk повторим этот процесс. Поскольку пути kPP ,,1  реберно-непересекающиеся, то после удаления ре- бер пути tP из сети G она остается допустимой сетью. Аналогично способу нахождения подграфа, изоморфного ,4KH = который описан в доказательстве теоремы 1, можем найти цикл длины 4 (если такой цикл 200 ISSN 0572-2691 существует) в сети .G Допустим, что ребра ,),( 11 wv ,),( 21 vw ),( 22 wv и ),( 12 vw лежат на этом цикле. Если , 12212211 wwvvwvwv cccc +<+ то, заменив ,),( 11 wv ),( 22 wv ребрами ,),( 21 vv ),,( 12 ww можно улучшить стоимость допу- стимой сети .G Таким образом, строится допустимая сеть G и соответствующее значение целевой функции (10) — .)upper(F Кроме этой процедуры, можно применить эвристические локальные алго- ритмы [32], использованные при решении задачи синтеза двухсвязной сети. Од- нако для применения этих алгоритмов локального поиска требуется найти под- графы с подходящими структурами в ,G и при этом неизвестно, будет ли стои- мость полученной допустимой сети лучше стоимости .G При решении ЗПНС временнáя сложность этих алгоритмов сравнима со временем, затрачиваемым на выполнение одного шага алгоритма ветвей и границ. Кроме того, в процессе ре- шения ЗПНС применение этих алгоритмов локального поиска и выполнение од- ного шага метода ветвей и границ эквивалентны по их выходом. Приведенные в следующем разделе результаты численных экспериментов показывают эффектив- ность алгоритма ветвей и границ с использованием предложенных алгоритмов нахождения нижней и верхней оценок. 9. Описание результатов численных экспериментов Предложенные в предыдущих разделах алгоритмы нахождения ,)lower(F )upper(F и второе правило ветвления реализованы в алгоритме ветвей и границ с односторонним обходом дерева решений и запрограммированы на языке C. При решении задач 1–6 (7–14), если относительная погрешность решения подзадачи, полученной на шаге ветвления, не превышает 5 (10) %, то в дереве решений соот- ветствующая подзадаче (изображающая ее) вершина считается висячей. Таблица № п/п Число вершин, n Число ребер, M Число узлов, N Оценки rF rnF Время, с нижняя lF верхняя uF 1. 8 12 4 20 20 20 0 0,1 2. 17 29 5 40 44 44 0 0,2 3. 38 65 8 552 553 553 0 0,2 4. 10 45 10 140 190 170 5 1,1 5. 15 105 10 113 118 116 1 9,2 6. 15 105 15 122 296 182 4 14,8 7. 20 190 10 54 112 104 5 647,8 8. 30 435 10 60 100 95 3 1841,92 9. 40 780 10 32 63 50 3 429,82 10. 50 1225 10 30 55 52 2 124,9 11. 50 1225 20 65 115 113 1 174,9 12. 50 1225 30 87 131 131 0 139,7 13. 50 1225 40 91 181 180 1 152,5 14. 50 1225 50 97 211 211 0 180,4 Результаты вычислительных экспериментов представлены в таблице, где rF — найденное рекордное значение для целевой функции (10) при ;1=k rnF — число изменения рекордного значения. Граф, представляющий сеть в задачах 2 и 3, является графом дорог для двух областей Украины. В задачах 4–14 сеть представляется полным графом. В качестве весов ребер выбирались случайные числа, между 0 и 100. Вычисления проводились на IBM c процессором 80486 (33 MГц, 8 Mбайт). Проблемы управления и информатики, 2006, № 1–2 201 Н.З. Шор, Ф.А. Шаріфов ЗАГАЛЬНА ЗАДАЧА СИНТЕЗУ НАДІЙНИХ МЕРЕЖ Розглядається важлива для розвитку теорії та практики задача проектування мережі мінімальної вартості, що продовжує функціонувати навіть при виході з ладу окремих її компонент. Кількість обмежень в моделі з потоковими змінни- ми 0 та 1 експоненційно залежить від кількості вузлів; показано, що LP-ре- лаксація цієї задачі NP-складна. Для окремих випадків доведено, що розв’язок відповідної LP-релаксації цієї задачі можна знайти за допомогою поліноміаль- ного алгоритму. Запропоновано ефективні алгоритми обчислення верхньої та нижньої границь для двозв’язної задачі Штейнера. Для розв’язання цієї задачі застосовується метод гілок та границь; наведено також результати обчислю- вальних експериментів. N.Z. Shor, F.A. Sharifov THE GENERAL RELIABILITY NETWORK DESIGN PROBLEMS We consider the important practical and theoretical problem of designing communica- tions network with a minimum total cost under condition that an optimal network must survive with respect to failures of certain its components. The model with 0, 1 — flow variables contains a number of constraints that is exponential in the number of nodes and we show that its LP-relaxation is NP-complete problem. For some particular cas- es, we prove that a solution of LP-relaxation problem can be found by polynomial time algorithm. We propose effective algorithms to compute lower and upper bounds for the two connected Steiner problem. For finding a solution of this problem we im- plement the branch and bound algorithm and we also report on some computational results. 1. Benzer S. On the topology of the genetic fine structure // Proc. Natl. Acadam., Sci. U.S. — 1959. — 45. — P. 1607–1620. 2. Басакер Р., Саати Т. Конечные графы и сети. — М. : Наука, 1974. — 366 c. 3. Hohcroft J., Tarjan R. An O (V logV ) algorithm for determining isomorphism of planar graphs // Inform. Proc. Lett. — Amesterdam : North Holland Publish. Comp. — 1971. — 1. — P. 32–34. 4. Burkard R.E. Selected topics on assignment problems // Disc. Appl. Math. — 2002. — 123. — P. 257–302. 5. Alt H., Blum N., Mehlhorn K., Paul M. Computing maximum cardinality matching in time )log/( 5,1 nmnO // Inform. Proc. Lett. — 1991. — 37. — P. 237–240. 6. Hopcroft J.E, Karp R.M. An 5,2n algorithm for maximum matching in a bipartite graph // SIAM J. Comput. — 1973. — 2. — P. 225–231. 7. Dell’Amico M., Paolo T. Algorithms and code for dense assignment problems: the state of the art // Discrete Appl. Mathemat. — 2000. — 100. — P. 17–48. 8. La Paugh A.S., Rivest R. L. The subgraph homeomorphism problem // J. Comput. System Sci. — 1980. — 20. — P. 133–149. 9. Ohtsuki T. The two disjoint path problem and wire routing design / N. Saito, T. Nishizeki eds //, Graph Theory and Algorithm, Lecture Notes in Comput. Sci. — Berlin : Springer, 1981. — 108. — P. 207–216. 10. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. — М. : Мир, 1985. — 510 c. 11. Seymour P.D. Disjoint paths in graphs // Discrete Math. — 1980. — 29. — P. 293–309. 12. Shiloach Y. A polynomial solution to the undirected two path problem // J. ACM — 1980. — 27. — P. 261–275. 13. Asano T. An approach to the subgraph homeomorphism problem // Theoret. Comput. Sci. — 1985. — 38. — P. 249–267. 202 ISSN 0572-2691 14. Шарифов Ф.А. Задача синтеза связных сетей относительно изоморфных подграфов // Ки- бернетика и системный анализ. — 2004. — № 5. — C. 126–131. 15. Stoet M. and Frank W. A Simple Min–Cut algorithm // J. ACM — 1997. — 44, N 4. — P. 585–591. 16. Nagamochi H., Ono H., Ibaraki T. Implementing an efficient minimum capacity cut algorithm // Math. Progr. — 1994. — 67, N 3. — P. 325–341. 17. Padberg M., Rinaldi G. An efficient algorithm for the minimum capacity cut problem // Math. Progr. — 1990. — 47, N 1. — P. 19–36. 18. Cook W.J., Cunningham W.H., Pulleyblank W., Schrijver S. Combinatorial optimization. — New-York : Jonh Wiley–Sons. Inc, 1998. — 355 p. 19. Vygen J. On dual minimum cost flow algorithms // Oper. Res. — 2002. — 56. — P. 101–126. 20. Orlin J.B. A faster strongly polynomial minimum cost flow algorithms // Ibid. — 1993. — 41. — P. 338–350. 21. Shor N.Z. Nondifferentiable optimization and polynomial problems. — N.-Y. : Kluwer Academ. Publ. 1998. — 339 p. 22. Харари Ф. Теория графов. — М. : Мир — 1973. — 300 c. 23. Kundu S. Bound on the number of disjoint spanning trees // J. of Comb. Theory B. — 1974. — 17. — P. 199–203. 24. Grotschel M., Monma C.L. Integer polyhedra arising from certain network design problems with connectivity constraints // SIAM. J. Disc. Math. — 1990. — N 4. — P. 502–522. 25. Шарифов Ф.А. Задача синтеза надежных сетей // Кибернетика и системный анализ. — 2000. — № 4. — C. 145–157. 26. Goemans M.X., Bertsimas D. J. Survivable networks, linear programming relaxations and the par- simonious property // Math. Progr. — 1993. — 60. — P. 145–166. 27. Winter P. Steiner problem in networks: A survey // Networks. — 1987. — 170. — P. 129–167. 28. Mehlhorn K. A faster approximation algorithm for the Steiner problem in graphs // Inform. Proc. Lett. — 1988. — 27. — P. 125–128. 29. Михалевич В.С., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно-тран- спортного планирования: Модели, методы, алгоритмы. — М. : Наука, 1986. — 264 c. 30. Трубин В.А., Шарифов Ф.А. Теоретическое и экспериментальное исследование задачи раз- мещения с ограничениями на мощности предприятий // Математические модели планиро- вания и управления сложными экономическими системами. — Киев : Ин-т кибернетики им. В.М. Глушкова АН УССР, 1986. — C. 8–14. 31. Трубин В.А., Шарифов Ф.А. Общая задача размещения // Теория и вычислительные про- блемы оптимизации. Сб. научн. тр. — Киев : Ин-т кибернетики им. В.М. Глушкова АН Ук- раины, 1993. — C. 16–20. 32. Monma C.L., Shallcross D.F. Methods for designing communications networks with certain two–connected survivability constraints // Oper. Res. — 1989. — 37, N 4. — P. 531–541. Получено 02.11.2005 1. Постановка общей задачи синтеза надежных сетей 2. Потоковая модель OЗCС 3. Частные случаи ОЗСС при первом способе задания графа H 4. Частные случаи ОЗСС при втором способе задания графа H 5. Задача проектирования надежных сетей 6. Численные методы решения ЗПНС 7. Алгоритм нахождения нижней оценки 8. Алгоритм нахождения верхней оценки 9. Описание результатов численных экспериментов № п/п

Ähnliche Einträge