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


Преобразования и аппроксимация графов


Мы имели до сих пор два метода расширения стратегии группирования ребер: группирование не минимальных проходов или разрезов и смягченные требования разделения ребер. В этом подразделе мы рассматриваем третье расширение, которое является, может быть менее прямым, чем предыдущие два.

Мы видели, что преобразования могут быть использованы, чтобы “упростить” сеть и уменьшить время, необходимое для точных алгоритмов. Такие преобразования сохраняют значение меры надежности. Другие преобразования сети могут иметь свойство, гарантирующее, что мера надежности не увеличится. Эти D-преобразования сохраняют нижние границы меры надежности (то есть, вычисление нижней границы после использования такого преобразования выдает то же значение нижней границы надежности, что и до преобразования). Аналогично, I-преобразования гарантируют неуменьшение меры надежности, и, следовательно, сохранение верхней границы.

Тривиальное D-преобразование ликвидирует ребро или дугу сети; оно следует принципам когерентности и статической независимости, так что мера надежности не может увеличиться после такого удаления. Аналогично, операция расщепления узла х на два узла х1 и х2, и замещение каждого ребра {y,x} на {y,x1} или {y,x2} не может увеличить надежность. Эти тривиальные преобразования имеют заметные последствия. Было показано, что нижняя граница при группировании ребер для двухтерминальной надежности может быть получена с помощью использования лишь удаления ребер и расщепления узлов (удалить все ребра, которые не работают для обеспечения проходов в группе и расщепить нетерминальные узлы, соответствующим образом, чтобы было более одного прохода в группе). Результатом этих преобразований является параллельная комбинация s,t-путей - очень простой параллельно-последовательный граф. Верхняя граница при группировании ребер для двухтерминальной надежности аналогична использованию I-преобразования, которое идентифицирует два узла [H.M.F. AboElFotoh and C.J.Colbourn, “Series-parallel bounds for the two-terminal reliability problem”, ORSA J.


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