Примеры сетевых топологий
Всетерминальная мера
Для ориентированной всетерминальной меры проблемы с наборами путей и разрезов с минимальной мощностью, являются задачами поиска минимального покрывающего дерева и минимального s-ориентированного разреза, соответственно.
Обе эти задачи решаются за полиномиальное время. Задача подсчета минимального s-ориентированных разрезов имеет сложность NP. А это, в свою очередь означает, что связанная с этим задача надежности имеет сложность NP. Для случая неориентированной меры задачи по распознаванию и подсчету минимального набора путей и разрезов имеют полиномиальную сложность. Однако задача вычисления общего члена в полиноме надежности имеет сложность NP потому, что задачи анализа надежности для неориентированного случая имеют сложность NP.
В свете этих негативных результатов, большинство исследований имело целью анализ структурированных сети. Самый широкий класс сетей, для которых можно выполнить вычисления за полиномиальное время, базируется на последовательно-параллельных графах и определенных обобщениях. Последние исследования посвящены сложности анализа надежности структурированных сетей, в частности это касается ориентированных ациклических и планарных сетей. Прован (J.S.Provan, “The complexity of reliability computations in planar and acyclic graphs”, SIAM, J. Computings 8 (1986), 694-702 ) показал, что неориентированная 2-терминальная проблема надежности имеет сложность NP в планарных нециклических сетях, имеющих степени узлов не выше трех.
Результаты данного раздела указывают на то, что полиномиальные алгоритмы для сетевой надежности существуют только для маленького класса сетей. Благодаря этому факту большое число исследований было посвящено изучению ограничений сетевой надежности, и подходов основанных на методе Монте-Карло.
