| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Асимптотика количества конечных положений случайного блуждания на ориентированном гамильтоновом метрическом графе Д. В. Пятько, В. Л. Чернышев Национальный исследовательский университет "Высшая школа экономики", г. Москва
Англоязычная версия:
Mathematical Notes, 2023, Volume 113, Issue 4, Pages DOI: https://doi.org/10.1134/S0001434623030252 
Реферативные базы данных:
  1. Введение1.1. Постановка задачиРассмотрим ориентированный метрический граф (одномерный клеточный комплекс, см. книгу [1] и ссылки в ней). Каждое его ребро является гладкой регулярной кривой и имеет длину, а также разрешенное направление движения. Мы будем рассматривать ситуацию общего положения и предполагать, что все длины ребер линейно независимы над полем рациональных чисел. Также зафиксируем вершину, которую будем называть стартовой. Из нее в начальный момент времени выходит случайное блуждание (см. [2], [3]). В каждой вершине с ненулевой вероятностью мы можем выбрать исходящее ребро для дальнейшего движения. Развороты на ребрах запрещены. Для анализа числа возможных конечных положений такого блуждания полезно предположить, что реализуются все возможности. Таким образом, мы приходим к следующей динамической системе. В нулевой момент времени из стартовой вершины вдоль всех ребер, которые из нее выходят, начинают двигаться точки с единичной скоростью. Как только какая-то из точек оказывается в вершине, на каждом инцидентном вершине исходящем ребре появляется новая точка, которая начинает двигаться в сторону конца ребра, а старая исчезает. Если в одну вершину одновременно приходит сразу несколько точек, то все эти точки пропадают, а появляются новые точки так, как это было описано для одной точки. Наша основная задача: исследовать $N(T)$ – количество движущихся точек в момент времени $T$ на произвольном конечном компактном графе. Данная динамическая система уже рассматривалась для случая неориентированных графов (см. [4], [5]). Для числа движущихся точек было получено полиномиальное приближение, т.е. было приведено описание многочлена степени $E-1$, где $E$ – число ребер графа, который аппроксимирует $N(T)$ с точностью до некоторой степени логарифма. Рассмотрение подобных динамических систем было мотивировано задачами о распространении узких волновых пакетов на метрических графах и гибридных мноогообразиях (см. [6] и ссылки там). Совсем недавно для некоторого класса ориентированных графов (однонаправленные шпернеровы графы) в статье [7] был получен старший член асимптотики. В этой статье мы будем рассматривать произвольные ориентированные гамильтоновы графы. 1.2. Структура текста и рассматриваемые графыОпределение 1. Через $N(T)$ будем обозначать количество движущихся точек в момент времени $T$, а через $N_{x}(T)$ – количество моментов времени $\leqslant T$ таких, что в вершину номер $x$ заходили точки. Наша основная задача – найти асимптотику $N(T)$ для графов, которые будут описаны далее. Рассмотрим ориентированный гамильтонов граф $G=(V, E)$. Далее множество вершин графа будем обозначать как $V$. Дополнительно положим $n=|V|$. Также множество ребер будем обозначать как $E$; в графе допускаются кратные ребра (иногда граф с таким допущением называют мультиграфом), но петли (ребра из вершины в саму себя) не разрешаются. Будем рассматривать графы, в которых есть цикл $(1, 2, \dots, n)$; если этого цикла нет, то в силу гамильтоновости можно так перенумеровать вершины $\{2, \dots, n\}$, чтобы такой цикл был. Заметим, что для графа с перенумерованными вершинами $N(T)$ будет таким же, как и для исходного графа в любой момент времени. Время прохождения ребра будем обозначать $t(e)$, $e \in E$; также можно считать, что $t(e)$ – длина ребра, потому что точки движутся с единичной скоростью. Считаем, что случайное блуждание начинается из вершины с номером 1 и множество времен ребер $\{t(e),\,e \in E\}$ линейно независимо над $\mathbb{Q}$. Будем считать, что вершины и ребра пронумерованы: $(v_{1}, \dots, v_{n})$, $(e_{1}, \dots, e_{|E|})$. Напомним, что первое число Бетти метрического графа (т.е. одномерного клеточного комплекса) можно найти по формуле $\beta=|E|-|V|+1$. Будем рассматривать графы с $\beta \geqslant 2$. При $\beta=1$ получаем граф-цикл, для которого $N(T)=1$ для любого времени $T > 0$. Несколько слов о дальнейшем устройстве работы. В п. 3.1 мы показываем, что достаточно представить $N_{1}(T)$ в виде где $\beta$ – первое число Бетти нашего комплекса, чтобы получить асимптотику $N(T)$. Пункты 2.1–2.4 посвящены нахождению нужного представления для произвольных графов, которые уже были описаны в разделе 1. Пункт 2.5 содержит утверждения, используя которые, можно упростить вычисление коэффициента. В п. 3.2 мы, используя результаты из пп. 3.1 и 2.1–2.5, получаем итоговую формулу для $N(T)$.2. Классификация путей в стартовую вершину2.1. АлгоритмВведем несколько обозначений. Для каждой вершины $i$ существует ребро в следующую вершину: для $i \in \{1, \dots, n-1\}$ это $i+1$, а для $n$ это 1. Будем называть такие ребра внешними (если таких ребер несколько для вершины $i$, то берем любое; таких ребер может быть несколько, если есть кратные ребра). Цикл из внешних ребер будет называться внешним циклом. Остальные ребра будут называться внутренними. Цикл с внутренним ребром мы будем называть внутренним циклом. Для каждой вершины рассмотрим все выходящие из нее ребра. Зафиксируем на них порядок так, чтобы внешнее ребро было последним. Определение 2. Пусть $\mathcal{H}$ – множество всех таких графов $H$, которые получены из $G$ присвоением неотрицательных целых чисел ребрам так, что для любой вершины сумма чисел на входящих ребрах равна сумме чисел на выходящих. В контексте графа $a \in \mathcal{H}$ или его подграфа можно говорить о том, что граф или его подграф является нулевым или ненулевым. Первое означает, что все присвоенные числа на ребрах равны 0, а второе – что найдется ребро, число на котором не 0. В частности, можно говорить о том, что какое-то ребро является нулевым или ненулевым. Сложение двух графов $a \in \mathcal{H}$ и $b \in \mathcal{H}$ определяется естественным образом: в результирующем графе на каждом ребре написана сумма чисел соответствующих ребер графов $a$ и $b$. Умножение $a \in \mathcal{H}$ на целую константу $\alpha$ определяется как умножение присвоенного числа каждого ребра в $a$ на $\alpha$. Число, соответствующее ребру, может означать, сколько раз по нему прошли. Равенство суммы входящих сумме выходящих означает, что в вершину зашли и вышли одинаковое число раз. Множество $\mathcal{H}$ дальше понадобится для того, чтобы описать алгоритм на графах из этого множества. Предъявим алгоритм, который разбивает $H \in \mathcal{H}$ на циклы определенного вида. В начале алгоритма положим $H'=H$. В $H'$ будут меняться числа на ребрах и отметки во время работы алгоритма. Алгоритм разбиения на циклы. Шаг 1. Начиная из вершины 1, каждый раз выбираем первое неотмеченное ребро. Когда приходим в вершину, в которой уже были, полагаем $c$ – образованный цикл. Шаг 2. Пока в графе $H'$ все ребра вдоль цикла $c$ имеют числа больше 0, вычитаем 1 вдоль них и берем цикл $c$ в ответ. Шаг 3. Если цикл $c$ – внешний и нулевой, то останавливаемся. Иначе отмечаем первое нулевое внутреннее ребро в цикле $c$. Возвращаемся к шагу 1. Граф $H'$ меняется в ходе шага 2, когда из чисел на ребрах вычитаются числа, и в ходе шага 3, когда появляются отметки на ребрах. В ходе шага 1 и шага 2 цикл $c$ рассматривается как подграф $G$ (без присвоенных чисел на ребрах). В ходе шага 3 цикл $c$ рассматривается как подграф $H'$ (с присвоенными числами на ребрах). Лемма 1 ( корректность алгоритма разбиения на циклы). Пусть мы запускаем алгоритм на $H \in \mathcal{H}$, а $c$ – любой цикл, который получается в конце шага 2. Пусть $H' \in \mathcal{H}$ – то, что “осталось” от $H$ после нескольких шагов алгоритма. Тогда выполнены следующие утверждения: Доказательство. Для доказательства утверждений нам понадобится простое, но полезное наблюдение о том, что в ходе алгоритма сохраняется свойство, что в любой вершине сумма входящих ребер равна сумме выходящих. Сначала покажем, что если цикл $c$ внешний, то он нулевой. Пусть это не так, тогда в цикле $c$ есть хотя бы одно ненулевое ребро. Поскольку $c$ внешний, то все внутренние ребра уже отмечены, следовательно, все внутренние ребра нулевые. В силу инвариантности равенства суммы входящих и выходящих чисел на ребрах, получаем, что в $c$ на всех ребрах написаны ненулевые числа, но это противоречит выбору $c$, который согласно шагу 2 должен иметь нулевое ребро. Таким образом, достаточно рассмотреть случай, когда цикл $c$ не внешний. Пусть $e=(v, u)$ – ребро с нулевым весом в $c$. Если оно внутреннее, тогда все доказано. Предположим, что оно внешнее. Поскольку внешнее ребро – последнее среди выходящих из вершины, то ребро $e$ – последнее из $v$, к тому же число на $e$ – это 0, поэтому все ребра из $v$ имеют нулевые числа (ребра до $e$ имеют нулевые числа, поскольку они отмечены, а отмечаются только ребра с нулевыми числами). В силу инвариантности, все ребра в $v$ также с нулевыми числами и, соответственно, ребро $e'=(w, v)$ цикла $c$ тоже нулевым числом. Если оно внутреннее, то все доказано, иначе оно внешнее и можно продолжить аналогичные рассуждения. В рассуждениях мы идем сначала от вершины $v$ к $v-1$, потом $v-2, \dots, 1$, $n, \dots, v+1$ и показываем, что либо очередное ребро внешнее и продолжаем, либо ребро внутреннее и останавливаемся. Если ни одно ребро не оказалось внутренним, то получается, что $c$ – внешний цикл, что противоречит предположению. Только что проведенные рассуждения показывают корректность шага 3. В силу конечности ребер и появления все новых отметок после каждой итерации, алгоритм завершится. После завершения алгоритма $H'$ будет нулевым, поскольку все внутренние ребра будут отмеченными и следовательно нулевыми, внешние ребра, которые составляют внешний цикл, будут нулевыми в силу условия остановки. Замечание 1. Для любого $H \in \mathcal{H}$ всего будет $\beta$ итераций (запусков шага 1) алгоритма. Доказательство. Каждой итерации, кроме последней, можно сопоставить биективно внутреннее ребро, которое было отмечено на шаге 3. Всего внутренних ребер $|E|-|V|$, но осталось учесть последнюю итерацию с внешним циклом, таким образом, всего получается $|E|-|V|+1=\beta$ итераций. 2.2. Генерируемые наборы цикловКогда мы обсуждали разбиение $H \in \mathcal{H}$ на циклы с помощью алгоритма, мы говорили, что получаем в ответе набор, состоящий из каких-то циклов $c$. Давайте поймем, как описать получающиеся наборы циклов. Для этого введем следующее определение. Во всех дальнейших обозначениях считаем, что $c_i$ – простой ориентированный цикл в графе $G$. Простой цикл – обход графа, в котором первая и последняя вершины равны, а любая другая вершина обхода встречается 1 раз. Определение 3. Набор $(c_{1}, c_{2}, \dots, c_{k})$ называется полным набором генерируемых циклов, если выполнены следующие условия: В ходе построения набора в определении 3 поддерживается граф с отметками аналогично тому, как это происходит для алгоритма. Доказательство. Каждому циклу кроме последнего можно сопоставить биективно внутреннее ребро, которое было отмечено после прохождения этого цикла. Всего внутренних ребер $|E|-|V|$, но осталось учесть последний внешний цикл, таким образом, всего $|E|-|V|+1=\beta$ циклов в полном наборе. Определение 4. 1. Набор $(c_{1}, c_{2}, \dots, c_{k})$ называется набором генерируемых циклов, если $(c_{1}, \dots, c_{k})$ – подпоследовательность какого-то полного набора генерируемых циклов. 2. Набор $((c_{1}, a_{1}), (c_{2}, a_{2}), \dots, (c_{k}, a_{k}))$ называется набором взвешенных генерируемых циклов, если $(c_{1}, c_{2}, \dots, c_{k})$ – набор генерируемых циклов, $a_i \in \mathbb{N}$ произвольны. Определение 5. 1. Временем подграфа $G'$ графа $G$ будем считать $t(G')=\sum_{e \in G'}t(e)$. 2 Под временем $H \in \mathcal{H}$ будем понимать $t(H)=\sum_{i=1}^{|E|}b_it(e_i)$, где $b_i$ – число, присвоенное $i$-му ребру в графе $H$. 3. Временем набора взвешенных генерируемых циклов $c=((c_{1}, a_{1}), (c_{2}, a_{2}), \dots, (c_{k}, a_{k}))$, $a_i \in \mathbb{N}$, называется $t(c)=\sum_{i=1}^{k}a_it(c_i)$. В третьем пункте определения 5 $t(c_i)$ – время прохождения $i$-го цикла, $t(c_i)$ определяется в первом пункте того же определения. Лемма 2. Алгоритм задает отображение $\sigma$, которое сопоставляет $H \in \mathcal{H}$ набор взвешенных генерируемых циклов $c=\sigma(H)$ такой, что $t(c)=t(H)$. Доказательство. Давайте запустим алгоритм на $H$ и получим набор циклов Здесь все циклы взяты из соответствующей итерации алгоритма. Всего циклов $\beta$ штук в силу замечания 1. По лемме 1 получаем, что $\sum_{i=1}^{\beta}a_it(c_i)=t(H)$. Заметим, что для $(c_{1}, \dots, c_{\beta})$ выполнены все условия полного набора генерируемых циклов. Отбросим циклы с $a_i=0$ и получим искомый набор взвешенных генерируемых циклов. Пусть
$$
\begin{equation*}
T=\sum_{i=1}^{|E|}a_it(e_i), \qquad a_i \in \mathbb{N} \cup \{0\}.
\end{equation*}
\notag
$$
Построим граф $H$, в котором на ребре $e_i$ написано $a_i$. Определим $\omega(T)=H$. Тем самым мы задали функцию $\omega$. Введем функцию $\mu=\sigma \circ \omega$. Функция $\sigma$ “запускает” на графе $H \in \mathcal{H}$ алгоритм и выдает результат. Функция $\omega$ дает по времени граф, у которого есть информация о том, сколько раз по каждому ребру прошли. В определении $\omega$ граф существует в силу выбора $T$, на которых определена функция $\omega$ и $\omega(T)$ задан единственным образом в силу линейной независимости над $\mathbb{Q}$ времен прохождения ребер. Следует обратить внимание на то, что функция $\omega$ определена не для любых времен, а только для времен особого вида (линейных комбинаций длин ребер с целыми неотрицательными весами). Замечание 3. Функция $\mu$ сохраняет время, т.е. $t(\mu(T))=t(\sigma(\omega(T)))=T$, если $\omega(T) \in \mathcal{H}$ и $T=\sum_{i=1}^{|E|}a_it(e_i)$, $a_i \in \mathbb{N} \cup \{0\}$. Доказательство немедленно следует из того, что $t(\omega(T))=T$, и леммы 2. Лемма 3. Для любого времени $T \in \mathcal{T}$ существует такой набор взвешенных генерируемых циклов $c=\mu(T)$ такой, что $t(c)=T$. Доказательство. Возьмем $H=\omega(T)$. Поскольку $T \in \mathcal{T}$, то $H \in \mathcal{H}$. По лемме 2 к $H$ применима функция $\sigma$. Можем взять $c=\mu(T)$. По замечанию 3 выполняется $t(c)=t(\mu(T))=T$. 2.3. Достижимые наборы цикловЛемма 3 показывает, что мы можем сопоставить времени $T \in \mathcal{T}$ взвешенный набор генерируемых циклов $c$ со временем $T$ c помощью $\mu$, но обратное неверно. То есть если взять произвольный набор взвешенных генерируемых циклов $c$, то не обязательно существует $\mu^{-1}(c)$. Теперь мы хотим это исправить и сделать так, чтобы между $\mathcal{T}$ и каким-то множеством наборов взвешенных генерируемых циклов была биекция, задаваемая функцией $\mu$. Заметим, что инъекция уже есть. Действительно, разные $T_{1} \neq T_{2}$ будут давать $\mu(T_{1}) \neq \mu(T_{2})$, поскольку $t(\mu(T_{1}))=T_{1}$, $t(\mu(T_{2}))=T_{2}$ и $T_{1} \neq T_{2}$ по предположению. Для биекции осталось получить сюръекцию, но ее просто сделать: необходимо ограничить множество всех взвешенных генерируемых циклов до $\mu(\mathcal{T})$. Получается, что есть какое-то “хорошее” множество $\mu(\mathcal{T})$ наборов взвешенных генерируемых циклов. Давайте теперь поймем, как с помощью $\mu(\mathcal{T})$ считать $N_{1}(T)$. Доказательство. Первое равенство выполнено по определению $N_{1}(T)$. Второе выполнено в силу того, что $\mu$ – биекция между $\mathcal{T}$ и $\mu(\mathcal{T})$, которая сохраняет время. Таким образом, целесообразно ввести новый вид набора взвешенных генерируемых циклов. Для этого вида мы будем требовать $c \in \mu(\mathcal{T})$. Однако давайте введем этот вид немного по-другому, чтобы было удобнее использовать определение в доказательствах, а потом докажем эквивалентность требованию $c \in \mu(\mathcal{T})$. Определение 7. Набор $c=((c_{1}, a_{1}), (c_{2}, a_{2}), \dots, (c_{k}, a_{k}))$ является набором взвешенных достижимых циклов тогда и только тогда, когда выполнены следующие условия: Доказательство. Необходимость: достаточно показать $c \in \mu(\mathcal{T})$, но $c=\mu(t(c))$, $t(c) \in \mathcal{T}$. Достаточность: из $c \in \mu(\mathcal{T})$ следует $c=\mu(t')$, $t' \in \mathcal{T}$, но $t(c)=t(\mu(t'))=t'$, откуда $\mu(t(c))=c$, $t(c) \in \mathcal{T}$. Смысл условия 2) определения 7 в том, что набор $c$ будет получаться как результат алгоритма на $\omega(t(c))$. В этом смысле он “достижим”. Лемма 4. Если $c=((c_{1}, a_{1}), (c_{2}, a_{2}), \dots, (c_{k}, a_{k}))$ – набор взвешенных достижимых циклов, то для любых $b_i \in \mathbb{N}$ – тоже набор взвешенных достижимых циклов. Доказательство. Первое условие выполнено по определению набора взвешенных генерируемых циклов. Заметим, что условие 3 определения для $c$ эквивалентно тому, что $\omega(t(c))$ – эйлеров граф, содержащий вершину 1, если требовать, чтобы число проходов по ребру было равным числу на ребре. Поскольку в $\omega(t(c))$ и $\omega(t(c'))$ одинаковое множество ненулевых ребер, то по теореме об эйлеровости графа $\omega(t(c'))$ тоже эйлеров. Осталось показать, что выполнено второе условие. Пусть $d=\mu(t(c'))$, $d=((d_{1}, x_{1}), \dots, (d_{k}, x_{k}))$. Нужно показать $c'=d$. Поскольку $c$, $d$ – наборы взвешенных генерируемых циклов, то допустимо следующее представление:
$$
\begin{equation*}
\begin{gathered} \, \xrightarrow{V_{0}} (c_{1}, a_{1}) \xrightarrow{V_{1}} (c_{2}, a_{2}) \dotsb (c_{k-1}, a_{k-1}) \xrightarrow{V_{k-1}} (c_{k}, a_{k}), \qquad V_i=(V_i^{1} \dotsb V_i^{s_i}) \lor \varnothing, \\ \xrightarrow{U_{0}} (d_{1}, x_{1}) \xrightarrow{U_{1}} (d_{2}, x_{2}) \dotsb (d_{w-1}, x_{w-1}) \xrightarrow{U_{w-1}} (d_{w}, x_{w}), \qquad U_i=(U_i^{1} \dotsb U_i^{p_i}) \lor \varnothing . \end{gathered}
\end{equation*}
\notag
$$
Здесь $V_i$ и $U_i$ обозначают набор вершин, на ребрах из которых происходили отметки между циклами $c_{i-1}$ и $c_i$ или $d_{i-1}$ и $d_i$. Пусть алгоритм прошел до $(d_i, x_i)$, $i \in \{1, \dots, w\}$, в $d$, взял цикл $d_i$ $x_i$ раз и остановился. Тогда выполнено следующее:
Обсудим индукционный переход. Пусть все выполнено для $i$, докажем для $i+1$: Пусть
$$
\begin{equation*}
G_{c}=\omega(t(c)), \qquad G_{d}=\omega(t(d))=\sum_{j=1}^{w}x_jd_j.
\end{equation*}
\notag
$$
По определению $d$ имеем $G_{d}=\omega(t(c'))$. Также пусть $G_{d}^{i}$ – граф, который получился после прохождения алгоритма до $(d_i, x_i)$ включительно; аналогично определяется $G_{c}^{i}$. Заметим следующее:
$$
\begin{equation*}
\begin{aligned} \, G_{d}^{i} &=\sum_{j=i+1}^{w}x_jd_j=\sum_{j=1}^{w}x_jd_j- \sum_{j=1}^{i}x_jd_j =\sum_{j=1}^{w}x_jd_j -\sum_{j=1}^{i}b_jc_j =G_{d}-\sum_{j=1}^{i}b_jc_j \\ &=\omega(t(c'))-\sum_{j=1}^{i}b_jc_j=\sum_{j=1}^{k}b_jc_j -\sum_{j=1}^{i}b_jc_j=\sum_{j=i+1}^{k}b_jc_j; \end{aligned}
\end{equation*}
\notag
$$
здесь третье равенство выполнено по предположению индукции. Поскольку в $G_{d}^{i}=\sum_{j=i+1}^{k}b_jc_j$ есть ребра с ненулевым весом, то $k \geqslant i+1$. Заметим, что поскольку $G_{c}^{i}=\sum_{j=i+1}^{k}a_jc_j$, то в $G_{c}^{i}$ и $G_{d}^{i}$ совпадает множество ребер с ненулевым весом. Рассмотрим $V_i=(V_i^{1} \dots V_i^{s_i})$ и $U_i=(U_i^{1} \dots U_i^{p_i})$. Поскольку состояния одинаковые после $(c_i, a_i)$ в $c$ и $(d_i, x_i)$ в $d$ и множество ребер с ненулевым весом одинаковое, то циклы в данный момент будут одинаковыми и отметка пойдет на одни и те же ребра, т.е. $V_i^{1}=U_i^{1}$. Заметим, что опять состояние одинаковое, мы не поменяли числа на ребрах, поэтому так же множество ребер с нулевым весом совпадает, т.е. $V_i^{2}=U_i^{2}$. Не может быть так, что $s_i \neq p_i$, потому что тогда бы в каком-то цикле было ребро с нулевым весом, а в том же цикле, но в другом наборе оно было бы с ненулевым весом, т.е. $V_i=U_i$. Другими словами, мы дошли до $(c_{i+1}, a_{i+1})$ и $(d_{i+1}, x_{i+1})$. Поскольку $V_i=U_i$, то состояние одинаковое, т.е. $c_{i+1}=d_{i+1}$. Если $k=i+1$, то $G_{d}^{i}=b_{i+1}c_{i+1}$ и $x_{i+1}=b_{i+1}$, иначе посмотрим на ребро, которое было отмечено $V_{i+1}^{1}$. Оно входит в цикл $c_{i+1}$ и используется ровно $b_{i+1}$ раз. Все остальные ребра цикла используются $\geqslant b_{i+1}$ раз. То есть цикл $c_{i+1}$ будет вычитаться ровно $b_{i+1}$ раз, $x_{i+1}=b_{i+1}$.Получаем, что $k \geqslant w$, для всех $j \leqslant w$ выполнено $c_j=d_j$, $x_j=b_j$. То есть $d$ – префикс $c'$; если $k > w$, то $\omega(t(c')) \neq \omega(t(d))$, таким образом, $k=w$ и $c'=d$. Определение 8. Набор $(c_{1}, c_{2}, \dots, c_{k})$ называется набором достижимых циклов, если $((c_{1}, 1), (c_{2}, 1), \dots, (c_{k}, 1))$ является набором взвешенных достижимых циклов. Определение 8 подразумевает, что если $(c_{1}, c_{2}, \dots, c_{k})$ – набор достижимых циклов, то любой взвешенный набор с этими циклами является взвешенным достижимым, и наоборот, если $(c_{1}, c_{2}, \dots, c_{k})$ является генерируемым, но не достижимым, то любой взвешенный набор не будет взвешенным достижимым. Это верно в силу леммы 4. 2.4. Формула для $N_{1}(T)$Мы готовы сформулировать утверждение о точной формуле для $N_{1}(T)$. Теорема 1. Для $N_{1}(T)$, т.е. количества моментов времени $\leqslant T$ таких, что в вершину номер 1 заходили точки, справедливо следующее соотношение: Доказательство. Имеем следующую цепочку равенств: 2.5. Наборы взвешенных генерируемых циклов длины $\beta$Определение 10. Определим величину где $I\{X\}$ – индикатор истинности $X$, $e \in E$, $c=((c_{1}, a_{1}), \dots, (c_{p}, a_{p}))$ – набор взвешенных достижимых циклов. Лемма 5. Если $c=((c_{1}, a_{1}), \dots, (c_{p}, a_{p}))$, $d=((d_{1}, b_{1}), \dots, (d_{k}, b_{k}))$ – два набора взвешенных генерируемых циклов таких, что найдется $i$ такое, что для любого $j$, $1 \leqslant j < i$, выполняется $c_j=d_j \land a_j=b_j$, $c_i=d_i \land a_i \neq b_i$, то $t(c) \neq t(d)$. Доказательство. Допустим противное, $t(c)=t(d)$. Поскольку длины всех ребер линейно независимы над $\mathbb{Q}$, то для любого $e \in E$ должно быть выполнено $\mathrm{cnt}_{[1;p]}^{c}(e)=\mathrm{cnt}_{[1;k]}^{d}(e)$. Посмотрим на последовательность отметок. Возьмем $i$ из условия. Будем предполагать, что $i < p \land i < k$ (если $i=p \land i=k$, то очевидно; иначе пусть, например, $i=p$, $i < k$, тогда в наборе $d$ после $d_{p}$ произойдет отметка, и в новом неотмеченном ребре будет разным $\mathrm{cnt}$ по всему набору). Посмотрим на то, как получился цикл $c_{i+1}$ из $c_i$ и $d_{i+1}$ из $d_i$. Пусть для $c_{i+1}$ произошли отметки на $v_{1}, \dots, v_{s}$, а для $d_{i+1}$ – на $u_{1}, \dots, u_{t}$. Пусть $v_{1}=u_{1}$, обозначим через $e_{v}$ ребро, которое отметили. Получаем
$$
\begin{equation*}
\mathrm{cnt}_{[1;p]}^{c}(e_{v})=\mathrm{cnt}_{[1;i-1]}^{c}(e_{v})+a_i , \qquad \mathrm{cnt}_{[1;k]}^{d}(e_{v})=\mathrm{cnt}_{[1;i-1]}^{d}(e_{v})+b_i,
\end{equation*}
\notag
$$
но $\mathrm{cnt}_{[1;i-1]}^{c}(e_{v})=\mathrm{cnt}_{[1;i-1]}^{d}(e_{v})$, а при $a_i \neq b_i$ выполнено $\mathrm{cnt}_{[1;p]}^{c}(e_{v}) \neq \mathrm{cnt}_{[1;k]}^{d}(e_{v})$. Противоречие. Пусть теперь $v_{1} \neq u_{1}$. Ребро, которое мы отметили в $c$, обозначим через $e_{v}$, а в $d$ – через $e_{u}$. Получаем неравенства
$$
\begin{equation*}
\begin{aligned} \, \mathrm{cnt}_{[1;p]}^{c}(e_{v}) &=\mathrm{cnt}_{[1;i-1]}^{c}(e_{v})+a_i, \\ \mathrm{cnt}_{[1;k]}^{d}(e_{v}) &\geqslant \mathrm{cnt}_{[1;i-1]}^{d}(e_{v})+b_i, \\ &\Downarrow \\ b_i &\leqslant a_i, \end{aligned} \qquad \begin{aligned} \, \mathrm{cnt}_{[1;k]}^{d}(e_{u}) &=\mathrm{cnt}_{[1;i-1]}^{d}(e_{u})+b_i, \\ \mathrm{cnt}_{[1;p]}^{c}(e_{u}) &\geqslant \mathrm{cnt}_{[1;i-1]}^{c}(e_{u})+a_i, \\ &\Downarrow \\ a_i &\leqslant b_i. \end{aligned}
\end{equation*}
\notag
$$
Получаем $a_i=b_i$, противоречие. Определение 11. Будем называть два набора взвешенных генерируемых циклов $c=((c_{1}, a_{1}), \dots, (c_{m}, a_{m}))$ и $d=((d_{1}, b_{1}), \dots, (d_{k}, b_{k}))$ одинаковыми и писать $c=d$, если $m=k$ и для всех $i \leqslant m$ выполнено $c_i=d_i$ и $a_i=b_i$. В противном случае будем считать их разными и писать $c \neq d$. Лемма 6. Если $c=((c_{1}, a_{1}), \dots, (c_{\beta}, a_{\beta}))$ и $d=((d_{1}, b_{1}), \dots, (d_{k}, b_{k}))$, $k \leqslant \beta$, – два разных набора взвешенных генерируемых циклов, то $t(c) \neq t(d)$. Доказательство. Для удобства сравнения записей будем считать, что если до первого цикла нет отметок, то там есть “пустая отметка”. Поскольку $d$ – набор взвешенных достижимых циклов, то $d'=(d_{1}, \dots, d_{k})$ – набор генерируемых циклов, а они являются подпоследовательностью какого-то полного набора генерируемых циклов, то $d'$ можно записать как а взвешенный набор можно записать как В свою очередь для $c$ справедливо следующее представление:
$$
\begin{equation*}
\begin{gathered} \, (c_{1}, a_{1}) \xrightarrow{V_{1}}(c_{2}, a_{2}) \xrightarrow{V_{2}}(c_{3}, a_{3}) \dotsb (c_{\beta-1}, a_{\beta-1}) \xrightarrow{V_{\beta-1}} (c_{\beta}, a_{\beta}), \\ V_i=(v_i), \qquad i \in \{1, \dots, \beta-1\} \end{gathered}
\end{equation*}
\notag
$$
Рассмотрим два случая. Первый случай: $U_{0} \neq \varnothing$. Пусть $U_{0}=(u, \dots)$ и $e_{u}$ – ребро, которое было отмечено после первого прохождения $u$, тогда $\mathrm{cnt}_{[1; k]}^{d}(e_{u})=0$, $\mathrm{cnt}_{[1; \beta]}^{c}(e_{u}) > 0$. Получаем $t(c) \neq t(d)$. Второй случай: $U_{0}=\varnothing$. Поскольку $U_{0}=\varnothing$, то
$$
\begin{equation*}
\sigma=(d_{1}, b_{1}) \xrightarrow{U_{1}}(d_{2}, b_{2})\xrightarrow{U_{2}}(d_{3}, b_{3}) \dotsb (d_{k-1}, b_{k-1})\xrightarrow{U_{k-1}}(d_{k}, b_{k}).
\end{equation*}
\notag
$$
Заметим, что представления состоят из двух типов объектов: $(\cdot, \cdot)$ и $\xrightarrow{\cdot}$. Будем идти слева направо и сравнивать для $(\cdot, \cdot)$ $a_i$ и $b_i$, а для $\xrightarrow{\cdot}$ будем сравнивать наборы $V_i$ и $U_i$ как мультимножества. Если таким образом один из них есть собственный префикс другого, то, очевидно, $t(c) \neq t(d)$. Иначе существует $i$ такой, что $a_i \neq b_i \lor V_i \neq U_i$. В первом случае, когда $U_i=V_i$ и $a_i \neq b_i$, можно заметить, что
$$
\begin{equation*}
\forall\, j < i \qquad c_j=d_j \land a_j=b_j, \quad c_i=d_i \land a_i \neq b_i.
\end{equation*}
\notag
$$
По лемме 5 получаем, что $t(c) \neq t(d)$. Во втором случае $V_i \neq U_i$. Это значит, что есть внутреннее ребро $e_{u}$, которое было отмечено в $d$, но пока не было отмечено в $c$. Но поскольку $c$ – полный набор взвешенных циклов, то в какой-то момент в будущем мы переключимся c этого ребра дальше, но поскольку это произойдет после $\xrightarrow{V_i}$, то $\mathrm{cnt}_{[i+1;\beta]}^{c}(e_{u}) > 0$, но $\mathrm{cnt}_{[i+1; k]}^{d}(e_{u})=0$. Отсюда имеем
$$
\begin{equation*}
\begin{gathered} \, \mathrm{cnt}_{[1; \beta]}^{c}(e_{u})=\mathrm{cnt}_{[1; i]}^{c}({e_{u}}) +\underbrace{\mathrm{cnt}_{[i+1; \beta]}^{c}(e_{u})}_{> 0} , \\ \mathrm{cnt}_{[1; k]}^{d}(e_{u})=\mathrm{cnt}_{[1; i]}^{d}(e_{u}) +\underbrace{\mathrm{cnt}_{[i+1; k]}^{d}(e_{u})}_{=0}, \end{gathered}
\end{equation*}
\notag
$$
откуда следовательно, Лемма 7. Пусть $c=(c_{1}, \dots, c_{\beta})$ – набор генерируемых циклов длины $\beta$. Тогда $c$ – также набор достижимых циклов длины $\beta$. Доказательство. По определению 8 достаточно проверить, что $c'=((c_{1}, 1), \dots, (c_{\beta}, 1))$ – набор взвешенных достижимых циклов. Для него, в свою очередь, надо проверить, что выполнены условия из определения 7. Третье условие выполнено, так как $c_{\beta}$ – внешний цикл, который проходит по всем вершинам. Соответственно, если проходить по ребру число раз, которое написано на ребре, то получаем, что граф эйлеров. Проверим второе условие. Рассмотрим $d=\mu(t(c'))$, имеем $t(c')=t(d)$. Но по лемме 6 получаем $c'=d$. 3. Подсчет старшего коэффициента3.1. Результаты для произвольного ориентированного сильно связного графа $G$Следующая лемма справедлива для любого ориентированного сильно связного графа $G=(V, E)$ с линейно независимыми над $\mathbb{Q}$ ребрами, не обязательно гамильтонова. Обозначим через $N_{\tau, e, r}(T)$ количество точек в момент времени $T$ на отрезке длины $\tau$, который находится на расстоянии $r$ от начала ребра $e$. Значения $\tau$, $r$ выбраны так, чтобы отрезок полностью помещался на ребро. Лемма 8. Пусть нам известно, что число возможных движущихся точек, вошедших в первую вершину к моменту времени $T$, можно представить в виде $N_{1}(T)=a_{1}T^{\beta}+b_{1}T^{\beta-1}+O(T^{\beta-2})$, и пусть $r$ – расстояние до вершины 1 от начала отрезка. Тогда Доказательство. 1) Если $r$ – расстояние до вершины 1 от начала отрезка и $T'=T-r$, то 2) Докажем сначала для ребер длины $\tau=\varepsilon < t(e)$ для любых $ e \in E$. Отложим отрезок на ребре $e$ длины $\varepsilon$ и отрезок длины $\varepsilon$ на ребре $e_{1}$, которое выходит из 1 и от которого можно дойти до $e$. Пусть от конца отрезка на ребре $e$ до конца отрезка на ребре $e_{1}$ путь длины $p_{1}$, а от конца отрезка на ребре $e_{1}$ до конца отрезка на ребре $e$ путь длины $p_{2}$. Далее $r_i$ – расстояния, которые выбраны так, чтобы соответствующий отрезок полностью помещался на соответствующее ребро. Имеем
$$
\begin{equation*}
\begin{gathered} \, N_{\varepsilon, e_{1}, r_{1}}(T-p_{2}) \leqslant N_{\varepsilon, e, r_{2}}(T) \leqslant N_{\varepsilon, e_{1}, r_{1}}(T+p_{1}), \\ \varepsilon a_{1} \beta T^{\beta-1}+O(T^{\beta-2}) \leqslant N_{\varepsilon, e, r_{2}}(T) \leqslant \varepsilon a_{1} \beta T^{\beta-1}+O(T^{\beta-2}), \end{gathered}
\end{equation*}
\notag
$$
откуда
$$
\begin{equation*}
N_{\varepsilon, e, r_{2}}(T)=\varepsilon a_{1} \beta T^{\beta-1}+O(T^{\beta-2}).
\end{equation*}
\notag
$$
Рассмотрим остальные значения $\tau$. Замостим отрезок длины $\tau$ отрезками длины $\leqslant \min\{t(e),\, e \in E\}$, т.е.
$$
\begin{equation*}
\{l_i\}_{i=1}^{k}, \qquad \sum_{i=1}^{k}l_i=\tau, \quad l_i\leqslant \min\{t(e),\, e \in E\}.
\end{equation*}
\notag
$$
Получаем
$$
\begin{equation*}
\begin{aligned} \, N_{\tau, e, r}(T) &=\sum_{i=1}^{k}\biggl(N_{l_i, e, r_i}(T)+O(1)\biggr) =\sum_{i=1}^{k}(l_i a_{1} \beta T^{\beta-1}+O(T^{\beta-2})) \\ &=\biggl(\sum_{i=1}^{k}l_i\biggr) a_{1} \beta T^{\beta-1}+O(T^{\beta-2}) =\tau a_{1} \beta T^{\beta-1}+O(T^{\beta-2}). \end{aligned}
\end{equation*}
\notag
$$
3) Поскольку $N(T)$ – количество точек на графе в момент времени $T$, это количество можно получить как сумму количеств точек на каждом ребре в момент времени $T$. Имеем Из только что полученного утверждения вытекает утверждение о асимптотически равномерном распределении движущихся точек. Следствие 1 (о равномерности распределения). Пусть нам известно, что число возможных движущихся точек, вошедших в первую вершину к моменту времени $T$, можно представить в виде Тогда доля числа движущихся точек на произвольном отрезке длины $\tau$ будет асимптотически стремиться к доле отрезка в суммарной длине нашего метрического графа, а именно, Доказательство. Воспользуемся пунктами 2) и 3) леммы 8. Имеем 3.2. Гамильтоновы графыТеперь вернемся к гамильтоновым графам, которые описаны в п. 1.1. Лемма 9. Если $c=(c_{1}, \dots, c_{k})$ – набор генерируемых циклов, а граф гамильтонов, то $\{t(c_{1}), \dots, t(c_{k})\}$ линейно независимы над $\mathbb{Q}$. Доказательство. Допустим противное: пусть существует такое $(\alpha_{1}, \dots, \alpha_{k}) \neq (0, \dots, 0)$, что $\sum_{i=1}^{k}\alpha_it(c_i)=0$. Можно считать, что $\alpha_i \in \mathbb{Z}$. Известно, что $c$ – подпоследовательность полного достижимого набора $d$ (набора длины $\beta$). Положим $\gamma=\max_{i=1}^{k}{|\alpha_i|+1}$, получаем Мы готовы сформулировать основной результат. Теорема 2 (об асимптотике числа конечных положений случайного блуждания на гамильтоновом орграфе). Пусть нам дан гамильтонов ориентированный граф. Тогда число возможных движущихся точек, вошедших в первую вершину к моменту времени $T$, можно представить в виде Доказательство. 1. По теореме 1 имеем 2. Применяем лемму 8 и получаем, что
$$
\begin{equation*}
\begin{aligned} \, N(T) &=\biggl(\sum_{e \in E}t(e)\biggr) a_{1} \beta T^{\beta-1}+O(T^{\beta-2}) \\ & =\biggl(\sum_{e \in E}t(e)\biggr) \biggl(\sum_{d \in D_{\beta}}\frac{1}{\beta! \prod_{i=1}^{\beta}t(d_i)}\biggr) \beta T^{\beta-1}+O(T^{\beta-2}) \\ &=\biggl(\sum_{d \in D_{\beta}}\frac{\sum_{e \in E}t(e)}{(\beta-1)!\prod_{i=1}^{\beta} t(d_i)}\biggr) \cdot T^{\beta-1}+O(T^{\beta-2}). \end{aligned}
\end{equation*}
\notag
$$
По лемме 7 можно понимать $D_{\beta}$ как множество всех генерируемых циклов длины $\beta$. 4. Обсуждение результатов4.1. Случай, когда существует ровно один полный достижимый наборВ общем случае в $D_{\beta}$ для гамильтонова графа может быть много наборов достижимых циклов. Давайте рассмотрим частный случай гамильтоновых графов, для которых есть ровно один полный достижимый набор. Рассмотрим ориентированный цикл. Разобьем все вершины на два множества. Первое множество будет содержать вершины, номера которых идут подряд, но не будет содержать стартовую вершину. Второе множество будет содержать все остальные вершины (стартовую вершину в частности). Все ребра, которые находятся вне ориентированного цикла могут идти лишь из второго множества вершин в первое. Имеем ровно один полный достижимый набор $d^{0}$, потому что в каждом простом цикле в графе не более одного внутреннего ребра. Итоговая формула выглядит так:
$$
\begin{equation*}
N(T)= \biggl(\frac{\sum_{e \in E}t(e)}{(\beta-1)!\prod_{i=1}^{\beta}t(d^{0}_i)}\biggr) \cdot T^{\beta-1}+O(T^{\beta-2}).
\end{equation*}
\notag
$$
4.2. Сравнение с ранее полученными результатамиТеперь рассмотрим класс ориентированных графов, для которых старший коэффициент асимптотики был получен ранее, и сравним результаты. Речь идет про однонаправленные шпернеровы графы, подробное описание которые приведено в [7]. Основным свойством таких графов было то, что для любой вершины у нас был определен однозначный путь в нее из стартовой вершины, а ребра, задающие циклы, вели только в стартовую вершину. По лемме 8 достаточно найти $N_{1}(T)$. Напомним, что для первого числа Бетти справедлива формула $\beta=|E|-|V|+1$. Получаем, что в графе всего $|E|-(|V|-1)=\beta$ “обратных” ребер в стартовую вершину. Любое время захода в стартовую вершину задается линейной комбинацией с неотрицательными коэффициентами $a_{1}, \dots, a_{\beta}$ простых циклов $c_{1}, \dots, c_{\beta}$, каждое из которых содержит обратное ребро. Заметим, что если $(a_{1}, \dots, a_{\beta}) \neq (b_{1}, \dots, b_{\beta})$, $a_i, b_i \in \mathbb{N} \cup \{0\}$ и $a \neq 0$ или $b \neq 0$, то
$$
\begin{equation*}
\sum_{i=1}^{\beta}a_it(c_i) \neq \sum_{i=1}^{\beta}b_it(c_i).
\end{equation*}
\notag
$$
Это верно, потому что в каждом цикле $c_i$ есть какое-то обратное ребро $e_i$, которого нет в других циклах $c_j$, $j \neq i$, и все ребра линейно независимы над $\mathbb{Q}$. Имеем
$$
\begin{equation*}
N_{1}(T)=\#\biggl\{ \sum_{i=1}^{\beta}n_ic_i \leqslant T,\, n_i \in \mathbb{N} \cup \{0\}\biggr\}=\frac{1}{\beta!\prod_{i=1}^{\beta}t(c_i)}T^{\beta} +b_{1}T^{\beta-1}+O(T^{\beta-2}),
\end{equation*}
\notag
$$
и первый коэффициент равен Из леммы 8 получаем
$$
\begin{equation*}
N(T)=\biggl(\sum_{e \in E}t(e)\biggr)a_{1}\beta T^{\beta-1}+O(T^{\beta-2}) =\frac{\sum_{e \in E}t(e)}{(\beta-1)!\prod_{i=1}^{\beta}t(c_i)}T^{\beta-1} +O(T^{\beta-2}).
\end{equation*}
\notag
$$
Полученная асимптотическая формула для $N(T)$ совпадает с той, что приведена в [7].
5. ЗаключениеМы нашли асимптотику для числа возможных конечных положений случайного блуждания $N(T)$ при $T \to+\infty$ для ориентированных гамильтоновых графов. Старший коэффициент вычисляется по формуле
$$
\begin{equation*}
\sum_{d \in D_{\beta}} \frac{\sum_{e \in E}t(e)}{(\beta-1)!\prod_{i=1}^{\beta}t(d_i)}
\end{equation*}
\notag
$$
и не зависит от выбора порядка на ребрах, т.е. $\sum_{d \in D_{\beta}}{1}/(\prod_{i=1}^{\beta}t(d_i))$ является инвариантом относительно смены порядка на ребрах для гамильтоновых графов. Понимание природы этого инварианта и изучение $N(T)$ для ориентированных сильно связных графов, которые не являются гамильтоновыми, могут быть целью для дальнейшего исследования. БлагодарностиД. В. Пятько выражает благодарность Д. Э. Волгину за предоставление вычислительных ресурсов для проведения компьютерных экспериментов (результаты которых согласуются с полученными теоретическими выкладками) и Д. А. Полякову за конструктивные обсуждения текста. В. Л. Чернышев благодарит А. А. Толченникова за полезные обсуждения. 
Цитирование в формате AMSBIB
\RBibitem{PyaChe23} |
|
||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|