К вопросу о перечислении некоторых классов ориентированных и неориентированных деревьев и лесов

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