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


Преобразования и аппроксимация графов - часть 2


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-преобразованиями для специфицированной надежности или меры работоспособности, мы имеем эффективно вычисляемые границы для алгоритма группирования ребер.Если, кроме того, мера может быть вычислена точно для последовательно-параллельной сети за полиномиальное время, мы имеем эффективные последовательно-параллельные аппроксимации. Используя объединение Ломоносова, ограничения для статических мер надежности, обсуждаемые здесь, могут быть применены для времязависимых мер надежности.




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



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