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

• Автор: Караваев, Артем Михайлович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Петрозаводск
• Количество страниц: 145 с. : ил.

Оглавление
Введение
Терминология и система обозначений
Вспомогательная терминология
Общая схема алгоритма
Состояния и переходы
Список обозначений
1 Обзор литературы
1.1 Подсчет циклов в сеточных графах
1.2 Константа связности
1.3 Вычислительные особенности
метода матрицы переноса
1.4 Особенности распараллеливания
1.5 Явные формулы
и рекуррентные соотношения
1.6 Экстраполяция числовых
последовательностей
2 Метод матрицы переноса
2.1 Общее описание метода
2.2 Применение метода матрицы переноса
к поставленным задачам
2.3 Примеры применения метода
к небольшим графам
2.3.1 Число циклов на решетках У3 х Уп и СР4 х Уп

2.3.2 Число циклов на цилиндрах Єз х 7п и С4 х Тп
2.3.3 Число циклов на торах Єз х 0П и С4 х Сп
2.4 Выводы к главе
3 Кодирование состояний в задачах подсчета циклов
3.1 Кодирование состояний
на решетках и цилиндрах
3.1.1 Переходы между состояниями
3.1.2 Метод динамического программирования
3.1.3 Методы распараллеливания
3.1.4 Оптимизация
3.2 Кодирование состояний на торах
3.2.1 Переходы между состояниями
3.2.2 Метод динамического программирования
3.2.3 Количество состояний
3.2.4 Оптимизация
3.3 Выводы к главе
4 Предельные свойства в задачах подсчета циклов
4.1 Рекуррентные соотношения
4.1.1 Алгоритм вывода рекуррентных соотношений
4.1.2 Результаты, полученные алгоритмом
4.2 Асимптотика последовательностей
4.2.1 Ускорение сходимости
4.3 Асимптотика для циклов на торе
4.3.1 Гипотеза о виде асимптотики
4.4 Выводы к главе
Заключение
Список использованных источников

Введение
Подсчет гамильтоновых циклов в сеточных графах является одной из классических задач перечислительной комбинаторики. Однако помимо чисто комбинаторного интереса, связанного с непре-кращающимся поиском новых алгоритмических подходов к решению перечислительных задач, не меньшее значение имеет физическая интерпретация получаемых результатов. В решеточных моделях статистической механики задача подсчета количества конформаций плот-ноупакованных макромолекул в ряде важных случаев сводится к подсчету гамильтоновых циклов, позволяя, тем самым, определить важнейшие термодинамические потенциалы таких систем непосредственно из их микроскопической модели.
В работе рассматриваются три семейства графов: прямоугольные решетки х 7ті, цилиндры Ст х 7п и торы Єт х Сп (рис. 1).
Рисунок 1 — Примеры сеточных графов.
Слева направо: решетка У4 х У в, цилиндр 68 х У6 и тор Сб х С8

В небольшом числе случаев можно отыскать явную формулу, выражающую количество циклов в сеточных графах с фиксированным параметром т относительно меняющегося параметра п. Именно в таком виде были впервые получены явные выражения для числа циклов в семействах Уз х Уп и У4 х Уп [40].
Позднее выяснилось, что явные формулы в виде кратных сумм выглядят чрезвычайно громоздко, поэтому потребовался другой способ записи решения. Наиболее оптимальным оказалось представление решения в виде рекуррентного соотношения. Было показано, что полученные ранее последовательности, включая У 5 х Уп [41,42], удовлетворяют линейным рекуррентным соотношениям с постоянными коэффициентами.
В результате дальнейших исследований было установлено, что аналогичные рекуррентные соотношения имеют место при любых фиксированных значениях т, поскольку для подсчета циклов может быть использован метод матрицы переноса. В свою очередь, теорема Кэли — Гамильтона позволяет оценить порядок рекуррентного соотношения сверху порядком матрицы переноса. Данное обстоятельство позволило продлить цепочку рекуррентных соотношений для циклов на решетке вплоть до значения т = 9 [33]. В работе [35] было показано, что для графов, допускающих представление вида С х Уп, линейные рекуррентные соотношения естественным образом возникают при подсчете не только циклов, но и ряда других важных структурных параметров. Рекуррентные соотношения для числа циклов на цилиндрах Ст х Уп при т = 3,4,5 вытекали из указанных результатов в качестве частных случаев. Небольшой набор значений параметра т явился следствием попыток автора разработать универсальный алгоритм вывода рекуррентных соотношений, применимый к любому графу вида С х Д.