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


Методы, базирующиеся на маршрутах и разрезах - часть 3


Однако число нециклических субграфов является экспоненциальной функцией n. Следовательно, несмотря на существенное сокращение вычислительных усилий, объем вычислений остается значительным.

Использование знаковой доминантности в задачах без ориентированности осуществляется совсем другим образом. В задачах без ориентированности циклические релевантные графы имеют ненулевую доминантность. Таким образом, алгоритмы включения-исключения, использующие минимаршруты, требуют алгоритмов вычисления знаковой доминантности. Однако настоящий алгоритм вычисления знаковой доминантности отдельного графа является тем же, что и алгоритм для рекурсивного расчета надежности с привлечением факторизации. Фактически, оптимальные стратегии факторизации, использующие последовательные и параллельные редукции, реализуют столько же шагов факторизации, что и в доминантности.

Предположим, что у нас есть перечень минипроходов P1,…,Ph и пусть Ei является случаем, когда все ребра/дуги минипрохода Pi являются работоспособными. Как было замечено, события {Ei} не являются независимыми. Мы рассматриваем стратегию формирования набора независимых событий. Пусть

обозначает дополнение события Ei. Теперь определим событие D1=E1, и вообще,
. События Di являются независимыми, и, поэтому часто называются событиями “независимого произведения”. Более того, Rel(G)=
. При использовании этого подхода нужно получить формулу для Pr[Di] в терминах состояний ребер/дуг. Каждое событие Ei может быть записано в виде булевого выражения, которое является произведением состояний ребер/дуг минимаршрута Pi. Следовательно, Di может быть также записано в виде булева выражения. По этой причине алгоритмы, которые используют независимые произведения, называются иногда методами “булевой алгебры”.

Существует большое разнообразие методов булевой алгебры. Во-первых, заметим, что выражение для события Di является комплексным булевым выражением, включающим дополнения событий Ei, а не только состояния ребер и дополнения состояний ребер.


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