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


Оболочечность - часть 3


Для наших целей важны три вещи. Прежде всего, для k і jі i, x<k/i> = x<j/i><k/j>. Во-вторых, при заданных x, j и i мы можем эффективно вычислить x<j/i>. В-третьих, всякий раз, когда xіy, x<j/i> іy<j/i>.

Теорема Стенли может быть использована для получения эффективно вычисляемых ограничений полинома надежности. Задав префикс (F0,…,Fs) F-вектора, мы можем эффективно вычислить префикс (Н0,…,Нs) Н-вектора.

Зная этот префикс, мы можем получить некоторые простые ограничения; они вообще применимы к оболочечным системам, но мы представляем их здесь для всетерминального случая.

Здесь используется информация о размере набора разрезов минимальной мощности и, где возможно, числа таких разрезов. Эта простая формулировка игнорирует существенную часть информации, число деревьев связи. Это получено с учетом того, что

.

Ставим в соответствие каждому Нi “корзину”. Теперь предположим, что мы имеем Fd “мячей”. Наша задача заключается в том, чтобы поместить все мячи в корзины, так чтобы номера мячей в i-ой корзине, удовлетворяли условию

.

Как следует распределить мячи так, чтобы максимизировать или минимизировать полином надежности? Эти распределения, когда будут найдены, дадут верхнее и нижнее ограничение полинома надежности. Тщательно рассмотрим сумму полиномов надежности:

. Так как 0<р<1, сумма больше, когда коэффициенты нижнего порядка больше. Фактически для двух Н-векторов (Н0,…,Нd) и (J0,…,Jd) всякий раз, когда
для всех i, полином надежности Нi доминирует над полиномом надежности для Ji.

Это последнее простое наблюдение предлагает методику получения ограничений. В практической модели верхняя граница получается путем помещения мячей в самую левую корзину (с корзинами пронумерованными 0,…,d слева направо); аналогично, нижняя граница получается помещением мячей в самую правую корзину. Мы делали это размещение не без ограничений, так как мы заранее знали содержимое корзин 0,…,s.

Теперь мы формируем коэффициенты

для полинома верхней границы и
для полинома нижней границы, используя префикс (Н0,…,Нs) и Fd.


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