Вопросы перечисления остовных лесов некоторых графов

В статье рассмотрены вопросы перечисления некоторых графов специального вида. Именно, доказан ряд новых результатов о числе остовных деревьев и остовных лесов графов, играющих важную роль в прикладных задачах теории информации. Во-первых, рассмотрены свойства остовных сходящихся лесов ориентированных графов, участвующих в построении квазиметрики среднего времени первого прохода – обобщенной метрической структуры, тесно связанной с эргодическими однородными цепями Маркова. Во-вторых, изучены характеристики остовных корневых лесов и остовных сходящихся лесов неориентированных и ориентированных графов, необходимых для построения матрицы относительной лесной доступности – одной из мер близости вершин графовых структур, играющей важную роль при решении прикладных задач. Рассуждения проведены на основе нескольких простейших графовых моделей, в том числе на базе простого цикла, простого пути и их ориентированных аналогов.
В первом разделе (введении) представлена история вопроса, дан обзор основных идей и результатов работы. Рассмотрена роль графовых моделей в представлении и исследовании эргодических однородных цепей Маркова – последовательностей случайных событий с конечным или счетным числом исходов, характеризующихся тем, что распределение вероятностей параметров процесса в следующий момент времени зависит только от параметров процесса в предыдущий момент. Марковская цепь может быть изображена в виде ориентированного взвешенного графа переходов, вершины которого соответствуют состояниям цепи, а дуги – переходам между ними. С другой стороны, любой связный граф (ориентированный граф) может служить базой для построения модели простейшей цепи Маркова: если вершина $i$ имеет степень (полустепень исхода) $k$, то все выходящие из нее ребра превращаются в дуги с весами $\frac{1}{k}$. Дано определение и раскрыта роль матрицы относительной лесной доступности неориентированных и ориентированных графов для решения прикладных задач теории информации.
Во втором разделе собраны базовые определения теории графов, необходимые для формулировки и доказательства основных результатов работы. Дано определение графа и ориентированного графа, остовного подграфа, остовного корневого леса (для неориентированных графов) и остовного сходящегося леса (для ориентированных графов). Приведены примеры.
В третьем разделе дано определение чисел Фибоначчи, сформулирован и доказан ряд свойств чисел Фибоначчи, необходимых для получения основных результатов статьи в случае неориентированных пути и цикла.
В четвертом разделе доказаны две теоремы о перечислении графов, связанных с построением матрицы среднего времени первого прохода для однородной эргодической цепи Маркова. Именно, найдено количество остовных сходящихся деревьев для ориентированного пути и цикла и остовных корневых деревьев для неориентированного пути и цикла; произведен подсчет остовных лесов, состоящих из двух деревьев, для тех же графовых структур. Результаты, связанные с ориентированным случем, сформулированы в терминах величин $2^k$, $k\geq 0$; результаты для неориентированного случая сформулированы в терминах чисел Фибоначчи $u_k$, $k\geq 1$. Доказательства проведены на базе элементарных методов перечислительной комбинаторики.
В пятом разделе представлены результаты, связанные с перечислением остовных лесов, необходимых для построения матрицы относительной лесной доступности неориентированного пути и цикла и их ориентированных аналогов. Найдено общее количество остовных сходящихся лесов для ориентированного пути и цикла и остовных корневых лесов для неориентированного пути и цикла; произведен подсчет остовных сходящихся лесов, в которых вершина $i$ принадлежит дереву, сходящемуся к $j$ в ориентированном пути и цикле, и остовных корневых лесов, в которых вершина $i$ принадлежит дереву с корнем $j$ в неориентированном пути и цикле. Как и ранее, результаты, связанные с ориентированным случаем, сформулированы в терминах величин $2^k$, $k\geq 0$; результаты для неориентированного случая сформулированы в терминах чисел Фибоначчи $u_k$, $k\geq 1$.
В шестом разделе (заключении) приведены основные выводы работы, намечены результаты дальнейших исследований.