Вычисление вероятности несвязности планарного взвешенного графа с высоконадежными ребрами
Сергиенко Валентин Иванович
14 сентября 2018
235
Предметная область | — |
Отрасли по ОКВЭД | — |
Страна, регион, город | Российская Федерация, Приморский край, Владивосток |
Отличия от конкурентов | — |
Вид документа об охране ИС | программа для ЭВМ |
Номер документа ИС | 201561293 |
Дата регистрации документа ИС | 2015-02-26 |
Необходимые инвестиции для внедрения | договорная |
Сроки внедрения | — |
Стоимость предоставления технологии | договорная |
Наличие экспертного заключения | Нет |
Польза для потенциального потребителя
Программа создана на основе разработанного авторами алгоритма. Построенный алгоритм имеет кубическую сложность по числу ребер в отличие от классических переборных алгоритмов. Основными этапами построения алгоритма являются доказательство асимптотического соотношения для вероятности несвязности и получение формул вычисления его параметров (минимального объема разрезов и некоторого весового коэффициента). Расчет асимптотических констант осуществлялся для планарных графов с использованием перехода к двойственному графу. Построенный алгоритм был протестирован на планарных графах с различным минимальным объемом разрезов, в том числе на сотовых структурах. Время счета составляло несколько секунд, а методом Монте-Карло несколько часов.