Простые ограничения

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

RelA(p)»Nn-1pn-1(1-p)m-n+1

а когда р близко к 1,

RelA(p) »1-Ссpm-c(1-p)c

В заданном определении полинома надежности точная формулировка аппроксимации Кельмана верна для всех значений р:

Nn-1pn-1(1-p)m-n+1ЈRelA(p) Ј1 - Ccpm-c(1-p)c

Таким образом, аппроксимации Кельмана могут рассматриваться как абсолютные ограничения на полином надежности. Существенным наблюдением здесь является то, что для крайних значений р любой член, содержащий Nn-1 или член, включающий Cc, доминирует над остальными членами. Мы знаем, что Ni+Cm-I=

и, следовательно, мы имеем

Это наблюдение подводит нас к простому набору ограничений:

В нижней границе каждый “неизвестный” Ni аппроксимируется нулем; известные коэффициенты равны для i < n-1 (нуль) i=n-1 (число деревьев связи), i=m-c (m-c-реберный субграф, чьи компоненты не равны минимальной мощности набора разрезов), и i > m-c (все возможные i-ребра субграфов). В верхней границе “неизвестный” Ni аппроксимируется

. Расширение для k-терминальной надежности достаточно прямолинейно: просто всюду подставляем l вместо n-1. Нижняя граница, несмотря на это, оказывается недооценивающей Nl как 0; верхняя граница получается просто путем использования недооценки для самого l.

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

Содержание раздела