Расчет вероятности связности случайного графа. Версия №2

Назначение – программа для точного расчёта вероятности связности случайного графа с ненадёжными рёбрами.

Область применения - анализ надёжности и живучести сетей различного назначения.

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

Для расчёта используется рекурсивный алгоритм факторизации (ветвления, Мура-Шеннона) с выбором разрешающего ребра по критерию минимума суммы степеней смежных вершин. Рекурсии продолжаются до достижения графов с пятью и менее вершинами, для расчёта надёжности которых используются специальные формулы [2]. При каждом рекурсивном вызове  граф подвергается последовательно-параллельному преобразованию. На предварительном этапе осуществляется удаление "прикрепленных деревьев" и разложение графа на блоки (двусвязные компоненты). Далее для каждого блока производится декомпозиция по его двухвершинным сечениям [1].

Входные данные программы – граф, вероятности присутствия рёбер.

Выходные данные программы – значение вероятности связности графа.

Программа работает с двумя представлениями графов – полный файл предшественников (списки KAO,FO) и список рёбер. Вводить списки представления графов и редактировать их можно в соответствующих окнах программы, возможна загрузка (сохранение) графов из текстовых файлов (в текстовые файлы). Информация в файле должна располагаться следующим образом: первая строка – количество вершин, вторая строка – количество рёбер, третья и четвёртая строка – списки представления графа (элементы списка разделяются запятыми). Есть возможность генерации связных графов.

[1] Migov D.A., Rodionova O.K., Rodionov A.S., Choo H. Network Probabilistic Connectivity: Using Node Cuts // EUC Workshops, Springer-Verlag LNCS, vol. 4097, 2006. - P.702-709.

[2] Мигов Д.А. Формулы для быстрого расчета вероятности связности подмножества вершин в графах небольшой размерности // Проблемы информатики, № 2(6), 2010. –  С.10-17.

Функциональные возможности – расчёт вероятности связности графов с количеством элементов около сотни.

Инструментальные средства создания - Delphi.

По сравнению с 1 версией программы (№ PR10003) внесены следующие изменения:

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

- ветвление прекращается по достижению графов с пятью и менее вершинами, для расчёта надёжности которых используются специальные формулы, что также увеличивает быстродействие;

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