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

Цель работы

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

Общие теоретические сведения

Введение

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

Дано: топология исходной системы распределенной обработки данных, набор резервных линий, надежность каждого из исходных и резервных элементов, стоимость каждой из резервных линий.

Минимизировать: суммарную стоимость введенных резервных линий.

Варьируются: топологические варианты введения резервных линий.

Ограничение: надежность синтезированного варианта топологии не менее заданной.

Физическая и математическая модели систем распределенной обработки данных

Физической моделью систем распределенной обработки данных можно считать совокупность узлов, некоторые из которых соединены линиями связи. Чаще всего оказывается допустимым считать узлы системы абсолютно надежными, так как их надежность многократно превышает надежность линий.

Поток отказов линий связи можно описать процессом восстановления с конечным временем восстановления.

Поток отказов линий связи допустимо описывать экспоненциальными законами распределений.

Опишем математическую модель системы распределенной обработки данных.

Абсолютно надежным узлам физической модели соответствуют вершины случайного графа, пронумерованные натуральными числами от 1 до n. Линиям связи физической модели соответствуют ребра графа, вершины графа абсолютно "надежны", а каждое из его ребер r "отказывает" и "восстанавливается" в соответствии с экспоненциальными законами распределений времен безотказной работы и восстановления имитируемых линий связи. Ребра ведут себя независимо.

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

Пусть 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)

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

Упрощает пользование методом следующее пояснение:

0 q_1,2 q_1,3... q_1,_k₊₁ q_1,_k₊₂... q_1,_n

0 q_2,3...................................

...................................

если (q_ij)= 0 q_k_,_k₊₁ q_k_,_k₊₂... q_k_,_n_,

...................................

0 q_n_-1,_n

то получается из (q_ij), если каждый обведенный элемент k строки умножить на лежащий над ним элемент первой строки, а после этого вычеркнуть из (q 4ij 0) первую строку и первый столбец.

Пример. Вычислим вероятность связности полного графа G на пяти вершинах при условии, что все его ребра отказывают с одной и той же вероятностью "q", т.е. графу G соответствует матрица

0 q q q q