Пример вероятностного расчета на основе случайного графа

Задача 1.

Пусть задан случайный граф , изображенный на рис. 3, и требуется определить вероятность связности вершин 1 и 2 .

Существует несколько путей решения этой задачи.

Путь 1.

Сначала рассмотрим все возможные пути из вершины 1 в 2. Всего их два: ; .

Вероятность существования первого пути , второго – . Следовательно, вершины 1 и 2 связны с вероятностью

(1)

Путь 2.

Рассмотрим множество всех возможных неслучайных графов, которые можно получить на основе случайного. Каждый такой граф может появиться со своей вероятностью . Среди них выделим подмножество , в котором путь из вершины 1 в вершину 2 существует. Для рассматриваемого примера N = 8, К = 5. Список элементов и вероятности появления такого графа представлены в таблице 1.

N	Ребро 1-2	Ребро 2-3	Ребро 1-3	Вероятность появления
	нет	есть	есть
	есть	нет	нет
	есть	нет	есть
	есть	есть	нет
	есть	есть	есть

Теперь просуммируем вероятности, соответствующие элементам множества , и получим окончательный ответ, совпадающий с результатом формулы (1):

Путь 3.

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

Поскольку ребро 2-3 для случайного графа существует всегда, то вершины 2 и 3 можно объединить в одну, как показано на рис. 3. Для же ребро 2-3 просто отсутствует.

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

Для полученных с помощью декомпозиции случайных графов определим вероятность связности вершин 1 и 2:

(2)

(3)

Теперь, чтобы получить вероятность связности для случайного графа воспользуемся формулами (2) и (3):

(4)

Нетрудно проверить, что результаты формул (1) и (4) совпадают.

Декомпозицию для новых графов можно продолжать. При этом в узлы построенного таким образом «двоичного дерева» будут отображаться случайные графы. Существенно то, что случайные графы, находящиеся на нижних ярусах, будут иметь более простую топологию по сравнению с графами на вышестоящих ярусах.

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