Asymptotics of connectivity probabilities for pairs of graph nodes.pdf Для случайных графов с низконадёжными рёбрами построен удобный в реализации алгоритм вычисления вероятности связности любой пары его вершин на основе доказанного асимптотического соотношения. Для параметров полученного соотношения (характеристик кратчайших путей) разработаны модификации классических алгоритмов. Особенностью предлагаемых алгоритмов является тот факт, что в них не требуется перечислять кратчайшие пути между узлами, нужно лишь определить их количество. Ещё одним существенным фактором упрощения вычислений является рассмотрение графов с ограниченным диаметром, которые в последние годы вызывают большой теоретический и практический интерес. Проведенный вычислительный эксперимент подтвердил быстродействие построенной процедуры определения вероятности связности по сравнению с методом Монте-Карло. Рассмотрим неориентированный связный простой граф G с множеством узлов U и множеством рёбер V. Предположим, что каждое ребро v графа G с вероятностью p(v) работоспособно, причём все рёбра функционируют независимо. Обозначим D(i, j) минимальное число ребер в путях, соединяющих узлы i, j графа G, C(i, j) —число путей с D(i, j) рёбрами. Для вероятности связности Pj(G) узлов i, j графа G доказаны следующие утверждения. Теорема 1. Если p(v) = h, v Е V, то Pij(G) - C(i,j)hD(i,j), h м 0. (1) min C(i, j). (i,j): D(i,j)=D Для нахождения всех элементов матриц \\D(i,j)||nj=i, ||C(i,j)||nj=i асимптотической формулы (1) построены модификации известных в теории графов алгоритмов (в том числе Флойда — Стейнберга). Такая процедура является более экономичной, чем последовательное определение элементов этих матриц, имеет вычислительную сложность O(n3lnn) для матрицы ||D(i,j^^^ и O(n4) для матрицы ||C(i,j)Hrij=1. Зная матрицу IlD(i,j^IT^, можно вычислить диаметр D графа G. Для сетей с ограниченным диаметром D сложность вычисления матриц IlD(i,j)|Щj=1, IICs(i,j)I\nj^ составляет O(n3) арифметических операций. На основе построенного алгоритма для вероятности связности любой пары вершин графа был проведён вычислительный эксперимент. Зададим граф G матрицей смежности D = max D(i,j), C Следствие 1. Если p(v) = h, v G V, то min Pij (G) - ChD, h ^ 0, 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 0 Полагаем, что работоспособность его рёбер равна p(v) цированные алгоритмы, вычислим h = 0,01. Используя модифи- 0 1 2 1 2 1 0 1 2 121 1 0 1 2 2 1 1 0 1 211 2 1 0 1 2 2 2 1 0 111 1 2 1 0 1 2 , IIC (i,j )lH,j=i = 1 2 1 0 1 2 2 2 2 1 0 1 2 1 1 1 0 1 1 1 2 2 1 0 1 1 1 210 I\D(i,j )I\b=i Результаты вычислений вероятностей связности пар вершин Pj (G), формуле (1) и методом Монте-Карло (обозначим их P*j(G)) при 106 ставлены ниже: 1 ^ i,j ^ 6, по итераций пред- / 1 0,01 0,0002 0,01 0,0002 0,01 \ 0,01 1 0,01 0,0002 0,0001 0,01 0,0002 0,01 1 0,01 0,0001 0,0001 0,01 0,0002 0,01 1 0,01 0,0002 0,0002 0,0001 0,0001 0,01 1 0,01 V 0,01 0,01 0,0001 0,0002 0,01 1 I II Pij (G)j Время счета по формуле (1) составило 10 с, методом Монте-Карло — 6 ч. Более подробное изложение представленных результатов можно найти в [1].

Скачать электронную версию публикации