Материал: Теория сетевых войн. Живучесть атакуемых сетей. учеб. пособие. Остапенко А.Г., Калашников А.О

4.4.4.1. Вычисление минимальных путей

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

Рис. 4.9. Условныеобозначения при анализе надежности методом узлов

Граф в общем случае может состоять из n ветвей и k узлов, которые можно пронумеровать в любой последовательности. Ради удобства будем обозначать всегда начальный узел как (k-1)-й, а конечный – как k-й. Между начальным и конечным узлами структурной схемы расчета надежности вводится фиктивная, нулевая ветвь (Рис.4.9). Топологию структурной схемы расчета надежности отражает матрица инцидентности узлов и ветвей А, элементы которой

Определим также квадратную матрицу узловых соединений К порядка k. Элемент этой матрицы kxx=(K)xx’(x,x’=1,2,…,k) представляет собой функцию работоспособности прямого соединения между x и x’узлами. Поэтому диагональные элементы матрицы kxx=1 (x=1,2,…,k), в то время как недиагональные элементы kxx’ (x≠x’=1,2,…,k)

86

определяются булевой суммой функций работоспособности всех ветвей, непосредственно связывающих x и x’ узлы.

В диагональную матрицу Х порядка n мы объединим функции работоспособности отдельных ветвей X=<x1,x2,…,xn>.

Дальнейшего рассмотрения оказывается целесообразным также распространить булевы сложение и умножение на булевы матрицы. Будем называть матрицу булевой, если ее

элементы являются булевыми переменными или константами из области задания значений булевых переменных.

Пусть mλx – элементы булевой матрицы М, а nλx – элементы булевой матрицы N. Булеву матрицу S с элементами sλx= mλx ˅ nλx будем называть суммой булевых матриц М и N и обозначать S= М ˅ N.

Матрицу P с элементами pλλ’ mλ ˄nλ’ = будем

т

называть произведением булевых матриц М и N и обозначать

P = М ˄ Nт.

Квадратную булеву матрицу Q можно возвести в степень, при этом операция возведения в степень определяется по

правилу

Q(i+1)= Q(i) ˄ Q, i=0,1,2,…,

где Q(0)=I – единичная булева матрица, совпадающая с обычной арифметической единичной матрицей, если булевы переменные принимают значения 0 и 1 [52].

С помощью операций над булевыми матрицами можно сформулировать следующую связь между введенными ниже матрицами А, К, Х:

Действительно, в соответствии с выражением (4.46) для элементов главной диагонали матрицы К имеем вид

kxx=1 ˅(А˄ХАТ)xx=1

и для (x≠x’)остальных элементов

Выражение ( ˅ ′ ) становится равным точно единице тогда, когда одновременно =1 и ′ =1, то есть если v-я ветвь непосредственно связывает x-й и x’-й узлы. Этим самым формула (4.46) полностью доказана.

Элементы степенной булевой матрицы К можно также интерпретировать геометрически.

Теорема 1. Элемент (K(i))xx’(x,x’=1,2,…,k) i-й степени булевой матрицы узловых соединений является функцией работоспособности всех путей соединения между узлами x и x’, проходящих через любые другие промежуточные узлы, число которых равно 0,1,2,…, i-1.

Доказательство. Выше сформулированное предложение докажем методом полной индукции. Для i=1 справедливость теоремы следует из определения матрицы К. Если утверждение теоремы доказано для любого натурального i, то оно в этом

В каждом члене первый множитель в соответствии с предположением индукции представляет собой функцию работоспособности всех путей, связывающих x и λ узлы через промежуточные узлы, число которых не более i-1. Второй

множитель является функцией работоспособности прямого соединения узла λ с узлом x’. Следовательно, элемент (K(i+1))xx’

является функцией работоспособности всех соединительных путей между узлами x и x’ при максимальном числе промежуточных узлов, равном I [52].

Из теоремы 1 непосредственно следует важная.

Теорема 2. Элемент матрицы (K(k-1))k-1, k представляет собой функцию работоспособности системы с рассматриваемой структурной схемой надежности. Если при выполнении умножения булевых матриц последовательно опускать булевы выражения, соответствующие путям, которые многократно проходят через хотя бы один узел, то получим функцию работоспособности системы. Эту систему можно

88

истолковывать как параллельное соединение эквивалентных схем всех минимальных путей между (k-1)-м и k-м узлами.

Следствие. По найденным минимальным путям можно вычислить функцию отказа системы [52].

В качестве примера рассмотрим структурную схему надежности, изображенную на рисунке 4.10, с обозначенными узлами и ветвями.

Из матрицы функций работоспособности ветвей Х=<x1,x2, x3,x4, x5,x6, x7,x8> и матрицы инцидентности

=

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

Рис. 4.10. Эквивалентная схема по работоспособности с обозначенными ветвями и узлами

89

Матрицу К можно также записать, исходя непосредственно из структурной схемы надежности. Вычисляя элемент (К)45(4) по теореме 1, получим все минимальные пути. Для булевых произведений выбирается сокращенная форма записи, например, вместо x1˄x2˄x3 записывается только 1 2 3. Тогда для четвертой и пятой строк К(2) получаем вектор-строки в виде

(К(2))4=(1˅23, 14˅15˅26, 2˅13, 1, 27), (К(2))5=(37˅48˅58, 8˅67,7˅86, 27, 1),

откуда

(К(4))45=(27˅137˅268˅1368˅148˅158˅1467˅1567˅2348˅23

58).

Элемент (К(4))45 дает функцию работоспособности системы [52].

4.4.4.2. Расчет минимальных сечений

Прежде всего, предполагается, что граф, соответствующий структурной схеме надежности, является плоским. Пусть в расширенном нулевой ветвью графе имеется всего m замкнутых контуров. Связная часть графа называется замкнутым контуром, если каждый узел этой части связывается друг с другом 2 ветвями, Если представить себе плоский граф без пересечений плоскости, то для каждой точки поверхности, которая не лежит прямо на ветви или узле графа, можно указать такой контур, внутри которого лежит рассматриваемая точка. Ограничивающие контур ветви образуют так называемое окно замкнутого контура. В этом разделе под контуром будем понимать замкнутый контур. Очевидно, не нарушая общности, можно считать, что (m-1)-й и m-й контуры выбраны так, как показано на рисунке 4.11.

90