Пятница, 23 марта, ауд. 106. Начало в 18:00.
Докладчик: А. Н. Воропаев (Петрозаводский государственный университет).
Тема: Явные формулы для подсчёта циклов фиксированной длины в неориентированных графах.
Abstract
Явные формулы для подсчёта циклов длиной k представляют собой комбинации сумм, соответствующих разнообразным формам замкнутых маршрутов длиной k. Члены сумм составляются из элементов матрицы смежности, её степеней и других матриц.
Идея вывода таких формул возникла ещё в середине прошлого века, и до сих пор все известные выражения выводились "вручную". В нашей работе предложены алгоритмы, позволяющие автоматизировать вывод явных формул, а также учесть специфику графов при выводе.
С помощью системы компьютерной алгебры удалось существенно расширить набор известных выражений. На основе накопленных данных были сформулированы и обоснованы оценки вычислительной сложности явных формул, как в случае произвольных графов, так и для частных семейств графов.
Особое внимание уделено подсчёту циклов в двудольных графах с заданным обхватом. Был проведён сравнительный анализ эффективности использования явных выражений и нескольких известных альтернативных алгоритмов, предложенных в рамках изучения LDPC-кодов.
Явные формулы применимы не только для численных расчётов, но и для символьных преобразований. Интересным примером, на котором мы опробовали аналитические вычисления, является задача о количестве k-угольников конечной проективной плоскости.
