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


Преобразования и сокращения - часть 2


Замена 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-связанные графы.




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