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

В статье рассмотрены вопросы перечисления остовных дереьвев некоторых графов специального вида. Именно, доказан ряд новых результатов о числе остовных деревьев графов, играющих важную роль в прикладных задачах теории информации. Во-первых, рассмотрены свойства остовных сходящихся деревьев ориентированных графов, участвующих в построении  квазиметрики среднего времени первого прохода -- обобщенной метрической структуры,   тесно связанной с эргодическими однородными цепями Маркова. Во-вторых, изучены характеристики остовных корневых деревьев и остовных сходящихся дереьвев неориентированных и ориентированных графов, необходимых для построения матрицы относительной лесной доступности -- одной из мер близости вершин графовых структур, играющей важную роль при  решении прикладных задач.  Рассуждения проведены   на базе графов-гусениц и их ориентированных аналогов. Аналогичные результаты для простого пути и простого цикла (как в ориентированном, так и в неориентированном случаях) были получены ранее.

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

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

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

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

В пятом разделе представлены  примеры матрицы относительной лесной доступности.

В шестом разделе  (заключении) приведены основные выводы работы, намечены результаты дальнейших исследований.

1. Воробьев Н.Н. Числа Фибоначчи. - М.: Наука, 1978.

2. Деза М.М., Деза Е.И., Дютур Сикирич М. Полиэдральные конструкции, связанные с

3. квази-метриками // Чебышевский сборник. 2015. Том 16, выпуск 2. С. 79 – 92.

4. Деза Е.И., Мханна Б. О специальных свойствах некоторых квазиметрик // Чебышевский

5. сборник. 2020. Том 21, выпуск 1. С. 145 – 164.

6. Деза Е.И., Мханна Б. Квазиметрики на графах // Чебышевский сборник. 2021. Том 22,

7. выпуск 2 (78). С. 48 – 75.

8. Деза Е.И., Мханна Б. Вопросы перечисления остовных лесов некоторых графов // Чебышевский сборник. 2021. Том 22, выпуск 3 (79). С. 77 – 99.

9. Потапов В.Н. Теория информации. Кодирование дискретных вероятностных источников.

10. - Новосибирск: НГУ, 1999.

11. Харари Ф. Теория графов. - М.: УРСС, 2003.

12. Chebotarev P. Spanning forest and the Golden ratio // Discrete Applied Mathematics. 2008.

13. Vol. 156. P. 813 – 821.

14. Chebotarev P. Studying new classes of graph metrics / in F. Nielsen and F. Barbaresco, editors,

15. Proceedings of the SEE Conference ”Geometric Science of Information“ (GSI-2013) // Lecture

16. Notes in Computer Science. 2013. LNCS 8085. P. 207–214.

17. Chebotarev P., Agaev R. Forest matrices around the Laplacian matrix // Linear Algebra and

18. its Applications. 2002. Vol. 356. P. 253–274.

19. Chebotarev P., Deza E. Hitting time quasi-metric and its forest representation // Optimization

20. Letters. 2020.Vol. 14. P. 291–307. https://doi.org/10.1007/s11590-018-1314-2

21. Chebotarev P.Y., Shamis E.V. On proximity measures for graph vertices // Automation and

22. Remote Control. 1998. Vol. 59. P. 1443—1459.

23. Deza E., Deza M., Dutour Sikiri´c Generalizations of Finite Metrics and Cuts. - World Scientific,

24.

25. Deza M., Deza E. Cones of partial metrics // Contributions to Discrete Mathematics. 2011.

26. Vol. 6. P. 26–47.

27. Deza M. M., Deza E. Encyclopedia of Distances. - Springer: Berlin-Heidelberg, 2016.

28. Deza M., Deza E., Vidali J. Cones of weighted and partial metrics / in Proceedings of the

29. Internat. Conference on Algebra 2010 // Advances in Algebraic Structures. 2012. P. 177–197.

30. Kirkland S.J., Neumann M. Group inverses of M-matrices and their applications. - CRC Press,

31.

32. Leighton T., Rivest R.L. The Markov chain tree theorem // Computer Science Technical Report

33. MIT/LCS/TM-249, Laboratory of Computer Science, MIT, Cambridge, Mass. 1983.

34. Meyer Jr., C. D. The role of the group generalized inverse in the theory of finite Markov chains

35. // SIAM Review. 1975. Vol. 17. P. 443–464.