Примеры сетевых топологий
Оболочечность
У нас нет надежды без дополнительной информации улучшить ограничения Крускал-Катона. Такая дополнительная информация может быть получена разными путями. Одним из таких путей мог бы быть эффективный алгоритм вычисления (или установления более жестких границ) одного или более неизвестных Fi. Другим - может быть выявление того, что конкретное наследственное семейство, имеет некоторую специальную комбинаторную структуру. Этот последний подход является многообещающим, так как, несмотря на то, что компоненты наборов маршрутов в когерентных системах образуют наследственные семейства, не все наследственные семейства образуются таким путем.
Фактически, F-комплекс в проблеме всетерминальной надежности является матроидом, кографическим матроидом графа. В описании F-векторов кографических матроидов отсутствует прогресс, и можно задать вопрос, чем может быть F-вектор матроида вообще. Даже для этой проблемы прямого прогресса не достигнуто. Однако мы можем идентифицировать класс наследственных систем, который является промежуточным между матроидами и наследственными системами вообще, результаты представлены ниже.
Прован и Биллера доказали важный результат, связанный со структурой матроидов, который (вместе с другими результатами) накладывает ограничения на их F-векторы. Они показали, что матроиды являются “оболочечными” комплексами. Важность результата Прован-Биллера в исследованиях надежности заключается в том, что они предлагают возможность использования оболочечности для улучшения ограничений Крускал-Катона. Конечно, это требует введения структурной теоремы для оболочечных систем. Интервал [L,U] является семейством субнаборов {S:LНSНU}. Часть интервала комплекса является набором разъединенных интервалов, для которых каждый набор в комплексе принадлежит строго одному интервалу. Комплекс разделим, если он имеет секции интервалов [Li,Ui], 1 Јi Ј J с Ui в качестве базы для всех i. Оболочечные комплексы всегда являются разделимыми.
Рассмотрим оболочечный комплекс с b базами.
Пусть {[Li,Ui]|1 Јi Ј b} является секцией интервала для этого комплекса. [Li,Ui] является компактной записью для всех наборов в интервале. Вероятность того, что какой-то из этих наборов реализуется, равна тогда pm-|Ui|(1-p)|Li|. Другими словами, ребра |Li| должны отказать, а ребра m-Ui должны работать. Состояние остальных ребер не играет никакой роли. Каждый Ui является базой в комплексе; следовательно, мощности всех Ui равны (ранг d базы). Однако ранги Li не являются идентичными; мы, следовательно, определяем Hi=|{Lj:1Јj Ј b,|Lj|=i}|. Это дает увеличение Н-вектора (Н0,…,Нd). Коэффициенты Hi определяют интервалы в секции, чей младший набор имеет ранг i.
Это предлагает еще одну форму полинома надежности:
Здесь l - мощность набора маршрутов с минимальной мощностью (дерево связей), а d=m-l является рангом базы. Более конкретно, в графе с n-вершинами и m-ребрами i=n-1, а d=m-n+1.
Естественно, любая информация о Н-векторе также предоставляет данные о полиноме надежности. Однако чтобы поместить Н-вектор в соответствующий контекст, важно рассмотреть отношения между Н-вектором и F-вектором для оболочечного комплекса. Н-вектор для любого комплекса может быть определен непосредственно в терминах F-вектора. В секционном случае, однако, соответствие может быть легко установлено комбинаторно.
Рассмотрим наборы ранга k в комплексе. Они подсчитываются с помощью Fk. Теперь любой интервал [Li,Ui] отвечает за определенные наборы. Пусть r является рангом Li. Если r > k, интервал отвечает за 0 наборов в Fk; однако, если rЈ k, он отвечает за наборы
Это выражение позволяет нам эффективно вычислить Н0,…,Нs. Другой очевидный, но полезный факт заключается в том, что
Стенли получил нижнюю границу
Для наших целей важны три вещи. Прежде всего, для 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,…,d слева направо); аналогично, нижняя граница получается помещением мячей в самую правую корзину. Мы делали это размещение не без ограничений, так как мы заранее знали содержимое корзин 0,…,s.
Теперь мы формируем коэффициенты
Шаги включают в себя:
- Для i=0,…,s устанавливаем =Нi=
- Для i=
В каждом ограничении мы определяем число мячей в каждой корзине от 0 до d по порядку. Как мы заметили, содержимое корзин 0,…,s известно. Для последующих корзин верхняя граница определяется следующим образом. Число мячей, которые могут попасть в текущую корзину, ограничено теоремой Стенли, и лимитируется также тем фактом, что существует фиксированное число мячей, подлежащих распределению. Если осталось больше мячей, чем мы можем поместить в текущую корзину, мы кладем столько, сколько сможем. Если все может быть помещено в текущую корзину, мы делаем это; в этом случае все мячи оказались распределены, а остальные корзины пусты. Нижняя граница определяется путем помещения минимально возможного числа мячей.
Метод приводит к очень мощному набору ограничений, границам Болл-Провена:
В отличие от ограничений Крускала-Катона в случае ограничений Болла-Прована обычно не имеет место неравенство
