Полиномиальность нахождения оценок в общей задаче синтеза надежных сетей
We consider the design minimum cost network problem under requirement that if edges of any isomorphic subgraph to given a graph, are deleted from the network then there exist a path between every pair of distinct nodes in the network. It is shown that when the graph has a simple structure the upper...
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2005 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2005
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84928 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Полиномиальность нахождения оценок в общей задаче синтеза надежных сетей / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 80-86. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860216935680049152 |
|---|---|
| author | Шарифов, Ф.А. |
| author_facet | Шарифов, Ф.А. |
| citation_txt | Полиномиальность нахождения оценок в общей задаче синтеза надежных сетей / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 80-86. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | We consider the design minimum cost network problem under requirement that if edges of any isomorphic subgraph to given a graph, are deleted from the network then there exist a path between every pair of distinct nodes in the network. It is shown that when the graph has a simple structure the upper and lower bounds for this problem can be defined by polynomial time algorithm.
|
| first_indexed | 2025-12-07T18:16:15Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2005, № 4 80
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассматривается задача синтеза
сетей при условии, что между
двумя вершинами в проектируе-
мой сети существует хотя бы
один путь, соединяющий произ-
вольную пару ее узлов, после уда-
ления из нее ребер подграфа, изо-
морфного к заданному графу. По-
казано, что в случаях, когда по-
следний граф имеет простую
структуру, верхняя и нижняя
оценки по функционалу могут
быть определены за полиноми-
альное время.
Ф.А. Шарифов, 2005
УДК 519.8
Ô.À. ØÀÐÈÔÎÂ
ÏÎËÈÍÎÌÈÀËÜÍÎÑÒÜ ÍÀÕÎÆÄÅÍÈß
ÎÖÅÍÎÊ Â ÎÁÙÅÉ ÇÀÄÀ×Å ÑÈÍÒÅÇÀ
ÍÀÄÅÆÍÛÕ ÑÅÒÅÉ
Пусть заданы неориентированные графы
),( EVG = и ))(),(( HEHVH = ,
множество терминальных вершин или узлов
VN ⊆ , неотрицательные веса ec для всех
ребер e из E . Подграф 0G графа G опре-
делен подмножеством EE ⊆0 , если
00 )( EGE = и множество вершин )( 0GV со-
держит конечные вершины всех ребер из 0E .
Вес произвольного подграфа 0G определяет-
ся как сумма весов его ребер.
Общая задача синтеза надежных сетей
(ОЗСС) состоит в нахождении подграфа
),( *** EVG = (определенный с EE ⊆* ) с
минимальным весом такого, что после уда-
ления ребер любого подграфа Γ из графа
G , изоморфного заданному графу H , в под-
графе ),( *** EVG = существует хотя бы
один путь, соединяющий произвольную пару
узлов из N .
Следует отметить, что та же задача при
дополнительном условии удаления вершин
подграфа Γ , изоморфного заданному графу
H , известными способами сводится к ис-
ходной задаче. В результате этой операции
увеличивается только размер задачи. Поэто-
му здесь не рассматриваем условия сущест-
вования пути между всеми парами узлов сети
при удалении вершины подграфа Γ . В ОЗСС
предполагаем, что G – конечный, связный
граф. Другими словами, множества V и E
содержат конечное число элементов. При
этом граф H может быть задан с помощью
множеств )(HV и )(HE , количество
Ф. А. ШАРИФОВ
Теорія оптимальних рішень. 2005, № 4 81
элементов в которых конечно. Поэтому для ОЗСС имеет смысл рассматривать
граф H с конечными множествами его вершин и ребер. В некоторых случаях
множества )(HV и )(HE не задаются в явном виде, но известно, что граф H
может быть произвольным графом с выделенной структурой. В этом случае яс-
но, что должны выполняться условия | )(HV | ≤ | |V . Например, допустим, что
H – связный простой граф без циклов с двумя висячими вершинами, т.е. граф
H является простым путем. Отсюда следует число ребер графа H не больше,
чем | 1| −V . Отметим, что если H – тривиальный граф, то ОЗСС и задача Штей-
нера на графах эквивалентны. Другой вырожденный случай ОЗСС соответству-
ет тому, что в графе G не существуют ни одного подграфа, изоморфного H .
Вырожденные случаи ОЗСС также возникают на практике. Так как в дальней-
шем будем рассматривать только невырожденные случаи ОЗСС, здесь рассмот-
рим одну задачу из молекулярной биологии, которая сводится к вырожденному
случаю ОЗСС.
B работе [1] сформулирована следующая задача о возможных соединениях в
допустимых конфигурациях химических компонентов генов. Если такими ком-
понентами являются трехмерные молекулы, то они могут быть соединены вме-
сте в соответствии с определенной структурой. Это объединение может быть
представлено в трехмерном пространстве, если каждой молекуле поставлена в
соответствие некоторая вершина, и вершины соединены прямыми линиями при
наличии связи между соответствующими молекулами. Возникает вопрос: можно
ли расположить молекулы на одной и той же прямой линии так, чтобы они со-
хранили прежние связи? Каждая молекула представляется при этом отрезком
прямой. Если пара молекул связана, то соответствующие им отрезки взаимно
перекрываются. Таким образом, задача состоит в нахождении условий, при ко-
торых граф связей можно представить с помощью пересекающихся определен-
ным образом отрезков одной прямой линии, т.е. необходимо так сопоставить
отрезки с вершинами, чтобы два отрезка пересекались тогда и только тогда, ко-
гда они соответствуют смежным вершинам. Граф, который может быть пред-
ставлен таким образом, называется графом отрезков.
В работе [1] показано, что если граф не содержит ни одного подграфа,
изоморфного одному из пяти графов, представленных в [1], то он может быть
изображен с помощью отрезков на линии. Таким образом, получаем, что если
решения ОЗСС на графе G для всех указанных в [1] типов графа H являются
деревьями Штейнера, то G можно представить с помощью отрезков на линии.
Легко понять, что задача Штейнера с множеством основных вершин N и с
множеством вершин Штейнера NV \ имеет решение на графе G тогда и только
тогда, когда G содержит связный подграф, множества вершин которого содер-
жит N . Таким образом, когда H – тривиальный граф, имеем достаточное и
необходимое условие существования решения ОЗСС. Для общего случая усло-
вия существования решения ОЗСС также можно сформулировать, однако про-
верка их выполнимости не так проста. Для этого рассмотрим задачу о допусти-
ПОЛИНОМИАЛЬНОСТЬ НАХОЖДЕНИЯ ОЦЕНОК В ОБЩЕЙ ЗАДАЧЕ…
Теорія оптимальних рішень. 2005, № 4 82
мости: содержит ли данный граф G подграф 0G , в котором существует хотя бы
один путь, соединяющий произвольную пару узлов из N при удалении из G
ребра любого подграфа Γ графа G , изоморфного заданному графу H .
Утверждение 1. Задача о допустимости имеет решение тогда и только то-
гда, когда множество ребер произвольного подграфа 1G графа G , изоморфного
H , не образует разрез в графе G .
По утверждению 1 задача о допустимости сводится к задаче изоморфизма
подграфу. Для этого надо найти в G некоторый подграф 1G . Если ребра 1G об-
разуют разрез, то задача о допустимости не имеет решения. В противном случае
все вершины 1G стягиваются в один узел, и в полученном графе находим под-
граф, изоморфный графу H , и т. д.
После удаления из G ребер подграфа 1G (найденного на некотором этапе),
если G распадается на несколько компонентов связности, то задача о допусти-
мости не имеет решения и в этом случае ясно, что характеристический вектор
подграфа 1G не удовлетворяет разрезному неравенству. Учитывая, что для за-
данного вектора задача выполнимости разрезных неравенств принадлежит к
классу P , во многих задачах синтеза сетей эти неравенства используются для
уменьшения разрыва двойственности [2, 3].
Математическая модель ОЗСС имеет следующий вид [2]:
∑
∈Ee
ee xcmin (1)
−
=−∑ ∑
Γδ∈ Γδ∈ ,1
,0
,1
))(( ))((ij ij
r
ji
r
ij xx
при
при
при
,
,0
,0
ri
ri
i
=
≠
=
, ,Vi ∈ 0, Nr ∈ , Ω∈Γ , (2)
e
r
ij xx ≤≤0 , 0Nr ∈ , ,),( Ejie ∈= (3)
,10 ∨=ex ,Ee∈ (4)
где }0{\0 NN = ; ))(( iΓδ – множество ребер, соединяющих вершину i с ос-
тальными вершинами на графе, который получается после удаления всех ребер
Γ из графа G ; Ω –множество изоморфных H подграфов графа G .
Ограничения (2), написанные для всех Γ из Ω , избыточны в том смысле, что
можно определить некоторое минимальное по включению подмножество 0Ω
подграфов из Ω , такое, что при замене условия Γ из Ω на Γ из 0Ω в ограни-
чениях (2) решение ОЗСС не будет меняться. Число | 0Ω | назовем точным чис-
лом ограничений (2).
Утверждение 2. Задача определения | 0Ω | является NP -полной.
Доказательство. Рассмотрим задачу Штейнера на графе G с множеством
основных вершин N и вершин Штейнера NV \ . Допустим, что *T – оптималь-
Ф. А. ШАРИФОВ
Теорія оптимальних рішень. 2005, № 4 83
ное решение этой задачи или, как часто называют, *T – оптимальное дерево
Штейнера. Рассмотрим ОЗСС для графа H , где }{)( gHE = и g – некоторое
фиксированное ребро графа G . Допустим, что g не является ребром дерева *T .
Тогда ОЗСС на графе G и ОЗСС на графе }){\,()( gEVgG = эквивалентны. От-
сюда следует, что для нахождения избыточных ограничений в (2), надо прове-
рить условие g ∈ *T . Следовательно, нахождение избыточных ограничений сво-
дится к определению: является ли ребро g ребром дерева *T или нет, что не-
возможно осуществить за полиномиальное время, так как задача Штейнера
NP -полная.
Аналогично доказывается следующее утверждение.
Утверждение 3. Если в Ω не существует подграф, который не содержит хо-
тя бы одно ребро оптимального дерева *T Штейнера, то *T является оптималь-
ным решением ОЗСС.
Согласно утверждениям 2 и 3 получаем, что множество вершин каждого
подграфа Γ из Ω должно содержать хотя бы одно ребро оптимального дерева
Штейнера. Следовательно, надо рассматривать только те подграфы Γ из Ω ,
которые содержат различные ребра оптимального дерева Штейнера. Отсюда по-
лучаем, что | 0Ω | 1|| −≤ V .
Пусть ),( jiΗ – множество подграфов, которые изоморфны H и содержат
ребро ),( ji . Пусть ),(\),(0 jiji ΗΩ=Η . Рассмотрим двойственную задачу к (1)
– (3):
∑ ∑
∈ Η∈Γ
Γ−Γ
0
)()(max
),(Nr
r
s
ji
r
r uu ,
∑
Η∈Γ
≤Γ−Γ
),(
)()(
ji
r
ij
r
i
r
j wuu , 0Nr ∈ , Eji ∈),( ,
∑
∈
≤
0Nr
ij
r
ij cw , ,0Nr ∈ Eji ∈),( ,
0≥
r
ijw , ,0Nr ∈ Eji ∈),( .
Число переменных этой задачи экспоненциально зависит от числа вершин графа
G . Путем замены ∑
Η∈Γ
Γ
),(
)(
ji
r
iu на r
iu двойственную задачу можно представить в
следующем виде:
∑
∈
−
0
max
Nr
r
s
r
i uu (5)
)()(
j)(i,
r
j Γ−Γ+≤− ∑
Η∈Γ
r
i
r
ij
r
i
r
j uuwuu , 0Nr ∈ , Eji ∈),( , (6)
ПОЛИНОМИАЛЬНОСТЬ НАХОЖДЕНИЯ ОЦЕНОК В ОБЩЕЙ ЗАДАЧЕ…
Теорія оптимальних рішень. 2005, № 4 84
∑
∈
≤
0Nr
ij
r
ij cw , ,0Nr ∈ Eji ∈),( , (7)
0≥
r
ijw , ,0Nr ∈ Eji ∈),( . (8)
Утверждение 4. Существует оптимальное решение задачи (5) – (8), такое,
что 0)()( ≠Γ−Γ
r
i
r
j uu только для одного подграфа Γ из ),( jiΗ .
Доказательство. Допустим, что существуют хотя бы два подграфа
1Γ , 2Γ ∈ ),( jiΗ , такие, что 0)()( ≠Γ−Γ k
r
ik
r
j uu для k = 1,2. В этом случае легко
можно переопределить значения для разницы двойственных переменных таким
образом, после чего оптимальное значение целевой функции (5) не изменится и
ограничения (6) не нарушатся. Аналогично переопределив значения разницы
двойственных переменных, когда алгебраическая сумма их не равна нулю, дока-
зываем справедливость утверждения.
По утверждению 4 ограничения (6) можем заменить на следующие условия:
)),(()),(( jiujiuwuu
r
i
r
j
r
ij
r
i
r
j Γ−Γ+≤− , 0Nr ∈ , Eji ∈),( , (9)
где ),( jiΓ – произвольный подграф, который содержит ребро ),( ji и изоморф-
ный H . Следовательно, если граф H имеет простую структуру, то ),( jiΓ мож-
но определить за полиномиальное время, и в этом случае получим задачу ли-
нейного программирования (5), (7) – (9), для которой число переменных оцени-
вается как )|(| 3
VO . Так как прямая задача (1) – (4) является линейной релакса-
цией ОЗСС, то, решив задачу (5), (7) – (9) с помощью одного из существую-
щих методов решения общей задачи линейного программирования, можно оп-
ределить нижнюю оценку для функционала ОЗСС за полиномиальное время.
Если H – граф типа дерева, паросочетания и т.д., то понятно, что ),( jiΓ может
быть определен за полиномиальное время.
Теперь, пусть H – произвольный лес с числом ребер не больше, чем k .
Теорема 1. Задача существования решения ОЗСС, где VN = и H – произ-
вольный лес с k числом ребер, имеет решение тогда и только тогда, когда ре-
берная связность графа G равна 1+k .
Доказательство. Пусть H – некоторый лес и kHE =|)(| . Покажем, что ес-
ли реберная связность графа G равна 1+k , то ОЗСС имеет хотя бы одно допус-
тимое решение. Допустим, что из графа G удалены ребра произвольного под-
графа, изоморфного H . Если в полученном графе не существует ни одного пу-
ти, соединяющего хотя бы одну пару узлов из N , то получаем, что реберная
связность графа G меньше чем 1+k . Это противоречие доказывает тогда и
только тогда часть теоремы. Для доказательства второй части теоремы пока-
жем, что если реберная связность графа G равна k , то ОЗСС не имеет реше-
ния. Пусть реберная связность графа G равна k . Тогда в G существуют k
Ф. А. ШАРИФОВ
Теорія оптимальних рішень. 2005, № 4 85
различных ребер kee ,...,1 , после удаления, которых граф G распадается на не-
сколько компонент связности. По определению реберной связности графа полу-
чаем, что множество ребер kee ,...,1 является минимальным по включению. По-
этому подграф, определенный множеством ребер kee ,...,1 , не содержит циклов,
т.е. он изоморфный некоторому лесу с числом ребер k , т.е. графу H .
Согласно этой теореме, в данном случае ограничения (2) можно заменить на
условия существования 1+k реберно-непересекающихся путей между всеми
парами узлов из N , и, таким образом, число переменных и число ограничений
ОЗСС будут выражаться как полином третьей степени от числа вершин графа
G . На базе этого свойства предложены алгоритмы нахождения верхней и ниж-
ней оценок для оптимального значения ОЗСС при в 1=k и ||||2 VN ≤≤ .
Рассмотрим еще один случай ОЗСС, когда VN = и множество ребер )(HE
графа H содержит по одному ребру из всех реберно-непересекающихся про-
стых циклов в G . Этот случай ОЗСС интересен тем, что в реальных ситуациях
для защиты информационного потока в линиях сетей связи каждая линия долж-
на лежать на замкнутой части сети. Относительно этого случая ОЗСС можем
доказать следующее утверждение.
Теорема 2. Задача существования решения ЗСНС при условии, что VN = и
множество ребер )(HE графа H содержит по одному ребра из всех простых
реберно-непересекающихся циклов, имеет решение, если реберная связность
графа G равна 4.
Доказательство. Справедливость утверждения теоремы можно показать
используя следующий результат, который доказан в [4]: если реберная связ-
ность графа G равна 4, то в G существуют два реберно-непересекающиеся ос-
товные деревья. Допустим, что из каждого q простого реберно-
непересекающегося цикла удалено одно ребро. Пусть 1T и 2T – два реберно-
непересекающиеся остовные деревья в графе G . Понятно, что ребра деревьев 1T
и 2T образуют простые циклы в графе G , и некоторые из этих циклов могут
иметь общие ребра, а некоторые нет. Поэтому при удалении по одному ребру из
каждого простого цикла, не имеющего общих ребер с другими циклами, отстав-
шие ребра этих циклов лежат на путях, соединяющих концевые вершины уда-
ленных ребер. Так как произвольное остовное дерево содержит хотя бы одно
ребро из каждого реберно-непересекающегося простого цикла, то удаленное
ребро может быт ребром либо 1T , либо 2T . Поэтому после удаления ребра мно-
жества )(HE из графа G в полученном графе существует хотя бы один путь
между всеми парами узлов из VN = , что и доказывает теорему.
Для рассмотренных случаев графа H решение задачи о допустимости на-
ходится за полиномиальное время. Также проведены эксперименты на эффек-
тивность алгоритмов нахождения нижней и верхней оценок в случае, когда H
ПОЛИНОМИАЛЬНОСТЬ НАХОЖДЕНИЯ ОЦЕНОК В ОБЩЕЙ ЗАДАЧЕ…
Теорія оптимальних рішень. 2005, № 4 86
имеет две вершины и одно ребро. Эти оценки могут быть также использованы
для определения мишени (taget) в схеме метода ветвей и границ [5].
Ф.А. Шаріфов
ПОЛІНОМІАЛЬНІСТЬ ЗНАХОДЖЕННЯ ОЦІНОК У ЗАГАЛЬНІЙ ЗАДАЧІ СИНТЕЗУ
НАДІЙНИХ МЕРЕЖ
Розглядається задача синтезу мереж за умови, що між двома вершинами мережі є хоча б один
шлях, що з'єднує довільну пару її вузлів, після вилучення ребер підграфа, ізоморфного зада-
ному графу. Показано, що у випадку, коли останній граф має просту структуру, нижня та
верхня оцінки можуть бути ефективно визначені за допомогою поліноміального алгоритму.
F.A. Sharifov
POLYNOMIAL SOVABILITY OF FINDING THE BOUNDS FOR GENERAL DESIGN
REABILITY NETWORKS PROBLEM.
We consider the design minimum cost network problem under requirement that if edges of any iso-
morphic subgraph to given a graph, are deleted from the network then there exist a path between
every pair of distinct nodes in the network. It is shown that when the graph has a simple structure
the upper and lower bounds for this problem can be defined by polynomial time algorithm.
1. Benzer S. On the Topology of the Genetic Fine Structure // Proc. Natl. Acad., Sci. U.S. –
1959. – 45. – P. 1607–1620.
2. Шарифов Ф.А. Задача синтеза связных сетей относительно изоморфных подграфов
// Кибернетика и системный анализ. – 2003. – №4. – С. 126–131.
3. Kerivin H., Mahjoub A.R. Separation of partition inequalities for (1,2) survivable network
design problem // Oper. Res. Lett. – 2002. – 30, N 4. – P. 265–268.
4. Kundu S. Bound on the number of disjoint spanning trees // J. of Comb. Theory. – 1974. –
17. – P. 199–203.
5. Volker S. Target-oriented branch and bound method for global optimization // J. of global
optimization. – 2003. – 23, N 3. – P. 261–277.
Получено 22.03.2005
|
| id | nasplib_isofts_kiev_ua-123456789-84928 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T18:16:15Z |
| publishDate | 2005 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шарифов, Ф.А. 2015-07-17T05:50:35Z 2015-07-17T05:50:35Z 2005 Полиномиальность нахождения оценок в общей задаче синтеза надежных сетей / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 80-86. — Бібліогр.: 5 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84928 519.8 We consider the design minimum cost network problem under requirement that if edges of any isomorphic subgraph to given a graph, are deleted from the network then there exist a path between every pair of distinct nodes in the network. It is shown that when the graph has a simple structure the upper and lower bounds for this problem can be defined by polynomial time algorithm. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Полиномиальность нахождения оценок в общей задаче синтеза надежных сетей Polynomial sovability of finding the bounds for general design reability networks problem Article published earlier |
| spellingShingle | Полиномиальность нахождения оценок в общей задаче синтеза надежных сетей Шарифов, Ф.А. |
| title | Полиномиальность нахождения оценок в общей задаче синтеза надежных сетей |
| title_alt | Polynomial sovability of finding the bounds for general design reability networks problem |
| title_full | Полиномиальность нахождения оценок в общей задаче синтеза надежных сетей |
| title_fullStr | Полиномиальность нахождения оценок в общей задаче синтеза надежных сетей |
| title_full_unstemmed | Полиномиальность нахождения оценок в общей задаче синтеза надежных сетей |
| title_short | Полиномиальность нахождения оценок в общей задаче синтеза надежных сетей |
| title_sort | полиномиальность нахождения оценок в общей задаче синтеза надежных сетей |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84928 |
| work_keys_str_mv | AT šarifovfa polinomialʹnostʹnahoždeniâocenokvobŝeizadačesintezanadežnyhsetei AT šarifovfa polynomialsovabilityoffindingtheboundsforgeneraldesignreabilitynetworksproblem |