Родионов А.С.
Полиномы надёжности случайных графов: получение и использование
В докладе обсуждаются вопросы получения и использования полиномов надёжности случайных графов с ненадёжными рёбрами. Для представления полиномов используется вид с наиболее информативными коэффициентами, некоторые из которых можно получать без расчётов либо с минимальными затратами исходя из их смысла, что позволяет существенно ускорить процесс вычислений. Наряду с исследованным автором ранее полиномом надёжности для всетерминальной (all-terminal) связности, рассматриваются полиномы для средней вероятности связности пары вершин и среднего размера связной компоненты, содержащей выделенную вершину. Для получения всех полиномов используется единый подход, основанный на методе факторизации по состоянию произвольно выбранного ребра, редукции размерности и получении точных выражений для графов специального вида и графов малой размерности.
В докладе рассматриваются также вопросы применения полиномов надёжности для оценки качества структур сетей различного назначения, проверки возможного изоморфизма графов и решения других задач структурной оптимизации сетей.
К списку докладов