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

В статье рассмотрены вопросы перечисления некоторых графов специального вида.
Именно, доказан ряд новых результатов о числе остовных деревьев и остовных лесов графов, играющих важную роль в прикладных задачах теории информации. Во-первых, рассмотрены свойства остовных сходящихся лесов ориентированных графов, участвующих в построении квазиметрики среднего времени первого прохода – обобщенной метрической структуры, тесно связанной с эргодическими однородными цепями Маркова. Во-вторых,
изучены характеристики остовных корневых лесов и остовных сходящихся лесов неориентированных и ориентированных графов, необходимых для построения матрицы относительной лесной доступности – одной из мер близости вершин графовых структур, играющей важную роль при решении прикладных задач. Рассуждения проведены на основе нескольких простейших графовых моделей, в том числе на базе простого цикла, простого пути и их ориентированных аналогов.
В первом разделе (введении) представлена история вопроса, дан обзор основных идей и результатов работы. Рассмотрена роль графовых моделей в представлении и исследовании эргодических однородных цепей Маркова – последовательностей случайных событий с конечным или счетным числом исходов, характеризующихся тем, что распределение вероятностей параметров процесса в следующий момент времени зависит только от параметров
процесса в предыдущий момент. Марковская цепь может быть изображена в виде ориентированного взвешенного графа переходов, вершины которого соответствуют состояниям цепи, а дуги – переходам между ними. С другой стороны, любой связный граф (ориентированный граф) может служить базой для построения модели простейшей цепи Маркова: если вершина 𝑖 имеет степень (полустепень исхода) 𝑘, то все выходящие из нее ребра превращаются в дуги с весами 1/𝑘 . Дано определение и раскрыта роль матрицы относительной лесной доступности неориентированных и ориентированных графов для решения
прикладных задач теории информации.
Во втором разделе собраны базовые определения теории графов, необходимые для формулировки и доказательства основных результатов работы. Дано определение графа и
ориентированного графа, остовного подграфа, остовного корневого леса (для неориентированных графов) и остовного сходящегося леса (для ориентированных графов). Приведены
примеры.
В третьем разделе дано определение чисел Фибоначчи, сформулирован и доказан ряд свойств чисел Фибоначчи, необходимых для получения основных результатов статьи в
случае неориентированных пути и цикла.
В четвертом разделе доказаны две теоремы о перечислении графов, связанных с построением матрицы среднего времени первого прохода для однородной эргодической цепи Маркова. Именно, найдено количество остовных сходящихся деревьев для ориентированного пути и цикла и остовных корневых деревьев для неориентированного пути и цикла;
произведен подсчет остовных лесов, состоящих из двух деревьев, для тех же графовых структур. Результаты, связанные с ориентированным случаем, сформулированы в терминах величин 2/𝑘, 𝑘 ≥ 0; результаты для неориентированного случая сформулированы в
терминах чисел Фибоначчи 𝑢𝑘, 𝑘 ≥ 1. Доказательства проведены на базе элементарных методов перечислительной комбинаторики.
В пятом разделе представлены результаты, связанные с перечислением остовных лесов, необходимых для построения матрицы относительной лесной доступности неориентированного пути и цикла и их ориентированных аналогов. Найдено общее количество остовных сходящихся лесов для ориентированного пути и цикла и остовных корневых лесов для неориентированного пути и цикла; произведен подсчет остовных сходящихся лесов, в которых вершина 𝑖 принадлежит дереву, сходящемуся к 𝑗 в ориентированном пути и цикле, и остовных корневых лесов, в которых вершина 𝑖 принадлежит дереву с корнем 𝑗 в неориентированном пути и цикле. Как и ранее, результаты, связанные с ориентированным случаем, сформулированы в терминах величин 2𝑘, 𝑘 ≥ 0; результаты для неориентированного случая сформулированы в терминах чисел Фибоначчи 𝑢𝑘, 𝑘 ≥ 1.
В шестом разделе (заключении) приведены основные выводы работы, намечены результаты дальнейших исследований.

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

2. Деза М.М., Деза Е.И., Дютур Сикирич М. Полиэдральные конструкции, связанные с квази-метриками // Чебышевский сборник. 2015. Том 16, выпуск 2. С. 79 – 92.

3. Деза Е.И., Мханна Б. О специальных свойствах некоторых квазиметрик // Чебышевский сборник. 2020. Том 21, выпуск 1. С. 145 – 164.

4. Потапов В.Н. Теория информации. Кодирование дискретных вероятностных источников.- Новосибирск: НГУ, 1999.

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

6. Chebotarev P. A graph theoretic interpretation of the mean first passage times //arXivpreprintarXiv:math.PR/0701359. 2007.

7. Chebotarev P. Spanning forest and the Golden ratio // Discrete Applied Mathematics. 2008.Vol. 156. P. 813 – 821.

8. Chebotarev P. Studying new classes of graph metrics / in F. Nielsen and F. Barbaresco, editors, Proceedings of the SEE Conference ”Geometric Science of Information“ (GSI-2013) // Lecture Notes in Computer Science. 2013. LNCS 8085. P. 207–214.

9. Chebotarev P., Agaev R. Forest matrices around the Laplacian matrix // Linear Algebra and its Applications. 2002. Vol. 356. P. 253–274.

10. Chebotarev P., Deza E. Hitting time quasi-metric and its forest representation // Optimization Letters. 2020.Vol. 14. P. 291–307. https://doi.org/10.1007/s11590-018-1314-2

11. Chebotarev P.Y., Shamis E.V. On proximity measures for graph vertices // Automation and Remote Control. 1998. Vol. 59. P. 1443—1459.

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

13. Deza M., Deza E. Cones of partial metrics // Contributions to Discrete Mathematics. 2011.Vol. 6. P. 26–47.

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

15. Deza M., Deza E., Vidali J. Cones of weighted and partial metrics / in Proceedings of the Internat. Conference on Algebra 2010 // Advances in Algebraic Structures. 2012. P. 177–197.

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

17. Leighton T., Rivest R.L. The Markov chain tree theorem // Computer Science Technical Report MIT/LCS/TM-249, Laboratory of Computer Science, MIT, Cambridge, Mass. 1983.

18. Meyer Jr., C. D. The role of the group generalized inverse in the theory of finite Markov chains // SIAM Review. 1975. Vol. 17. P. 443–464.

19. Wilson W. On quasi-metric spaces // American Journal of Mathematics. 1931. Vol. 53. P. 675–684.