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


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


Шаги включают в себя:
  1. Для i=0,…,s устанавливаем
    =Нi=
  2. Для i=

В каждом ограничении мы определяем число мячей в каждой корзине от 0 до d по порядку. Как мы заметили, содержимое корзин 0,…,s известно. Для последующих корзин верхняя граница определяется следующим образом. Число мячей, которые могут попасть в текущую корзину, ограничено теоремой Стенли, и лимитируется также тем фактом, что существует фиксированное число мячей, подлежащих распределению. Если осталось больше мячей, чем мы можем поместить в текущую корзину, мы кладем столько, сколько сможем. Если все может быть помещено в текущую корзину, мы делаем это; в этом случае все мячи оказались распределены, а остальные корзины пусты. Нижняя граница определяется путем помещения минимально возможного числа мячей.

Метод приводит к очень мощному набору ограничений, границам Болл-Провена:

В отличие от ограничений Крускала-Катона в случае ограничений Болла-Прована обычно не имеет место неравенство

.




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