Примеры сетевых топологий

Вафельницы опт смотрите на http://www.opt-tut.ru. |

Введение к сложности анализа надежности - часть 3


Коэффициенты матрицы имеют свойство матрицы Вандермонде и, следовательно, является невырожденной, таким образом, можно вычислить значения Fi.

Исследуем более детально вид полинома надежности для функций SCBS. Если задана SCBS, мы определяем значения:

m = число компонентов в системе

с = мощность набора минимального разреза

nc = число наборов разрезов с минимальной мощностью

l = мощность минимального набора путей.

nl = число наборов путей с минимальной мощностью

Заметим сразу, что коэффициенты полинома надежности обладают следующими свойствами:

, для i = 0,1,…,m

, для i< c,

, для i=c,

Fi=nl для i=m-l,

Fi=0 для i>m-l

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

Теорема 2.3. Для любой SCBS, если выполняется одно из следующих пяти условий, то задачи анализа функциональной и рациональной надежности являются NP сложными:

1. Задача распознавания минимального набора путей имеет сложность NP.

2. Задача подсчета минимального набора путей имеет сложность NP

3. Задача распознавания минимального набора разрезов имеет сложность NP

4. Задача подсчета минимального набора разрезов имеет сложность NP

5. Задача нахождения общих коэффициентов в полиноме надежности имеет сложность NP.

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




Начало  Назад  Вперед