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


Когерентность - часть 2


Напомним, что Fс равно
. Для всетерминальной надежности мы можем вычислить Fс точно; в остальных двух случаях мы не можем надеяться вычислить Fс, но мы можем легко вычислить Fс-1. Предположим, что мы можем вычислить эффективно последовательность коэффициентов F0,F1,…,Fs. Тогда теорема Крускала-Катона дает нам верхнюю границу для Fs+1. Затем, задав значение верхней границы для Fs+1, мы идем тем же путем, чтобы получить верхние ограничения для Fs+2, Fs+3 и так далее.

Нижние границы получаются симметрично. Мы эффективно вычисляем некоторую последовательность коэффициентов Fm-l, Fm-l+1,…,Fm. Для всетерминальной и двухтерминальной надежности Fm-l равно числу деревьев связи и кратчайших путей, соответственно. В k-терминальной проблеме, для того чтобы вычислить эту последовательность, мы можем задать, например, l=k-1. В любом случае пусть d=m-l. При известном Fd, теорема Крускала-Катона выдает нижнюю границу для Fd-1, а именно

.




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