Примеры сетевых топологий
Методы, базирующиеся на состояниях
Когда преобразования, сохраняющие надежность не могут сократить сеть до класса, где существует эффективный точный метод расчета надежности, мы вынуждены обратиться к методам с потенциально экспоненциальными временами расчетов. Первый главный класс таких точных методов расчета рассматривает возможные состояния сети.
Состояние сети G=(V,E) определяется субнабором SНE работоспособных ребер. Концептуально простейшим точным алгоритмом является полный подсчет состояний. Пусть O является набором всех рабочих состояний. Тогда
При генерации всех состояний и определении того, какое является рабочим, надежность вычисляется легко (но неэффективно).
Конечно, можно легко определить работоспособность больших групп состояний, не просматривая их одно за другим. Следовательно, можно сразу достичь улучшения путем генерации состояний более разумным образом. Базовой составляющей при этом является теорема факторизации:
Rel(G)=peRel(GЧe)+(1-pe)Rel(G-e)
для любого ребра е из G. Факторизация продолжается до тех пор, пока не будут подсчитаны все состояния. Однако некоторые простые наблюдения могут дать определенные улучшения. Когда G - е не работает, любая последовательность сокращений и удалений приводит к неработающему состоянию сети, и по этой причине нет нужды факторизовать G - е. Более того, хотя мы можем не иметь возможности упростить G с помощью преобразования, сохраняющего надежность, мы можем упростить GЧe или G - e.
Факторизация с удалением нерелевантных ребер, стягивание необходимых ребер, а также последовательные, параллельные и 2-степенные редуцирования образуют основу многих точных алгоритмов. Для полных графов полный подсчет подразумевает рассмотрение
Ниже мы определяем метод факторизации более явно:
procedure factor (graph G)
используем преобразования, сохраняющие надежность G, следующим образом
удаляем нерелевантные ребра
стягиваем необходимые ребра
используем последовательные редуцирования
используем параллельные редуцирования
используем 2-ступенчатые редуцирования
используем другие редуцирования, такие как многогранник-цепочка, содержащие G, каждое ребро которого имеет вероятность, полученную в результате последовательности редуцирований, а также поддерживаем мультипликативный фактор mult, который получен в результате редуцирований.
если G имеет только один оставшийся терминал, return(mult)
в противном случае
выбираем ребро е из G
return(mult*(factor(G Чe)+factor(G-e)))
end (конец)
Дальнейшие улучшения возможны путем разделения графа на двухсвязные или трехсвязные компоненты на каждом этапе.
