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


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


Пусть {[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, он отвечает за наборы

. Отсюда мы нашли, что
. Приравнивание форм F-вектора и Н-вектора полинома надежности дает выражение для Hi в терминах F-вектора, а именно

Это выражение позволяет нам эффективно вычислить Н0,…,Нs. Другой очевидный, но полезный факт заключается в том, что

.

Стенли получил нижнюю границу

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


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



Книжный магазин