Локализация траекторий на конечном регулярном графе с дефектом

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Московский институт электроники и математикиим. А.Н. Тихонова

Выпускная квалификационная работа

Локализация траекторий на конечном регулярном графе с дефектом

по направлению 01.03.04 Прикладная математика

Синицын Александр

Москва 2020

Аннотация

Объектом исследования данной работы являются два класса древовидных графов. Оба имеют одинаковую степень всех вершин p, кроме корня степени p₀и концевых узлов. В одном случае концевые узлы остаются свободными, т.е. степени 1, в другом случае концы соединяются между собой таким способом, что их степени тоже равны p. Цель работы - анализ и сравнение асимптотического поведения функции количества путей этих графов. В процессе работы были рассмотрены конечные и бесконечные древовидные графы с одной особой вершиной в корне, проанализированы и изучены регулярные графы с одной особой вершиной, проведено сравнение асимптотического поведения количества путей для двух классов графов, выведены законы изменения времени релаксации для двух классов графовв зависимости от степени вершины и количества поколений регулярных графов. Для этого были разработаны алгоритмы на языках WolframLanguage, используя систему WolframMathematica.

In this work, two tree-like graph classes are studied. Both have the same vertex degree p, excluding root of degree p₀ and lists. In one case the lists are not interconnected, meaning that their degrees are 1. In other case the lists are interconnected in such a way that their degrees equal p. The goal of this work is to analyze and compare asymptotic behavior of path counting on such graphs. Finite and infinite tree-like graphs with one special vertex in the root were reviewed in this study. Regular tree-like graphs with one special vertex in the root were analyzed in this study. Comparing of asymptotic behavior of the number of paths in these two classes of graphs was conducted and the formulas for relaxation timedepending on vertex degree and number of generations of regular graph were derived. The Wolfram language algorithms were developed for that purpose using Wolfram Mathematica. асимптотическое поведение графа алгоритм

Содержание

• Введение
• 1. Обзор проблематики
• 1.1 Постановка задачи
• 1.2 Анализ решений в несоединенном случае
• 1.3 Соединенный случай
• 2. Описание решений
• 2.1 Прямое сравнение количества путей
• 2.2 Логарифм количества путей
• 2.3 Анализ собственных значений
• Заключение
• СписокИсточников


Введение

Проблема асимптотического поведения функции количества путей уже была рассмотрена на некоторых классах графов в [1;5]. В этой работе продолжается исследование, начатое в [5], и проводится сравнение двух классов графов. Для начала проводится литературный обзор существующих работ. Изучается древовидный граф, представленный в [1], вершины которого имеют одинаковую степень, за исключением одной корневой вершины и концевых узлов (пр. рис. 1). Для этого вводится функция Z_N(x), равная количеству путей длины N, заканчивающихся на расстояния xот корня. Как показано в [1], эта функция зависит от максимального собственного значения матрицы смежности. При больших степенях и количестве поколений в таком графе изучать матрицы смежности становится проблематично, поэтому вводится матрица перехода, позволяющая менее трудоёмко вычислять Z_N(x). В [2;3] показано, что собственные значения такой матрицы являются собственными значениями матрицы смежности, что позволяет значительно упростить анализ и вычисления. Далее, в [1] показывается, что в таком графе максимальное собственное значение равно , где p₀-степень корня, а p-степень остальных вершин, кроме концевых узлов.

При рассмотрении того же графа, но с бесконечным числом поколений обнаруживается критическое значение ,при переходе через который поведение функции Z_N(x) меняется. Если степень корневой вершины больше критического значения, то в таком графе наблюдается локализация около корня. Если меньше - локализация не наблюдается.

В этой работе изучается поведение другого класса графов - регулярного графа с одной особой вершиной, так называемым дефектом. Концевые узлы такого графа замкнуты на самих себя таким образом, чтобы их степень тоже равнялась p. В [5] показано, что асимптотическое поведение не зависит от способа замыкания. В данной работе это подтверждается, используя выведенную матрицу перехода.

Во второй главе основной части сначала проводится прямое сравнение количества путей, результаты которого подтверждают выводы, сделанные в [5].Далее вводится функция, равная логарифму функции количества путей, деленного на длину пути. Выбрана именно эта функция, потому что при длине пути, стремящемуся к бесконечности, эта функция стремится к константе. Показано, что эта константа равна логарифму максимального собственного значения соответствующей матрицы смежности. Т.к. собственные значения имеют ключевую роль в исследовании этих графов, далее рассматриваются максимальные собственные значения и их разница со вторыми максимальными собственными значениями. Выводится закон, которому подчиняется поведение разницы между двумя максимальными собственными значениями в таких графах.

Вычисления и построения графиков были проведены, используя WolframLanguageи Python.

1. Обзор проблематики

1.1 Постановка задачи

В данной работе исследуются асимптотические различия между двумя классами древовидных графов. Оба имеют одинаковую степен всех вершин p, кроме корня степени p₀и концевых узлов. В одном случае концевые узлы остаются свободными, т.е. степени 1 (рис. 1), в другом случае концы соединяются между собой таким способом, что их степени тоже равны p (рис. 2).

Рис. 1.G (4,3,3)с несоединенными листами

Рис. 2.G (4,3,2) с соединенными листами

На рис. 2 граф имеет вершину p₀ степени 4, называемую далее корнем или нулевым поколением. У всех остальных вершин на этом рисунке степень 3, включая концевые узлы (номера 0-7), называемое далее последним поколением. Обозначение G (4,3,2)означает, что в этом графеp₀ = 4,p = 3и количество поколений n = 2.Поведение графов в несоединенном случае уже было исследовано [1], в данной работе исследуются графы с соединенным последним поколением и сравниваются с поведением графов в первом случае.

1.2 Анализ решений в несоединенном случае

Представим краткий обзор решений, представленных в [1]. Пусть имеется ненаправленный конечный граф G, и его матрица смежности B_G. Количество путей длины NZ_N(x)из корня в поколение xопределяетсявозведением матрицы смежности в степень N - B_G^N. Элементы этой матрицы являются значениями количества путей из вершины iв вершину j, где iиj-соответствующие строка и столбец этой матрицы. Тогда функция Z_N(x)вычисляется по формуле:

Это означает, что асимптотическое поведение этой функции зависитот максимального собственного значения матрицы смежности ?_max(G) [1].

Возводить матрицу смежности в степень может оказаться проблематичным при больших N иn.Количество вершин растёт экспоненциально с количеством поколений, но в [2;3] был предложен способ заменить матрицу смежности на другую, более простую, используя её свойство симметричности. Согласно этим исследованиям, спектр матрицы смежности совпадает со спектром матрицы, элементы которой представлены следующим образом:

(1)

Таким образом, нахождение максимального собственного значения матрицы смежности сводится к нахождению максимального собственного значения гораздо меньшей матрицы A_n, количество строк и столбцов которой равно не количеству вершин графа, а количеству его поколений. Её гораздо легче исследовать как численно, так и аналитически.

Чтобы найти это максимальное собственное значение, отвечающее за асимптотику функции количества путей, рассмотрим характеристический многочлен P_n(p0, p)матрицы A_n, который задаётся следующим рекуррентным образом [4]:

Решение этой системы представлено в [1]. Для каждого nбыло получено одно действительное значение, которое отвечает за ?_max⁽ⁿ⁾. Предел этого решения при n>?:

Отсюда следует, что асимптотическое поведение функции количества путей на несоединенном конечном дереве с корнем p₀и вершинами pпри N>? выражается формулой:

Теперь рассмотрим бесконечный граф такой же структуры. Рекурсивная функция количества путей длины NZ_N(x)может быть представлена следующим образом:

В [1] представлено решение этой системы, и она основе этого были сделаны два важных вывода для всей работы в целом:

1) При общее количество траекторий: , где не зависит от N. Здесь, по большому счёту, корень p₀ никак не влияет на асимптотическое поведение функции, и любая типичная траектория из N шагов заканчивается на расстоянии от начала.

2) При наблюдается иная картина. Количество путей сильно зависит от p₀, что является признаком локализации вокруг корня. Сам факт, что функция количества траекторий зависит от p₀ при любом N говорит о том, типичные траектории возвращаются в начало при любом N.

1.3 Соединенный случай

Получив эти заключения, приступим к рассмотрению второго случая, когда концевые узлы соединены между собой таким образом, что их степень тоже равнялась p. В ходе [5] было выяснено, что поведение Z_Nне зависит от способа соединения. Действительно, если рассмотреть матрицу перехода количества путей из поколения xв поколение x+1, то для всех поколений, кроме нулевого и последнего, будет p-1 вариантов перейти в следующее поколение и 1 вариант вернуться обратно. Рекурсивно функция будет задана следующим образом:

Матрица перехода для неё будет совпадать с матрицейA_n(1), описаннойранее, не считая последнего элемента. Она будет одинакова для любого способа соединения. Элементы этой матрицы будут равны:

Эту матрицу легко анализировать, и в ходе её рассмотрения были подтверждены результаты, полученные в [5]. Её собственные значения совпадают с собственными значениями матрицы смежности графа, что в дальнейшем сильно упростит вычисления количества путей и набора собственных значений.

На основе изучения теории предыдущих исследований можно сделать следующие выводы:

1) Асимптотическое поведение функции количества путей длины NZ_N(x)контролируется максимальным собственным значений матрицы смежностиB_G.

2) Матрицу смежности B_Gможно без потери функциональности заменить на более простую матрицу A_n, спектр которой совпадает со спектром матрицы смежности.

3) Для несоединенного случая существует критическое , при превышении которого поведение кардинально меняется. Если , то локализации не наблюдается. Если , то корень служит центром локализации путей.

4) В соединенном случае асимптотическое поведение количества путей не зависит от способа коммутации.

5) Матрица A_nтакже является матрицей перехода от Z(n-1) к Z(n).

2. Описание решений

Исследуем роль граничного условия в задаче о локализации траекторий на регулярном дереве с особой точкой, отличающейся по связности от остальных вершин графа. Для этого проведём сравнение асимптотического поведения количества путей длины на двух классах графов, описанных в предыдущей главе. Возьмём три значения p₀, большее, меньшее и равное критическому . Если p₀ превышает критическое значение, то наблюдается локализация, т.е. асимптотика траекторий такая, что они всегда будут возвращаться в корневую вершину. Еслиp₀ меньше критического значения, то локализации не наблюдается. Предполагается, что для в обоих случаях функция будет вести себя одинаково, т.к. граница редко посещается. Для значения функции должны отличаться кардинально.

Примем число поколений (т.е. расстояние от корня до границы) M = 100,количество шагов n = 100 000, p = 5,а критическое , соответственно, равно . Для рассматриваются три значения: 18, 20 и 22 - меньшее, равное и большее критического соответственно. Рассматриваются только чётные значения поколений, т.к. при чётном/нечётном количестве шагов в чётных/нечётных поколениях заканчиваются ноль путей для несоединенного случая и близкое к нулю значение для соединенного случая. Поэтому в следующих графиках по горизонтальной шкале отложено 50 значений - половина количества поколений. По вертикальной оси взяты не сами значения количества путей, т.к. они слишком велики, а их натуральные логарифмы для более наглядного примера. Для вычисления количества путей была использована матрица перехода, описанная в предыдущей главе. Матрицы перехода для обоих классов графов различаются только в одном элементе последней строки последнего столбца.

Для начала рассмотрим . Локализации около корня происходить не будет, и граница графа будет часто посещаться. От этого происходит различие в количестве путей, т.к. соединенные друг с другом листы будут давать большее количество вариантов. Причём чем ближе к границе, тем большее количество путей там концентрироваться для соединенного случая. Поэтому график для соединенного случая растёт быстрее, а его значения сильно больше несоединенного случая (рис. 3).

Рис. 3. Натуральный логарифм количества путей в зависимости от поколения, p0 = 18

Теперь взглянем на случай, когда . Тут локализации не происходит для обоих случаев, но из-за различия в строении графиков большое количество путей концентрируется на около границы для соединенного случая, а для несоединенного случая последнее поколение почти не отличается всех остальных. Кардинальные различия между графиками в этому случае начинаются около 90 поколения (рис. 4).

Рис. 4. Натуральный логарифм количества путей в зависимости от поколения, p0 = 20

Остался последний третий случай , в котором в несоединенном случае происходит локализация в корне. Тут она происходит и в соединенном случае, а графики так же начинают различаться только в конце. В соединенном случае мы видим небольшой отросток, который указывает на увеличение количества путей на конце (100 и 99 поколение) (рис. 5).

Рис. 5. Натуральный логарифм количества путей в зависимости от поколения, p0 = 22

Из этих графиков видно, что количество путей в соединенном случае похоже на несоединенный случай, но из-за особенностей строения суммарное количество изменено, а около границы наблюдается особое поведение. Это подтверждает результаты [5].

2.2 Логарифм количества путей

Нам известно [1], что функция количества путей как функция от количествашагов растёт экспоненциально. Введём следующую функцию:

При . Это позволяет ввести параметр, который может численно характеризовать оба случая, и с которым удобнее численно работать, так как он принимает меньшие значения и стремится к константе.

Рассмотрим те же три случая: меньший, равный и больший критического. Пусть . На графике (рис. 6) видно, что в обоих случаях функции стремятся к константе,а в соединенном случае значения гораздо большо, что и ожидалось. Различия между функциями начинаются при .

Рис. 6. Функция в зависимости от n, p0 = 18

Пусть теперь снова . На больших функции снова различаются (рис. 7). Это соответствует полученным ранее графику для (рис. 4). Тут различие начинается чуть позже, при .

Рис. 7. Функция в зависимости от n, p0 = 20

Теперь рассмотрим последний случай . Как и предполагалось, функции для соединенного и несоединенного случаев не отличаются друг друга, т.к. граница посещается редко и не имеет существенного влияния на поведение функции (рис. 8).

Рис. 7. Функция в зависимости от n, p0 = 22

В этом подразделе была численно исследована зависимость функции от количества шагов для трёх случаев (наличия локализации, отсутствия локализации и критического случая) и для отсутствия/наличия коммутации концевых узлов.

2.3 Анализ собственных значений

Как было показано ранее, максимальное собственное значение отвечает запредельные значения функции количества путей и, соответственно, функции ,определенной в предыдущем подразделе.Разница между первым и вторым собственным значением (первым и третьим, если первые два отличаются только знаком), определяет то, насколько быстро система выходит на свою асимптотику при . Рассмотрим разницу собственных значений в обоих случаях в зависимости от числа поколений. На рис.8 представлена зависимость логарифма разницы первого и третьего собственных значений от количества поколений при . На нём мы видим, что в соединенном случае логарифм разницы собственных значений линейно зависит от количества поколений, а график несоединенного случая напоминает график логарифма.

Рис. 8. Логарифм разницы первого и третьего собственных значений в зависимости от числа поколений,

Взглянем на зависимость этой разницы от логарифма числа поколений в несоединенном случае, чтобы убедиться, что это действительно график логарифма.

Рис. 9. Логарифм разницы первого и третьего собственных значений в зависимости от логарифма числа поколений,

Графики на рис. 8 и рис.9 позволяют сделать вывод о зависимости разницы собственных значений от числа поколений. Она будет представлена следующими уравнениями:

где x - разница между первым и третьим собственным значением в несоединенном случае, y-разница между первым и третьим собственным значением в соединенном случае, n -число поколений, а aи b- какие-то коэффициенты.

Немного видоизменив эти уравнения, получаем следующие равенства, определяющие по какому закону меняется разница между собственными значениями:

где .

Отсюда следует, что в соединенном случае разница растёт как степенная функция, а в несоединенном - экспоненциально.

Попробуем найти этот коэффициент.Для этого рассмотрим критический случай и построим зависимость коэффициента aот p. Используя линейную регрессию для pот 3 до 10 в соединенном случаеможно простроить зависимость:

Рис. 10. Зависимость коэффициента aот степени вершин pв критическом соединенном случае

Таблица 1

Т.к. в уравнении (3) a находится в степени экспоненты, возведём экспоненту в степень полученных значений, записанных в таблице 1. Таким образом, мы получаем ряд квадратных корней натуральных чисел. Отсюда можно сделать вывод, что. Тогда формула (3) предстаёт в следующем виде:

В несоединенном случае коэффициент aостаётся константой и равен -1.95. Тогда законы, по которым изменяется разница собственных значений матриц смежности обоих классов графов, можно записать в виде:

В этом подразделе были выведены законы изменения разницы между двумя максимальными собственными значениями матриц смежности двух классов графов.

Заключение

В данной работе были исследованы два класса графов. В первой главе основной части проведён литературный анализ предыдущих работ по теме, включая статьи российский и зарубежных авторов, а также результаты предыдущей работы автора по теме.Была выведена матрица перехода, существенно упрощающая аналитическую и вычислительную работу. Во второй главе представлены результаты, полученные в ходе самостоятельного изучения данной проблемы. Было показано, как ведёт себя функция количества путей в зависимости от наличия и отсутствия соединения концевых узлов. Была введена и исследована как показательный параметр функция логарифма количества путей для обоих классов графов. Проведя анализ собственных значений матрицы, были найдены законы, которым подчиняется разница между собственными значениями матрицы.

Список Источников

1. S.K. Nechaev, M.V. Tamm, and O.V. Valba, Path counting on simple graphs:from escape to localization, J. Stat. Mech., 053301 (2017); arXiv:1611.08880v3.

2. O. Rojo and R. Soto, The spectra of the adjacency matrix and Laplacian matrixfor some balanced trees, Linear algebra and its applications, 403, 97-117 (2005).

3. O. Rojo and M. Robbiano, An explicit formula for eigenvalues of Bethe trees andupper bounds on the largest eigenvalue of any tree, Linear Algebra and itsApplications, 427, 138-150 (2007).

4. V. Kovaleva, Yu. Maximov, S. Nechaev, and O. Valba, Peculiar spectralstatistics of ensembles of trees and star-like graphs, J. Stat. Mech., 073402(2017), arXiv:1612.01002.

5. Синицын А.Ю. Сложные сети: перечисление траекторий и локализация //Курсовая работа: МИЭМ НИУ ВШЭ, 2019

6. Z. Burda, J. Duda, J.M. Luck, and B. Waclaw, Localization of maximal entropyrandom walk, Phys. Rev. Letters, 102, 160602 (2009), arXiv:0810.4113v2.

Размещено на Allbest.ru