Информационная система "Конференции"

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

29-31 октября 2005 года, г. Кемерово, Россия

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

математическое моделирование

Формулы вероятности связности k вершин для графов небольшой размерности

Мигов Д.А.

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

Рассматривается задача точного расчета вероятности связности выделенного множества вершин в случайном графе с абсолютно надежными вершинами и ненадежными ребрами. Из способов решения данной задачи, являющейся NP-трудной, наиболее широко известен метод ветвления (Мура-Шеннона [1]}). Метод заключается в рекурсивном применении формулы полной вероятности при рассмотрении в качестве альтернативных гипотез наличия либо отсутствия очередного разрешающего ребра.

В методе ветвления рекурсии продолжаются до получения или несвязного графа, или до получения графа малой размерности. Для этих графов желательно рассчитывать вероятность связности напрямую, для возможно большей размерности, так как это избавляет от необходимости дальнейшей декомпозиции и, следовательно, уменьшает число рекурсивных вызовов. При этом, в силу многократного выполнения формулы расчета, необходимо построить ее оптимальным образом. В работе [2] приводятся формулы вероятности связности 3-х и 4-х вершинных графов, полученные с помощью ветвления по ребрам.

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

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

Мур Э., Шеннон К. Надежные схемы из ненадежных реле // Кибернетический сб. -- М.: Иностр. лит., 1960. -- Вып.~1. -- C.~109--148.
Родионова О.К. Некоторые методы ускорения расчета надежности информационных сетей // Труды XXX Международной конференции "Информационные технологии в науке, образовании, телекоммуникации и бизнесе, IT+SE'2000", Ялта-Гурзуф, 2003.

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

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

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