Содержание к диссертации
Введение
Глава 1. Исследование уязвимости многопродуктовой сети с помощью теоретико-графовых и потоковых методов 11
1. Основные предположения и формулировки 11
2. Исследование задачи анализа уязвимости МП-соти с помощью потоковых методов 17
3. Исследование задачи анализа уязвимости МП-сети с помощью теоретико-графовых методов 21
4 О сложности решения общего случая задачи анализа уязвимости МП-сети и о построении приближенного решения 26
Глава 2. Исследование уязвимости многопродуктовой сети с помощью формализма простых разрезов 31
1. Свойства просгых разрезов графа 31
2 Способы построения простых разрезов 41
3. Алгоритм построения простых разрезов 51
Глава 3. Исследование уязвимости многопродуктовой сети с помощью формализма несократимых разрезов 59
1. Свойства несократимых разрезов сеги 59
2. Схема метода ветвей и границ, для задачи анализа уязвимосіи многопродуктовой сеіи 69
3. Алгоритм комбинирования простых разрезов 84
Глава 4. Результаты модельного вычислительного эксперимента
1 Построение и исследование на уязвимость модели междугородной телефонной сети на территории РФ
2 Исследование уязвимости моделей со случайными физическими и логическими графами сети
Заключение
Список литературы
- Исследование задачи анализа уязвимости МП-сети с помощью теоретико-графовых методов
- Способы построения простых разрезов
- Схема метода ветвей и границ, для задачи анализа уязвимосіи многопродуктовой сеіи
- Исследование уязвимости моделей со случайными физическими и логическими графами сети
Введение к работе
Актуальность темы. В связи с анализом функционирования реальных территориально-распределенных систем таких, как топливно-энергетические комплексы, сети связи и управления, Интернет, возникает вопрос о способности системы удовлетворять заданным требованиям при наличии произвольных неслучайных возмущений, таких как: масштабные аварии, техногенные катастрофы, военные и террористические действия, диверсии и т.п. Необходимость априорной оценки последствий подобных воздействий приводит к проблеме анализа уязвимости сетевых систем.
В потоковой сети возможно наличие потоков единственного продукта с несколькими источниками и стоками (например, водопровод), множества взаимозаменяемых продуктов (например, топливно-энергетический комплекс, в котором один вид топлива, как правило, может быть заменен другим и перераспределен между потребителями) или группы невзаимозаменяемых продуктов (например, телефонная сеть, в ней потоки — разговоры каждой пары абонентов соответствуют как бы определенным "видам" продуктов, которые в сети не могут перемешиваться или перераспределяться между другими пользователями). Математической моделью для изучения уязвимости сетевых систем первых двух типов служит однопродуктовая сеть, при исследовании систем третьего типа рассматривается многопродуктовая сеть (МП-сеть).
Для оценки уязвимости изучаемой системы моделируется разрушение соответствующей однопродуктовой или МП-сети. При этом анализ уязвимости конкретной модели сводится к исследованию того, как определенный вид разрушений влияет на связность, обеспеченность потоковых требований, ущерб пользователей, затраты на восстановление или другие функциональные характеристики сети, интересующие исследователя.
Данная работа ориентирована на изучение потоковых задач анализа уязвимости МП-сети при условии выхода из строя (пол-
ностью) одного или нескольких, заранее не известно каких, ребер, так, что передача потока хотя бы для одной пары источник — сток становится невозможной. Исследуются характеристики уязвимости, связанные с потерями разделенных пользователей МП-сети, а именно с количеством требований на передачу потоков, которые не выполняются вследствие разрушения системы. С учетом длительности процесса восстановления, проблема априорной оценки ущерба пользователей в указанном смысле представляется одной из наиболее актуальных.
Целью работы является создание и изучение модели, позволяющей до удара оценить ущерб, который может быть нанесен вследствие целенаправленного разрушения МП-сети. Критерием уязвимости выбрана гарантированная (наихудшая) оценка ущерба разделенных пользователей поврежденной сети.
Методы исследования, применяемые в работе, используют математический аппарат теории исследования операций, методы теории графов, дискретного программирования, комбинаторной и многокритериальной оптимизации.
Обоснованность научных положений. Теоретические положения и выводы диссертации сформулированы в виде утверждений, лемм, теорем и строго доказаны. Достоверность полученных результатов подтверждена экспериментальной проверкой алгоритмов и программ на модельных данных для задач реальной размерности.
Научная новизна. Предложена новая модель, позволяющая заранее оценивать уязвимость МП-сети, подвергающейся неслучайному разрушающему воздействию. Для анализа уязвимости предложен ряд формальных постановок в виде двух-критериальных лексикографических задач оптимизации. Выделены случаи, когда предложенные постановки полиномиально разрешимы, указаны соответствующие алгоритмы. Обоснована возможность использования свойств несократимых и простых разрезов для решения общего случая рассматриваемой задачи, разработаны соответствующие алгоритмы.
Практическая ценность. Разработан математический аппарат для решения задачи анализа уязвимости МП-сети, который позволяет выявить узкие места моделируемой сетевой системы, спрогнозировать возможный ущерб до ее разрушения и в дальнейшем укрепить или модернизировать систему, сведя к минимуму реальные потери.
Апробация работы. Результаты диссертации докладывались на: 2-й (1998) и 3-й (2001) Московских международных конференциях по исследованию операций; IX международной конференции "Проблемы функционирования информационных сетей"в г. Новосибирск (2006). Ряд результатов диссертации использовался в работе по проектам РФФИ № 98-01-00233, 01-01-00502, 04-01-00203.
Публикации. По материалам диссертации опубликовано 7 печатных работ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы из 141 наименования. Общий объем работы — 131 страница, включая 14 рисунков и 7 таблиц.
Исследование задачи анализа уязвимости МП-сети с помощью теоретико-графовых методов
Задача анализа уязвимости сети в постановках 1,1 ,2,2 предполагает поиск такого множества ребер, что его удаление из сети разрушит все пути соединения хоія бы для одной тяготеющей пары, и, соответственно, минимизирует или максимизирует второй критерий. Другими словами, требуется найти разрез с определенными свойствами для выделенной пары (или множества пар) вершин. Схожие задачи о построении разрезов с различными свойствами исследуются теорией графов в разделе, изучающем связность [35]. Под связностью далее будем подразумевать реберную связность [10].
Определение 7. Неориентированный граф G = {N,A) называется к-связным относительно пары вершин v\,V2 Є V, если после удаления любых (к — 1) ребер останется путь, соединяющий v\ и V2- Граф G называется к-связным, если он к-связеп относительно любой пары вершин
Определение 8. Числом реберной связности называется наименьшее число ребер, удаление которых приводит к несвязному графу.
Определение 9. Остовным деревом называется подграф данного графа, содержащий все его вершины и являющийся деревом.
Сформулируем несколько классических задач теории графов, результаты решения которых позволяют исследовать некоторые частные случаи задачи анализа уязвимости сети. I Задача о минимальном разрезе графа [49]. Дан граф G = (V, Л), вес каждого ребра c(r),C : А - N. Найти разрез минимального веса, разделяющий данный граф на две непустые части. II Задача о связностных характеристиках графа [15, 35]. Дан граф G — {V,A), и целые числа 5, к. Существует ли fc-элементное множество А С А такое, что G — A! состоит по крайней мере из 5 связных компонент? В случае 5 = 2, задача II называется задачей о поиске числа к реберной связности и по сути является задачей о минимальном разрезе для графа с единичными весами ребер. Ill Задача о минимальном -разрезе [49]. Дан граф G = (V, Л), вес каждого ребра с(г),С : А —» N, и целое число 8. Найти разрез минимального веса, разделяющий данный граф на 5 непустых частей
В общем случае задача о минимальном разрезе являеіся полиномиально разрешимой, и для ее решения традиционно используюіся потоковые методы. Однако все чаще им на смену приходят более быстрые алгоритмы, опирающиеся на вероятностные [42-44], эвристические [78], и другие [87, 123] методы Общий случай задачи о связноегных характеристиках графа является iVP-полным для любого 2 5 п [35]. Задача о минимальном (5-разрезе iVP-трудна для любого 2 5 п [49], и полиномиально разрешима в случае построения приближенного решения [117].
Используя задачу о поиске числа к реберной связности для графа многопродуктовой сети с единичной пропускной способностью, можно определить достаточное условие для случая, когда решения задачи уязвимости в рассматриваемых постановках не существует. Действительно, если для графа с единичной пропускной способноеіьіо ребер число реберной связности к /о, то задача в постановках 1 ,2 решения не имеет.
В задачах I—III, как и в рассматриваемых постановках задачи анализа уязвимости МП-сети, предполагается поиск разрезов, удаление которых из сети нарушает связность исследуемых графов В первом случае изучается только структура графа: определяется число ребер, или вес соответствующего разреза. Во втором случае мы пытаемся увеличить число разъединенных тяготеющих пар, удаляя ребра, при этом граф сети становится несвязным. Однако разделение графа сети на две или более связных компонент в общем случае не означает разъединение хотя бы одной тяготеющей пары в сети (источник и сток могут оказаться в одной связной компоненте для всех видов продуктов). Таким образом, расположение тяготеющих пар, наличие транзитных вершин и требований на поток в общем случае определяет недостаточность методов, используемых при решении задач 1-ІII, для исследования уязвимости многопродуктовых сетей Тем не менее, нарушение связности графа дает решение задачи в постановках 2,2 для МП-сети в случае, когда множество Np вершин графа тяготений Gp совпадает со всем ./V, и граф Gp содержит остовное дерево физического графа G. Такой граф тяготений обозначим Gp0. В самом деле, если граф тяготений Gp состоит из одной связной компоненты, то разбиение G на две части автоматически влечег за собой разделение хотя бы одной тяготеющей пары, так как в G нет транзитных вершин
В случае Gp решения задачи анализа уязвимости в посіановках 2,2 могут быть найдены с помощью полиномиального алгоритма решения задачи поиска минимального разреза графа G [14]. Этот алгоритм позволяет построить любой минимальный разрез для графа, ребра которого имеют единичную пропускную способность Его работа основывается на следующих свойствах сгруктурного графа Г((?) [8]:
1) любой минимальный реберный разрез графа G является минимальным реберным разрезом графа Г(С) и его можно найти за 0(п) операций (п — число вершин в графе G);
2) любые два простых цикла в Г((?) имеют не более одной общей вершины, и число ребер Г(С?) равно 0(п).
Алгоритм построения структурного графа имеет оценку трудоемкости 0(па), (а — число ребер графа G), минимальный реберный разрез по графу T(G) можно найти за 0(п) операций, следовательно, минимальный реберный разрез графа G можно построить за 0(па) операций
Для графа G с тяготениями Gp минимальный реберный разрез является минимальным сетевым, поэтому решение задачи А в постановке 2 — минимальный реберный разрез, построенный для графа G, все ребра которого имеют единичную пропускную способность. Если число ребер в минимальном сетевом разрезе не превосходит /о, то это — решение. Иначе — нет решения.
Способы построения простых разрезов
Для построения множества % всех простых разрезов сети предлагается использовать полиномиальный алгоритм помеюк ПОИСК, приведенный в работе [33]. Алгоритм начинает свою работу с выделенной вершины и, просматривая один раз матрицу смежности данного графа, помечает все вершины и ребра той связной компоненты, которой принадлежит эта вершина Если граф G = (N, А) являеіся связным, то будут помечены все его вершины. Опишем в общих чертах иосіроение множества 1Z.
Выберем произвольную вершину уг графа G. С помощью алгоритма ПОИСК определим, являеіся ли подграф G\{v%} связным. Если он связен, то согласно свойству 2 простого разреза, множество ребер Я!, соединяющих vt и G\{vt}, — простой разрез. Просмотрим множество А графа G, выберем из него все ребра г = (ьг,ь), для которых v Є N\{vi}, и поместим их в В!. Таким образом, первый простой разрез R! построен Поместим его в множество 11. Если подграф (?\{ J не является связным, рассмотрим следующую вершину Vj. Эту процедуру проведем для каждой вершины G
Выберем произвольную пару смежных вершин vt, Vj графа G. Положим G = (N2,A2), где N2 = {vt,Vj},A2 = {г}, г = {vt,Vj), и рассмотрим G\G С помощью алгоритма ПОИСК определим, является ли подграф G\G связным. Если он связен, то по свойству 2 простого разреза множество ребер, соединяющих вершины из G и G\G , простой разрез. Определим его, просмотрев множество всех ребер графа G Если G\G не является связным, то в качестве G рассмотрим другую пару смежных вершин и ребро, их соединяющее Эту процедуру проведем для каждой пары смежных вершин графа G. Таким образом, мы последовательно построим все простые разрезы, отделяющие от G всевозможные пары смежных вершин. И так далее.
Опишем эту процедуру для случая, когда в множестве Nk отделяемого порожденного подграфа G = (Nk, Ak), Nk С N, Ak С А, к вершин. В множество Ak входят все ребра г из Л такие, что г = (vt, v3), v% Є Nk, Vj Є Nk-Если порожденный подграф G не является связным, то его в качестве отделяемого множества рассматривать не будем. Подграф G\G определяется множеством вершин vm Є N\Nk, и множеством всех ребер г = (vm,vi), таких чго г A, vm Є N\Nk,vi Є N\Nk- С помощью алгоритма ПОИСК определим, является ли подграф G\G связным. Согласно свойству 2 простого разреза, если G\G связен, то множество R , состоящее из ребер г — (vp,vq),Vp Є Nk,vq Є N\Nk, соединяющих С и G\G — простой разрез. Определим ребра разреза R , просмоірев множество А всех ребер графа G. Если подграф G\G не являеіся связным, рассмотрим следующую связную компоненту G = {Nk, Ak), содержащую к вершин и все ребра из А, соединяющие эти вершины.
Покажем, что действуя согласно описанной процедуре, мы построим все множество 71 простых разрезов сеги. Докажем следующее
Утверждение 5. Пусть граф G = {N,A) является связным, не содержит кратных ребер, и в нем для любой пары вершин существует по крайней мере два вершинно непересекающихся пути, их соединяющих Пусть разрез В! является простым и делит граф G на две связные компоненты G и G\G , в которых множества N , N\N содержат 2 т пип — т вершин. Тогда найдутся: I) последовательность простых разрезов R1,..., Rm l, Rl Є А, г = 1, т — 1; II) последовательность вершин v1, ...,vm,vl Є N ,i = l,m; и III) последовательность связных подграфов G1, G2,..., Gm_1, Gm, такие, что каждый из подграфов G1 = v\ GXG1 связен, R1 отделяет G1 от G\Gl, G2, G\G2- связен, G2 = (iV2, Л2), N2 = {v\ v2}, A2 = Rh Rl = {r = (v\ v2)}, R2 отделяет G2 от G\G2,..., G\ G\Gl- связен, Gl = {Nl, A1), Nl = N1 1 [} v\ A1 = Al l (J Rl_h R% отделяет Gl от G\G\..., Gm-\G\Gm-1- связен, Gm l = (Nm-2,Am-2), дгш-2 = Nm-3\Jvm-l Лт-2 = " -2, Rm l отделяет Gm l от G\Gm \ Qm = Qm-\ у Rm_x \Jvm = Q\ G\G - СВЯЗЄН, R! отделяет G от G\G , где Ru і = 1, m — 1,— непустое множество ребер, соединяющих подграф Gl с вершиной vl+\. Кроме того, в любом подграфе G1 найдется вершина v, смежная по крайней мере с одной из верпшн подграфа G\Gl Докажем следующую лемму. Лемма 1. Пусть граф G = (N, А) является связным, не содержит кратных ребер, и в ном для любой пары вершин существует по крайней мере два вершинно непересекающихся пути, их соединяющих. Пусть разрез R является простым и делит граф G на две связные компоненты G и G\G . Тогда разрез В! состоит по крайней мере из двух ребер, таких, что все вершины-концы этих ребер различны.
Доказательство. Согласно условию между любыми двумя вершинами графа G существует не менее двух вершинно-непересекающихся путей. Поэтому для любых vu Vj в том числе и таких, что уг Є N , v3 Є N\N , связанных в G ребром r[ = (vt,Vj), найдется соединяющий их путь s, отличный от г[ (рис 2). Поскольку vt Є N , v3 Є N\N , то на пути s найдется ребро rj, Ф г ь 7 2 = (vp, vq), для которого vp Є N 1 vq Є N\N , рфг,яф J
Простой разрез В! делит G, на две части G ,G\G , и все пути из G в G\G про- G / ходят через R , поэтому ребро г 2 входит в R! Таким образом, разрез R состоит по крайней мере из двух различных ребер 7 1,7 2, таких, что все вершины-концы этих ребер различны. Лемма доказана.
Схема метода ветвей и границ, для задачи анализа уязвимосіи многопродуктовой сеіи
Рассмотрим задачу анализа уязвимости МП-сеги (постановки 1, Ґ), в предположении, что ресурсы нападающего позволяют нанести по физическому графу сети такой удар, который разделит его на три или более часі ей Как и в главе второй, будем считать, что физический и логический графы сети являются разреженными, все требования на поток в неповрежденной сети выполняются, а ресурсы нападающего ограничены величиной, достаточной для разрушения минимального МП-разреза
Решение задачи анализа уязвимости многопродуктовой сети в посіа-новках 1,1 для таких WQ будем искать среди несократимых разрезов сеги, разделяющих ее более, чем на две части. Покажем, что любой несократимый разрез графа G представим в виде объединения простых разрезов этого графа, каждый из которых разделяет непустое множество тяготеющих пар Тогда для решения иосіавленной задачи досіаточно будет построить все возможные комбинации простых разрезов физического графа сеіи и выбрать из них комбинацию простых разрезов - несократимый разрез, удовлетворяющий условиям (3), (5) для задачи А (все несократимые разрезы, удовлетворяющие условиям (3), (5) для задачи В).
Доказанные ниже утверждения 6 и 7 для любого несократимого разреза, делящего физический граф сети более чем на две части, гарантируют существование представления в виде объединения простых разрезов этого графа
Утверждение 6. Пусть разрез R графа G — несократим, делит граф G на п 2 связных компонент, и I(R) ф 0. Тогда существует последовательность вложенных подграфов G,G l,G 2,...,G n_2 и упорядоченный набор попарно непересекающихся множеств Ri,R.2,..-, Rn-i, таких, чю R\ — простой разрез для G, каждое Rt является простым разрезом в соответствующем подграфе G[_l Кроме того, разрез R иредсіавим в виде R = ДіиДгІІ-иДп-і, и I(R) = h(Ri)\Jhm\J...\Jln-i{Rn-i), где h{Ri) ф & множество номеров тяготеющих пар, разделенных в G, It{Rt) ф 0 — множество номеров тяютеющих пар, разделенных в подграфах G[, G 2,..., G n_2. Для доказательства утверждения б нам понадобиться следующая
Лемма 2. Пусть граф G является связным, и разрез R дели г его на п связных компонент G1, 2, ...,Gn. Тогда существует последовательность вложенных подграфов G,Gi,G2,—,G n_2 и упорядоченный набор попарно непересекающихся множеств Ri,R2,...,Rn i, таких, что R\ — простой разрез для G, каждое Rt является разрезом в соответствующем подграфе G\_x. Кроме этого, разрез R представим в виде R = R\ (J R2 \J... (J Rn-i Доказательство Разделение связного графа G на п частей рассмотрим как процесс последовательного отделения компонент от исходного графа G Поскольку разрез R делит G на п часіей G1, G2,..., Gn, то согласно свойству 3 просюго разреза, найдутся по крайней мере два различных простых разреза R С R и R" С R, отделяющих от графа G соответственно порожденные подграфы G \ G 3,G 1 ф G J,Gl С G \G3 С G 3, для некоторых г,; так, что оставшиеся подграфы G\G \ G\G 3 — связны.
Рассмотрим множество R\, образованное следующим образом: пусть в R\ С R входят ребра г = (г/, v") простого разреза R! (согласно свойству 2 простого разреза, либо v Є N\,v" iVi, либо v" Є N\, v N\), и все ребра г Є R, для которых v Є iVi,t " Є Ni Тогда J?i является разрезом и разбивает (7 на две связные компоненты G\, G[ = G\G\ Обозначим R[ = R\R\. В множество R[ входят все ребра г Є R, для которых v Є Nt, v" Є Nu или Ї/ Nt, г " Є Nj,i ф j,i = 2,n,j = 2, n, при этом Яі и Л х не пересекаются. G\ = {N[,A[) - {N\Ni,A\{Ax\}Ri}), те в подграф G\ входят вершины ЛГ2и зи-и пиребраЛ2и-иЛи{Л\Ді}.
Покажем, что разрез ./ разделяет подграф G\ на п — 1 связную компоненту. Для этого допустим, что R[ делит G\ на к п — 1 частей Тогда в подграфе G[\Ri существует ребро г = {v ,v"), г Є R, для которого v Є iVj,?;" Є iVj, г = 2,п, j = 2,п,г ф j, и путь из iV2 в Л , проходящий через это ребро. Не ограничивая общности, будем считать, что г — 2, j = 3
Удалим множество {R\ (J /} из G и рассмотрим подграф С\{Яі (J R[} По предположению в G\i?j найдется путь из N2 в ІУз, проходящий через ребро г Є R, для коюрого v Є N2,v" Є іУз, следовательно, разрез Я : не разделяет связные компоненты G2, з- Так как 2 1,3 ф 1, гю G2,G не разделяет и разрез Яь Это означает, что между G2,Gs в G\{i?ilji 1} сущесівуег путь, их соединяющий, а разрез Яі (J R[ делит граф G на п — 1 часіь. Однако по построению i?i(Ji?i = Я, следовательно, G\R распа-даеіся только на п — 1 связную компоненту, чю противоречит условию утверждения. Таким образом, предположение о том, что разрез R[ делит подграф G[ менее чем на п — 1 часть — неверно.
Рассмотрим связный подграф G[. Разрез R делит его на п — 1 связную компоненту Gl, G2,..., Gl l, Gt+1,..., Gn. Следовательно, для него выполняются все условия свойства 3 простого разреза, и найдутся хотя бы два различных простых разреза R С Я, Rn С Я, отделяющих порожденный подграф G 1 от G\\G 1, и порожденный подграф G s от С ДС? 6, G s ф G 1, так, что G[\G 1, G[\G S — связны. Положим G2 = G 1, R2 = Я;, при этом разрез R2 — простой только для подграфа G[. Пусть множество R2 С R состоит из ребер г = (г/, v") простого разреза Я2 подграфа G[ (согласно свойству 2 простого разреза, либо v Є iV2,u" N2, либо v Є Л , / JV2) и всех ребер г Є R, для которых v Є N2, v" Є iV2, тогда Я2 является разрезом для графа G j и разбивает его на две связные компоненты G 2 = G[\G2 и G2, где G 2 = iv;\ іУ2,лі\{л2ия2}) = (Jv\{MUiv2}, { u U iU }).
Исследование уязвимости моделей со случайными физическими и логическими графами сети
Введем следующие обозначения Т — множество всех непостроенных до конца в данный момент ветвей — комбинаций простых разрезов; S — ущерб, максимальный по всему множеству Т, запоминается как рекорд; S — оценка ущерба, максимальная по всему множеству Т. S — значение ущерба в концевой вершине, максимальное по всем достроенным ветвям дерева перебора, R — множество построенных оптимальных решений.
Замечание. Дерево перебора организовано в соответствии с описанием 2 т.е. выходящие из каждой вершины дуги упорядочены по невозрастанию S(Rt) слева направо.
Алгоритм комбинирования простых разрезов (КПР) использует следующие правила построения дерева перебора.
I Правила ветвления
1) В качестве следующего кандидата на ветвление рассмотрим вершину, отвечающую такому простому разрезу R3 (комбинации простых разрезов R) из Т, для которого оценка ущерба пользователей S(Rj) (S(R)), оказалась максимальной по всему множесіву Т Для простых разрезов оценку ущерба будем считать равной самому ущербу
2). К комбинации разрезов R = Ra[jRb[j[]Ri добавим разрез Rp из R\{Ra,Rb,...,Ri}, с минимальным номером р,р = i + l,v,Rp 0 Q(R), такой, что Rp разделяет хотя бы одну тяготеющую пару, не разделенную разрезами Ra, Rb,..., Rt. Дуга, отвечающая каждому такому Rp, даст ровно одну новую ветвь, исходящую из вершины, соответствующей комбинации разрезов R.
II Правила отсечения
1). Будем отсекать вершину, если сила удара для уничтожения комбинации простых разрезов, отвечающих этой вершине, больше WQ
2). Разветвляя каждую вершину, отвечающую комбинации простых разрезов R, будем отсекать дуги, соответствующие разрезам из множества Q(R) и их комбинациям
Формализуем построение множества Q(R) соответствующим алгоритмом Q . Для этого дополнительно введем следующие обозначения-R — построенное решение, не обязательно оптимальное; R , R — множества разрезов сети; Qi(R),Q2(R) — подмножества Q(R).
Алгоритм Q построения множества Q(R). Вход Пусть R := 0,Qi{R) := 0, W#) := 0, Q{R) = 0,Y := Y(R), S := S(R ),S:= S(R), R! := {Rj\Rj Є R}.
Шаг 1 Поместим в Qi(R) все разрезы Rj Є R, для которых I{R3) С /(і?). Шаг 2 Положим Я := R\Qi(R). 2 1. Если R = 0, перейдем к шагу 3, иначе — к 2.2. 2.2. Найдем в R разрез Rt с максимальным номером і. 2.3. Положим R! := R! \J Ru Y := Y(R ),S := S + S(Rt). 2.4. Если Y Wo, перейдем к 3, иначе — к 2.5. 2 5 Если S S перейдем к 3, иначе — к 2.6. 2 6 Поместим Rt в Q2{R), R% из R удалим.
2 7 Перейдем к 2.1. Шаг 3 Положим Q(R) := Qi(R)\JQ2{R). Выход Замечание. В случае, когда ни одно решение не найдено, при построении множества Q(R) будем полагать S = S(R\) Если неизвестно точное значение 5(Я), то будем считать, что S = S(R). Алгоритм КПР поиска решения задачи анализа уязвимости МП-сети. а) Предварительный этап Шаг 1 С помощью алгоритма АППР для исследуемой сети построим все простые разрезы сети 1Z, выделим из % множество простых разрезов, пропускная способность которых не превосходит WQ. Шаг 2 Для каждого разреза R вычислим S(R). Если для какого-либо разреза S(R) = 0, далее такой разрез не рассматриваем. Разрезы, для которых S(R) 0 упорядочим по невозрастанию S(R) и перенумеруем Ri, R2, ...Rv. Поместим такие разрезы в R.
б). Посіроение решения. Вход Пусть 5 := 0,5 := 0,5 := 0,5(Я,) := 5(Яг), R := ,Т := 0 Шаг 1 Разветвим корневую вершину, одновременно отсекая бесперспективные дуги по правилам II 1),11.2), те. построим все вершины первого яруса — простые разрезы из множества R\Q(0) Поместим все построенные разрезы в множество Т.
Шаг 2 По правилу I 1) из Г выберем кандидата на ветвление, т.е. выберем вершину, отвечающую разрезу R с максимальным значением S(R) по всему множеству Т. Положим 5 := S(R).
Шаг 3 Если максимальная оценка 5 равна сумме требований всех тяготеющих пар, то перейдем к шагу 4, иначе — к 8. Шаг 4 Вычислим точное значение S(R).
Шаг 5 Если точное значение S(R) равно сумме требований всех тяготеющих пар, то перейдем к шагу 6, иначе - к 7. Шаг б Одно оптимальное решение задачи найдено.
Для задачи А в гюсіановке 1 — выход, так как найдена такая комбинация разрезов R, удаление которой из сети делает невозможной передачу всех потоков.
Для задачи В положим 5 := S(R), перейдем к шагу 14. Шаг 7 Положим S(R) := S(R), перейдем к шагу 2
Шаг 8 Проверим, можно ли к комбинации разрезов R с максимальным значением 5 присоединить еще какой-нибудь разрез, не превысив величины WQ ЕСЛИ можно — перейдем к шагу 9, иначе — к 10. Шаг 9 Разветвим вершину R, вычислим величину удара для разрушения каждой новой комбинации разрезов, одновременно отсекая бесперспективные вершины и дуги по правилам II 1) и II 2) Все полученные комбинации простых разрезов добавим в множество Т, a R из Т — удалим.
