Home

Пятница 10 февраля, 18-00, ауд. 106

Пятница, 10 февраля, ауд. 106. Начало в 18:00.

Докладчик: А.М. Караваев (Петрозаводский государственный университет).

Тема: Подсчет гамильтоновых циклов на прямоугольных решетках, цилиндрах и торах методом матрицы переноса.

Abstract

В докладе рассматривается применение метода матрицы переноса к задаче о подсчете гамильтоновых циклов к трем семействам графов: прямоугольным решеткам $ P_m\times P_n $, цилиндрам $ C_m\times P_n $ и торам $ C_m\times C_n $. Гамильтоновым циклом называется цикл, проходящий через каждую вершину графа в точности один раз. Задача о подсчете таких циклов в указанных графах является труднорешаемой и на данный момент неизвестно никаких эффективных методов ее решения при произвольных соотношениях между $ m $ и $ n $. Фиксируя один из параметров семейства, искомую величину можно, по крайней мере в принципе, отыскать методом матрицы переноса.

Доклад посвящен описанию возможностей метода матрицы переноса применительно к задаче подсчета циклов с использованием высокопроизводительных вычислений. Помимо эффективного способа кодирования состояний, способствующего достаточно сильному сжатию матрицы, речь пойдет о новом эффективном алгоритме вывода рекуррентных соотношений для числа циклов. Будет показано, как точные перечислительные методы позволяют проверять корректность гипотез, лежащих в основе физических теорий. В качестве примеров будет рассматриваться приложение из области физики полимеров и связанная с задачей стандартная $ O(n) $ модель среднего поля.