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


Стандартная форма


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

Мы видели ранее, что один или более полезных точных алгоритмов используют теорию доминирования. Мы вернемся немного к этой теории, чтобы разработать интерпретацию коэффициентов в полиноме надежности. В развитие идеи доминирования следующим образом определена i-четность Pi(G). Пусть все Si являются i-реберными субграфами графа G. Тогда Pi(G)=

. Сатянарайана и Кхалил [A.Satyanarayana and Z.Khalil, “On an invariant of graphs and the reliability polynomial” SIAM J. Alg. Desc. Meth, 7 (1986), 399-403] установили, что Pi(G)=Pi-1(GЧe)+ Pi-1(G-e).

При получении значения надежности через наборы маршрутов каждое образование рассматривается только один раз. Пусть {G1,…,Gt} обозначает все K-субграфы графа G, Relk(G)=

. Следовательно, когда все вероятности для ребер равны, мы получаем другую форму полинома, стандартная форма:

Другими словами, четности являются просто коэффициентами этого полинома надежности (Р-вектор).

Описание Р-векторов, базирующееся на полиномах надежности, широко не изучалось. Р-вектор для полинома всетерминальной надежности удовлетворяет неравенству

для каждого i. О Р-векторе в настоящее время мало что известно. Легко видеть, что Pi =0 для i<n-1 и что Рn-1 равно числу деревьев связи в сети. Однако по существу ничего не известно об остальных коэффициентах в Р-векторе (за исключением, конечно, тех соотношений, которые связаны с эквивалентностью Н- и F-векторов).




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