Примеры сетевых топологий
Точное вычисление надежности
В этом разделе мы изучим алгоритмы точного вычисления мер надежности. Выше было показано, что для сетей в целом все меры надежности, представляющие интерес, являются #P-полными. Поэтому мы исследуем два основных направления: точные алгоритмы с экспоненциальным временем для общих сетей, и точные алгоритмы с полиномиальным временем для ограниченного класса сетей.
Оба этих направления опираются на простое, но важное соображение: существует такое преобразование графа, которое не меняет значений различных мер надежности, и это преобразование может быть использовано для упрощения топологии сети, для которой нужно вычислить точное значение надежности. Наша первая тема - такие преобразования графов с целью их упрощения.
