Непересекающиеся разрезы

Использование набора проходов и разрезов с разъединенными ребрами до сих пор мотивировалось первоначально необходимостью вычислить вероятность того, что один набор проходов работает (как в лемме 4.1) или что один набор разрезов приводит к отказу (как в лемме 4.2). Разработан метод, который позволяет наборам разрезов иметь общие ребра, сохраняя эффективность вычисления вероятности того, что один из наборов разрезов приводит к отказу. Для графа G=(V,E) секция (А,В) из V образует набор разрезов, содержащий все ребра, имеющие один конец в А, а другой в В. Два таких набора разрезов (А,В) и (

) являются непересекающимися, если, по крайней мере, один из АЗВ, АЗ

ЗВ и

является пустым. Коллекция разрезов является непересекающейся или ламинарной, если каждый из двух наборов в коллекции являются непересекающимися. В n-узловом графе с k терминалами набор непересекающихся разрезов содержит по большей части n-1+k-2 Ј 2n-3 непересекающихся разрезов. Базис разрезов n-вершинного графа является набором из n-1 разреза С1,…,Сn-1, для которых каждый разрез может быть записан как сумма по модулю 2 этих n-1 разрезов. Ломоносов и Полесски показали, что для любого базиса разрезов С1,…,Сn-1 всетеринальное значение надежности удовлетворяет равенству

Ограничение на базис, ограничивает число разрезов, которые могут быть использованы до уровня меньше, чем число терминалов. Более общее расширение получается при допущении использования наборов непересекающихся разрезов. Ограничение получено путем установления вероятности того, что ни один из непересекающихся разрезов не приводит к отказу. Это согласуется с k-терминальной узловой надежностью графа специального типа - ориентированного графа проходов. Тогда простая динамичная стратегия программирования обеспечит получение значений границ за полиномиальное время.

Ограничения, использующие непересекающиеся разрезы, существенно расширяют возможности стратегий группирования ребер при рассмотрении больших наборов разрезов, но при полиномиальном их числе.

Содержание раздела