Конференции ИВТ СО РАН

V Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям с участием иностранных ученых

1-3 ноября, г. Новосибирск, Россия

Тезисы докладов

Вычислительная математика и математическое моделирование

Расчет вероятности связности сети с применением вершинных разрезов специального вида

Мигов Д.А.

Институт Вычислительной математики и математической геофизики СО РАН (Новосибирск)

Рассматривается задача расчета вероятности связности сети с абсолютно надежными узлами и ненадежными каналами связи. В терминах теории графах эта задача формулируется как задача точного вычисления вероятности связности соответствующего случайного графа.

Для пояснения сути настоящей работы будем использовать следующие определения.

Циклический граф получается из произвольного цикла заменой ребер на двусвязные графы. Этот цикл - образующий цикл для данного циклического графа. Отметим, что граф может иметь сколько угодно много образующих циклов.

Циклический разрез в циклическом графе - множество вершин какого либо образующего цикла.

В работе [1] была представлена формула, позволяющая использовать двухвершинные разрезы двусвязного графа для вычисления вероятности его связности. Более конкретно, эта формула связывает вероятность связности двусвязного графа с вероятностями связности его подграфов, на которые граф разделяется произвольным разрезом из двух вершин, и вероятностями связности этих подграфов со склеенными вершинами этого разреза.

В настоящей работе получено два обобщения этой формулы.

1. Обобщение на произвольное количество подграфов, на которые распадается граф при удалении двухвершинного разреза.

2. Обобщение на произвольные циклические разрезы.

Таким образом, появилась возможность учитывать сразу группу двухвершинных разрезов с учетом их кратности, что позволяет избежать неоднократного пересчитывания вероятностей связности определенных подграфов. Как показали численные эксперименты, проведенные на графах, близких по структуре к реальным сетям связи, использование полученных формул позволяет дополнительно сократить время расчета.

[1] Мигов Д.А. Использование разрезов случайного графа для вычисления вероятности его связности // Тр. конф. молодых ученых ИВМиМГ СО РАН. - Новосибирск,2004. С.118-126.

Дополнительные материалы: Полный текст доклада
Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]