Примеры сетевых топологий
Постоптимизация ограничений
До сих пор мы обсуждали базовые стратегии получения ограничений. Даже конспективное описание каждого показывает, что существует огромное разнообразие доступных методов получения ограничений. Естественно попытаться объединить их для уточнения границ или получения более общих ограничений. Предпочтительным путем является нахождение общей теории, в которой число границ унифицировано. Потерпев неудачу в этом, можно пожелать получить какую-либо информацию о надежности, и это возможно с помощью разных рассмотренных методов. Например, если известна вероятность достижения u из s, и независимо известна также вероятность достижения t из u, что можно сказать о вероятности достижения t из s? Используя известную теорему Алсведе и Дайкина, Брехт и Кольбурн разработали методы для улучшения нижних границ. Они заметили, что если сеть G соединена с терминальным набором К1, с вероятностью р1, соединена с терминальным набором К2 и с вероятностью р2 и К1ЗК2№0, то G соединена с терминальным набором К1cК2 с вероятностью, по крайней мере, р1р2. Это дает мультипликативный треугольник неравенств для границ двухтерминальной надежности, который Брехт и Кольбурн нашли эффективным для улучшения границ двухтерминальной надежности, которые были вычислены другими методами (в частности методом группирования ребер). Ключом здесь является постоптимизация, методика улучшения ограничений для произвольных границ.
В чем-то похожий метод для верхних границ, называемый ренормализацией, был изучен недавно. Для двухтерминальной надежности вероятность хе того, что один терминал s не может связаться с другим терминалом t через специфицированное ребро е, ограничена сверху вероятностью того, что само ребро е не обеспечивает связь плюс вероятность того, что е работает с вероятностью, кратной вероятности хf для каждого ребра f, соединенного с е. Двухтерминальные верхние границы могут быть использованы для определения исходных оценок вероятности хе для каждого ребра е. Тогда каждое неравенство может привести к некоторому сокращению значения хе.
Ренормализация дает верхнюю границу при недооценке влияния пересечения s,t-маршрутов и при рассмотрении s,t-маршрутов, а не только s,t-проходов. Для s,t-связности ориентированных графов без циклов отсутствие ориентированных циклов гарантирует, что все s,t-маршруты являются s,t-проходами; в этом случае ренормализация является методом с полиномиальным временем, который гарантирует улучшение для верхнего ограничения. Ренормализация является существенно постоптимизационной стратегией, но может использоваться сама по себе, начиная с начальной переоценки вероятности отказа хе для ребра е.
Одна стратегия окончательной постоптимизации была сформирована для применения, когда вероятности работоспособности всех ребер равны между собой. Кольбурн и Хармс заметили, что если произвести оценку полинома
