Приближенное вычисление вероятностей связности пар вершин графа с низконадежными ребрами

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

В основе программы лежат асимптотические отношения, параметры которых определяются с помощью разработанных модифицированных алгоритмов Флойда-Стейнберга. Алгоритм заключается в определении минимального числа ребер в путях между всеми парами вершин на основе матрицы смежности с помощью модификации известного алгоритма Флойда. Модификация заключается в изменении начальных данных длины ребра на 0 и 1,  что уменьшает количество необходимых итераций. Далее определяются соответствующие числа минимальных путей для всех пар вершин на основе специально полученных формул, представленных в работе [1].

На основе полученных данных строятся асимптотические соотношения, характеризующие вероятность связности соответствующих пар вершин. В пересчете на одну пару вершин, количество необходимых арифметических операций и  время счета существенно сокращается.                                                                                                                                                                                                      

Программа может быть использована при исследовании различных случайных сетей и проектировании новых информационно-технических систем.        [1]  "Асимптотика вероятности связности графа с низконадёжными рёбрами", Прикладная дискретная математика, 2013, № 1, 93–98.  

В отличие от программ аналогичного типа данная программа позволяет:

1. Определять вероятности связности всех пар вершин графа произвольного вида;

2. Использовать новые, модифицированные алгоритмы, уменьшая вычислительную сложность;

3. Не требовать высоких технических характеристик к используемым аппаратным средствам.

Функциональные ограничения - в силу используемых формул вероятность связности ребра должна быть меньше чем 0,01.

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

Программа разработана на Object Pascal  в среде разработки Delphi 7.