Примеры сетевых топологий
Преобразования и сокращения
Ребро или дуга, которые не входят ни в один из минимальных наборов путей называется нерелевантным: работоспособность таких нерелевантных ребер не влияет на работу или отказ сети. Самым простым способом упрощающего преобразования графа является удаление нерелевантных ребер. По определению, такое преобразование не меняет меру надежности. Чтобы преобразование имело практическое применение для сети, время его эффективной реализации должно быть полиномиальным. Для все-, k- и 2-терминальных мер надежности петли всегда являются нерелевантными. А для k- и 2- терминальных мер надежности, нерелевантными являются также все ребра, не имеющие терминального окончания. Такие ребра легко находить и удалять. В случае ориентированных задач надежности поиск нерелевантных дуг отнюдь не простая задача. Было показано, что задача нахождения нерелевантных дуг в случае (s,t)-связанности имеет сложность NP, в то время как общая неориентированная задача допускает эффективное решение.
Сосредоточимся сначала на неориентированных задачах. Ребро или дуга, входящие во все минипути, является обязательным. После удаления всех нерелевантных ребер, каждое оставшееся соединение (набор разрезов ребер с мощностью 1) является обязательным. Пусть G=(V,E) с набором терминалов KНV, и ребро eОE имеет вероятность функционирования pe. Стягивание G?e , ребра e={x,y} из G получается путем удаления e, которое определяет x и y, и превращая результирующий узел в терминал всякий раз, когда K1{x,y}?0. Надежность Rel(G) графа G удовлетворяет соотношению Rel(G)=peRel(G?e), когда eявляется обязательным ребром. Таким образом, отображение G в G?e является преобразованием, сохраняющим меру надежности, с мультипликативным коэффициентом pe.
Два ребра e и f, имеющие одни и те же концы, являются параллельными. Так как любой минимальный путь содержит, по крайне мере, одно из двух таких ребер, а замена e на f будет естественным взаимно однозначным соответствием между минимальными наборами проходов, содержащих е, и минимальных путей с ребром f.
Замена e и f на одно ребро g с коэффициентом p=1-(1-pe)(1-pj) не изменит общую меру надежности. Это называется параллельным сокращением графа. Понятие параллельного сокращения можно обобщить на случай, когда e и f сами являются заменителями ребер.
Два ребра e={x,y} и f={y,z} называются последовательными, когда y является узлом степени 2. В этом случае любой миниразрез содержит либо ребро е, либо f. Замена e на f является естественной для миниразрезов, содержащих e и f, соответственно. Таким образом, преобразование, сохраняющее меру надежности, получается путем удаления узла y и ребер e, f и добавления ребра g = {x,z} с надежностью pg=pepf при условии, что y не является терминальной вершиной. Это называется последовательной редукцией. В более общем случае, когда два ребра являются дополнениями, могут быть использованы аналогичные преобразования.
Последовательную редукцию нельзя применять к терминальным узлам графа со степенью 2. Однако, в случае, когда x, y, z являются терминалами, некоторое структурное замещение с сохранением меры надежности возможно. Коэффициент такого преобразования будет равен 1-(1-pe)(1-pf), если надежность нового ребра g определяется вероятностью pg=pepf/(1-(1-pe)(1-pf)). Это называется редукцией второй степени. Остается рассмотреть случаи, когда y является терминалом, а x или z - нет.
В сущности, каждое упрощение может рассматриваться, как замещение некоторой субсети субсетью, которая имеет эквивалентные характеристики надежности, или характеристики, которые масштабируют исходную меру надежности определенным образом. Принимая это во внимание, рассмотрим сеть G=(V,E) с набором терминальных узлов KНV. Полученная из G подсеть H=(W,F) является s-связанной, если существует такой набор АНW, с |A|Јs, для которого каждое ребро графа G с одним концом в точке V\W и другим концом в W, имеет оконечную точка в А. Другими словами только узлы из А связывают подсеть с оставшейся сетью. Общий класс упрощений возникает из изучения s-связанных субграфов для малых s, и замещения каждого из них на более простые s-связанные графы.
1-связные субсети соединены с остальной сетью через один узел разреза. Если 1-связная субсеть не содержит терминалов, все ее ребра являются нерелевантными. С другой стороны, если субсеть, и остальная сеть содержат терминалы, сам узел разреза может рассматриваться как терминал, так как он связан с терминалами в любом минипути. Таким образом, добавляем узел разреза в качестве терминала. Затем сеть может быть разделена на две субсети H и G\(W-A), а мера надежности равна произведению мер этих двух объектов. Это обобщает понятие преобразования на процедуры, которые разделяет сеть на две или более субсети.
Для субсетей, объединенных в двух точках, мы рассматриваем замещение субсети как определение эквивалентного ребра. Если Н является субсетью, соединенной через {x,y}, и Н не содержит терминалов, то мы можем определить 2-терминальную надежность Н от х до у и заместить Н ребром {x,y}, чья вероятность работоспособности равна найденной 2-терминальной надежности. Когда Н содержит терминалы, ситуация более сложна, так как недостаточно знать, что х достижимо со стороны у, нужно также знать, могут ли все внутренние терминалы связаться с х или у или с обоими из них. Несмотря на это, разработаны преобразования, при которых ребрам присваивается несколько значений вероятности, а не только вероятность работоспособности. Число величин, которые нужно поддерживать, не зависит от размера сети, но растет экспоненциально с увеличением числа подсоединенных узлов.
