Когерентность

Ограничение неизвестного Ni сильно зависит от знания комбинаторной структуры набора работающих субграфов. Большинство проблем надежности, представляющих для нас интерес, имеют свойство когерентности. Имея это в виду, рассмотрим набор D={D1, D2,D3,…,Dr}, в котором каждый Di является набором ребер, для которого E - Di является рабочим. Набор D имеет набор для каждого работающего субграфа, в который входят ребра, не перечисленные в работающем субграфе. Определив так D, мы сформировали наследственное семейство наборов (или комплекс), называемый F-комплексом (то есть, если SОD и S’ НS, тогда S’О D. Тот факт, что сформированное семейство наборов является наследственным, означает, что оно имеет свойство когерентности. Не является совпадением и тот факт, что Fi, определенное ранее, в точности равно числу наборов мощности i в D. Фактически полином надежности для наследственного семейства D полностью определяется его F-вектором (F0,F1,…,Fd), где d=m-1.

Ключом к использованию когерентности при нахождении ограничений является следующее. Рассмотрим все i-наборы в семействе наследования D. Так как семейство является наследственным, в коллекции i-наборов должно быть несколько i-1-наборов; минимальное число таких индуцированных наборов является нижней границей для Fi-1. Минимизация Fi-1 как функции Fi является известной проблемой в теории экстремальных наборов. Здесь имеет место неравенство

Теорема Спернера может использоваться при небольших вычислительных усилиях для улучшения простых ограничений. Мы предполагаем, что доступны l, c, Fm-1 и Fc. Тогда

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

Одним из таких методов является улучшение теоремы Спернера. Теорема Крускала-Катона помещает нижнюю границу

на Fi-1, заданное Fi; соответственно, она помещает верхнюю границу

на Fi, заданное Fi-1. Форма границы здесь имеет малую важность, за исключением того, что xj/i может быть эффективно вычислено, и что всякий раз, когда xіy, xj/i і yj/i.
Напомним, что Fс равно

. Для всетерминальной надежности мы можем вычислить Fс точно; в остальных двух случаях мы не можем надеяться вычислить Fс, но мы можем легко вычислить Fс-1. Предположим, что мы можем вычислить эффективно последовательность коэффициентов F0,F1,…,Fs. Тогда теорема Крускала-Катона дает нам верхнюю границу для Fs+1. Затем, задав значение верхней границы для Fs+1, мы идем тем же путем, чтобы получить верхние ограничения для Fs+2, Fs+3 и так далее.

Нижние границы получаются симметрично. Мы эффективно вычисляем некоторую последовательность коэффициентов Fm-l, Fm-l+1,…,Fm. Для всетерминальной и двухтерминальной надежности Fm-l равно числу деревьев связи и кратчайших путей, соответственно. В k-терминальной проблеме, для того чтобы вычислить эту последовательность, мы можем задать, например, l=k-1. В любом случае пусть d=m-l. При известном Fd, теорема Крускала-Катона выдает нижнюю границу для Fd-1, а именно

.

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