Рассматривается задача точного вычисления вероятности связности сети с абсолютно надежными узлами и ненадежными каналами связи. В терминах теории графах эта задача формулируется как задача точного вычисления вероятности связности соответствующего случайного графа.
В докладе представлена формула для вероятности связности графа с вершинным разрезом, содержащим произвольное количество элементов. Эта формула выражает вероятность связности графа через вероятности связности подграфов, на которые граф разделяется разрезом, стянутых по разрезающим вершинам. Предложен метод вычисления вероятностей связности данных подграфов.
Как показали численные эксперименты, использование полученных формул позволяет дополнительно сократить время расчета.
Примечание. Тезисы докладов публикуются в авторской редакции
Ваши комментарии Обратная связь |
[Головная страница] [Конференции] |
© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск