Расчет вероятности связности случайного графа с применением сечений

Для сети, элементы которой подвержены случайным отказам, одним из важнейших показателей структурной надежности является вероятность связности заданного подмножества узлов. Сеть с ненадежными элементами обычно моделируется случайным графом, вершины которого соответствуют узлам сети, а ребра - каналам связи. Для каждого элемента графа задана вероятность его присутствия в графе, что соответствует надежности соответствующего элемента сети. В данной работе рассматривается задача точного расчета вероятности связности случайного графа с абсолютно надежными вершинами и ненадежными ребрами. Эта задача является NP-трудной, однако, несмотря на это, современные ЭВМ позволяют за разумное время рассчитывать надежность сетей практически интересной размерности (десятки и сотни узлов). С другой стороны, необходимость проверки приближенных методов на точность их работы также стимулирует дальнейшие исследования точных методов. В настоящей работе предлагаются новые методы понижения размерности поставленной задачи, основанные на использовании сечений (вершинных разрезов). Как показали численные эксперименты, полученные методы значительно ускоряют расчет надежности сетей.