Примеры сетевых топологий
Преобразования и аппроксимация графов
Мы имели до сих пор два метода расширения стратегии группирования ребер: группирование не минимальных проходов или разрезов и смягченные требования разделения ребер. В этом подразделе мы рассматриваем третье расширение, которое является, может быть менее прямым, чем предыдущие два.
Мы видели, что преобразования могут быть использованы, чтобы “упростить” сеть и уменьшить время, необходимое для точных алгоритмов. Такие преобразования сохраняют значение меры надежности. Другие преобразования сети могут иметь свойство, гарантирующее, что мера надежности не увеличится. Эти 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.
Computing 1 (1989), 205-222]. Использование преобразований для получения двухтерминальных границ при группировании ребер позволяет “рано” остановить процесс преобразования. Раз сеть преобразована в последовательно-параллельную сеть, надежность может быть вычислена точно за полиномиальное время и в дальнейших преобразованиях нет необходимости.
Одним частным приложением преобразований является анализ блокирующих свойств “канальных графов”. Преобразования для канальных графов используются и в отношении s,t-связности.
Два преобразования, треугольник-звезда (delta-wye) и звезда-треугольник достойны отдельного упоминания. Дельта (или D) в сетях является набором из трех ребер {{x,y},{x,z},{y,z}}, образующих треугольник, а wye (или у) является набором из трех ребер {{x,w},{y,w},{z,w}}, для которого вершина w является входящей для перечисленных выше вершин. Преобразования треугольник-звезда и звезда-треугольник являются лишь заменой одной конфигурации на другую. В 1962 году Леманом были предложены два метода определения вероятностей для ребер звезды (треугольника) при заданных вероятностях ребер треугольника (звезды, соответственно). Его два метода не являются, вообще говоря, точными, он скорее показал, что одно из преобразований является I-преобразованием, а другое D-преобразованием в предположении, что центральный узел не является терминальным. Удивительно, но то, какое из этих преобразований является I-преобразованием, зависит от численного значения вероятностей. Таким образом, преобразования треугольник-звезда и звезда-треугольник представляются отличными от ранее упомянутых преобразований, так как здесь нет простой комбинаторной настройки преобразования.
Возможно, большинство существенных аспектов разработки ограничений путем комбинирования простых преобразований являются потенциалом для разработки более сложных мер надежности. Например, всякий раз, когда удаление ребра и расщепление вершины являются I-преобразованиями для специфицированной надежности или меры работоспособности, мы имеем эффективно вычисляемые границы для алгоритма группирования ребер.Если, кроме того, мера может быть вычислена точно для последовательно-параллельной сети за полиномиальное время, мы имеем эффективные последовательно-параллельные аппроксимации. Используя объединение Ломоносова, ограничения для статических мер надежности, обсуждаемые здесь, могут быть применены для времязависимых мер надежности.
