Расчет вероятности связности случайного графа с применением сечений
Автор:Мигов Денис Год: 2011 Издание:LAP Lambert Academic Publishing Страниц: 108 ISBN: 9783845406695 Для сети, элементы которой подвержены случайным отказам, одним из важнейших показателей структурной надежности является вероятность связности заданного подмножества узлов. Сеть с ненадежными элементами обычно моделируется случайным графом, вершины которого соответствуют узлам сети, а ребра - каналам связи. Для каждого элемента графа задана вероятность его присутствия в графе, что соответствует надежности соответствующего элемента сети. В данной работе рассматривается задача точного расчета вероятности связности случайного графа с абсолютно надежными вершинами и ненадежными ребрами. Эта задача является NP-трудной, однако, несмотря на это, современные ЭВМ позволяют за разумное время рассчитывать надежность сетей практически интересной размерности (десятки и сотни узлов). С другой стороны, необходимость проверки приближенных методов на точность их работы также стимулирует дальнейшие исследования точных методов. В настоящей работе предлагаются новые методы понижения размерности...
