Примеры сетевых топологий
Терминала
Задачи распознавания минимального набора путей и разрезов, сопряженные с 2-терминальной мерой, являются проблемами кратчайшего пути и минимального разреза, соответственно. Известны полиномиальные алгоритмы для обеих этих задач. Валиант впервые показал, что задачи анализа надежности в случае 2-терминальной меры имеют сложность NP. Его результаты, которые мы описываем, являются хорошей иллюстрацией методик, используемых в данной области. Доказательство, приведенное ниже, зиждется на сведении проблемы вычисления SN(K) к задаче анализа 2-терминальной рациональной надежности:
Пусть дан граф G = (N,A) с исходным узлом s и набором терминальных вершин K. Построим граф Gґ, добавив к исходному графу узел t и дуги (u,t) для каждого uОK. Присвоим вероятность отказа 1-p всем ребрам (u,t), а всем дугам исходной сети присвоим вероятность отказа 0,5. Заметим, что если все дуги из А имеют одинаковую вероятность отказа, равную 0,5, то все случайные состояния дуг из А, будет иметь вероятность (1/2)|A|. Если через Ai обозначить число субграфов в G, в которых s соединена ровно с i узлами из K, то можно записать Pr[Rel(G`;s,t)]= ?i? SНK,|S|=iPr[существует рабочий путь от s к S, но не работают остальные K-S узлов, а (u,t) работают для всех uОS] = 2-|E|?Ai(1-pi). Сделав оценку такой надежности для |K| различных значений p, мы можем записать систему из |K| уравнений с |K| неизвестными величинами Ai. Отсюда мы можем найти Ai. Сведение завершено, т.к. A|K|=SN(K). Такое сведение показывает, что сложность рациональной задачи соответствует NP. Немногим сложнее доказать, что задача функциональной надежности имеет сложность NP.
