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


Преобразования и сокращения


Ребро или дуга, которые не входят ни в один из минимальных наборов путей называется нерелевантным: работоспособность таких нерелевантных ребер не влияет на работу или отказ сети. Самым простым способом упрощающего преобразования графа является удаление нерелевантных ребер. По определению, такое преобразование не меняет меру надежности. Чтобы преобразование имело практическое применение для сети, время его эффективной реализации должно быть полиномиальным. Для все-, 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.


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



Книжный магазин