1 Общие определения, мотивация и план работы 3
2 Существующие результаты для стандартной решётки Z2 6
3 Множество Г8 и его граница для регулярного графа G8 8
4 Алгоритм для определения принадлежности множеству
11
5 Периодичность Г8, оценка на среднее количество песка
для стабилизируемых матриц 12
6 Примеры паттернов, соответствующих видимым вершинам конусов в Г8 15
7 Гипотезы, основанные на экспериментальных фактах 19
8 Теоретические результаты для конкретной последовательности конусов 22
Дипломная работа посвящена изучению песочной модели на некотором регулярном графе. Приведем основные определения.
Определение 1.1. Состоянием песочной модели на графе G = (V, E) будем называть функцию ф: V ^ Z. Мы интерпретируем ф(х) как количество песчинок в вершине х G V.
Если для х G V верно ф(х) > deg(x) (число песчинок в вершине не менее степени вершины), то мы называем эту вершину нестабильной и разрешаем сделать в ней обвал. В результате такого обвала получается новое состояние ф1 по следующему правилу:
{
ф'(у') = ф(у) - deg(y), если у = х,
ф'(у) = ф(у) + 1, если (х, у) G E,
ф'(у) = ф(у), иначе.
При обвале происходит перераспределение песка в графе — из нестабильной вершины в каждого соседа уходит по одной песчинке.
Состояние ф называется стабильным, если все вершины в графе являются стабильными, то есть для любой вершины х G V выполнено ф(х) < deg(x).
Релаксацией называется выполнение обвалов в вершинах, пока эти обвалы возможны. Результат релаксации состояния ф будем обозначать ф°. Если существует конечная релаксация (а для состояний с конечным суммарным числом песчинок на связном бесконечном графе это всегда так), то состояние ф называется стабилизируемым или релаксируемым и определена функция числа обвалов, или одометр, u: V ^ Z>0, для каждой вершины х равная количеству обвалов в х во время релаксации. Несложно показать, что число обвалов в вершине не зависит от порядка выполнения обвалов в вершинах.
Иногда рассматривают песочные модели со «стоками» — выделенными вершинами графа, при попадании в которые песок «исчезает», или, что эквивалентно, в стоках запрещено делать обвалы. Наличие подобных вершин существенно для конечных графов, поскольку иначе процесс релаксации может не закончиться. Например, если суммарное количество песчинок во всех вершинах больше суммарной степени всех вершин. Нашим основным объектом изучения будет песочная модель на связном бесконечном графе (но с конечным суммарным числом песчинок), стоков в нашей модели не будет.
Определение 1.2. Пусть дана функция f: V ^ Z, определим дискретный лапласиан функции f на графе G следующим образом:
Acf(ж) = ^2 (f(y) -f(ж)) = 5Z f(y)- deg(x) ' f(x).y|(y,x)eE y|(y,x)eE
Обычно будет понятно о каком графе идёт речь, поэтому нижний индекс лапласиана мы будем опускать...
Мы провели следующие вычисления на компьютере: взяли все пары рациональных чисел (a, b) G [0,12] х [0, 6] со знаменателем 256, и для каждой такой пары посчитали sup{c | M8(a, b, c) G Г8} с точностью до 1/256. После этого, пользуясь периодичностью, эти данные продолжили на квадрат [0,12] х [0,12] по Предложению 5.1. Таким образом мы получили результат, отражённый на Рис. 4.
Предложение 6.1. Если c > 6 + , то для всяких a, b G R выполнено
(a, b, c) G Ц.
Доказательство. Произведённые вычисления показали, что для любых n, m G Z оео Дп~ m 6 + Е1 / г'
Z выполнено 256 , 256,6 + 256 G Г 8.
Допустим, что существует тройка (a, b, c) такая, что c > 6+ и (a, b, c) G Г8. Возьмём n = [256-a], m = [256-b]. Обозначим D = dist ((a, b), (^fg, 256)) • Оценим D сверху:
D < la — I + lb ——I = —— (|256 • a — n| + |256 • b — m|) < ——.
“ I 2561 I 2561 256 V| | | |y < 256
По Предложению 3.2 из (a, b, c) G Г8 следует, что (^fg, m, c — D) G Г8. При этом c — D > 6 + 256, пришли к противоречию с имеющимися результатами вычислений. □
В ситуации с G4 большую роль играли локальные максимумы на аналогичной картинке, они отвечали некоторым паттернам на областях в искомом пределе.
Также компьютер вычислил результат релаксации состояния, в котором в начале координат находится 107 песчинок, а в остальных вершинах песчинок нет, результат отражён на Рис. 1.
Из проделанных вычислений мы видим, какие тройки (a, b, c) будут точками локального максимума(относительно c), а также какой паттерн будет им соответствовать.
Далее для обозначения вершины с 0 песчинок будем использовать О, для 1 — , для 2 , для 3 , для 4 /, для 5 4/, для 6 Ж для 7 — ■...
