2–3 пути на графе-решетке. Случайные блуждания

В работе рассмотрен граф-решетка с 2–3 ограничениями на достижимость. Он имеет вершины в точках плоскости с неотрицательными целочисленными координатами. Из каждой вершины выходит две дуги: горизонтальная – в ближайшую правую вершину и вертикальная – в ближайшую верхнюю вершину. Допустимыми путями в случае 2–3 достижимости являются пути, удовлетворяющие дополнительному условию делимости на 2 количества дуг в максимальных по вложению отрезках путей, состоящих только из горизонтальных дуг и делимости на 3 количеств дуг в максимальных по вложению отрезках путей, состоящих только из вертикальных дуг. Это ограничение не распространяется на заключительные отрезки путей. Получена формула для количества 2–3 путей, ведущих из вершины в вершину. Рассмотрен процесс случайного блуждания по 2–3 путям на графе-решетке. Показано, что он локально сводим к Марковскому процессу на подграфах, определяемых типом начальной вершины. Получены формулы для нахождения вероятностей перехода из вершины в вершину по 2–3 путям.
Библиография: 22 названия.