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


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


Ограничение неизвестного 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.


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