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

Сергиенко Валентин Иванович
14 сентября 2018
157
Предметная область
Отрасли по ОКВЭД
Страна, регион, город Российская Федерация, Приморский край, Владивосток
Отличия от конкурентов
Вид документа об охране ИС программа для ЭВМ
Номер документа ИС 201561293
Дата регистрации документа ИС 2015-02-26
Необходимые инвестиции для внедрения договорная
Сроки внедрения
Стоимость предоставления технологии договорная
Наличие экспертного заключения Нет

Польза для потенциального потребителя

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