Матричный метод вычисления вероятности связности случайного графа

Пусть G - случайный, неориентированный граф без петель, сопоставлен системе распределенной обработки данных, для которой необходимо определить вероятность того, что в произвольный момент времени между любой парой узлов системы существует хотя бы один путь, т.е. вычислить вероятность P(G) связности графа G.

Пусть n - число вершин графа, а сами вершины пронумерованы натуральными числами от 1 до n. Символы [i,j] будем обозначать ребро G, соединяющее вершины "i" и "j". Пусть q_ij - вероятность отказа ребра [i,j] (при i=j, q_ij=0, что соответствует предположению об абсолютной надежности узлов системы).

Будем считать, что G - полный граф. В этом случае ребра графа, не имеющие аналогов - линий связи, характеризуются q_ij=1. Каждый такой граф полностью определяется симметрической матрицей (q_ij), у которой на главной диагонали стоят нули, а на месте i,j - вероятность отказа ребра [i,j]. Вероятность P(G) связности такого графа является функцией матрицы смежности (q_ij). Обозначая эту функцию через P_n((q_ij)), запишем:

, (1)

где - симметрические матрицы,

Дата добавления: 2014-01-15