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


Методы, базирующиеся на маршрутах и разрезах - часть 2


Структура является нечетной, когда i нечетно, и четным, когда i четно. Граф, имеющий структуру, является К-субграфом. Каждая нечетная структура субграфа вносит положительный вклад в надежность, а каждая четная структура дает негативный вклад. Знаковая доминантность G с терминальным набором вершин К, sdom(G,K), равна числу нечетных структур G минус число четных структур G. Доминантность dom(G,K) равна абсолютному значению знаковой доминантности. Мы обычно пишем sdom(G), а подразумеваем dom(G) с терминальным набором К. С учетом этих определений Сатианарайана и Прабхокар существенно упростили выражение для надежности:

,

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

Первой целью является определение того, какие состояния имеют знаковую доминантность равную нулю, и могут, следовательно, игнорироваться в выражении для надежности. Учитывая это, состояние (субграф) является релевантным, если он не содержит нерелевантных дуг. Субграф, содержащий нерелевантные дуги, не имеет каких-либо структур и, следовательно, имеет нулевую знаковую доминантность. Таким образом, мы ограничиваем наше рассмотрение только релевантными субграфами. Среди релевантных субграфов многие имеют нулевую знаковую доминантность: точнее циклические субграфы (субграфы с ориентированными циклами). Более того, нециклические релевантные диграфы с m дугами и n узлами имеют знаковую доминантность sdom(G)=(-1)m-n+1.

Изучение доминантности в отношении проблем надежности является разумным приложением комбинаторных аргументов. Метод, который в простейшем случае требует двойного экспоненциального времени, сводится к требованию формирования нециклических релевантных графов и тривиальным расчетам для каждого из них. На практике это позволяет существенно улучшить полный подсчет состояний.


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