Остовные леса и специальные числа
- Авторы: Деза Е.И.1
-
Учреждения:
- Московский педагогический государственный университет
- Выпуск: Том 221 (2023)
- Страницы: 51-62
- Раздел: Статьи
- URL: https://journal-vniispk.ru/2782-4438/article/view/271317
- DOI: https://doi.org/10.36535/0233-6723-2023-221-51-62
- ID: 271317
Цитировать
Полный текст
Аннотация
В статье рассмотрены вопросы перечисления некоторых графов специального вида. Получен ряд новых результатов о числе остовных лесов графов, играющих важную роль в теории информации. Рассмотрены свойства остовных сходящихся лесов ориентированных графов, участвующих в построении квазиметрики среднего времени первого прохода — обобщенной метрической структуры, тесно связанной с эргодическими однородными цепями Маркова. Изучены характеристики остовных корневых лесов и остовных сходящихся лесов неориентированных и ориентированных графов, необходимых для построения матрицы относительной лесной доступности — одной из мер близости вершин графовых структур. Рассуждения проведены на основе нескольких простейших графовых моделей, в том числе на базе простого пути, простого цикла, графа-гусеницы и их ориентированных аналогов.
Об авторах
Елена Ивановна Деза
Московский педагогический государственный университет
Автор, ответственный за переписку.
Email: elena.deza@gmail.com
Россия, Москва
Список литературы
- Воробьев Н. Н. Числа Фибоначчи. — М.: Наука, 1978.
- Деза Е. И., Мханна Б. О специальных свойствах некоторых квазиметрик// Чебышев. сб. — 2020. —21, №1. — С. 145–164.
- Деза Е. И., Мханна Б. Вопросы перечисления остовных лесов некоторых графов// Чебышев. сб. —2021. — 22, №3. — С. 77–99.
- Chebotarev P. A graph theoretic interpretation of the mean first passage times/ arXiv: math/0701359 [math.PR].
- Chebotarev P. Spanning forest and the Golden ratio// Discr. Appl. Math. — 2008. — 156. — P. 813–821.
- Chebotarev P., Agaev R. Forest matrices around the Laplacian matrix// Lin. Alg. Appl. — 2002. — 356.— P. 253–274.
- Chebotarev P., Deza E. Hitting time quasi-metric and its forest representation// Optim. Lett. — 2020. — 14.— P. 291–307.
- Chebotarev P. Yu., Shamis E. V. On proximity measures for graph vertices// Automat. Remote Control.— 1998. — 59. — P. 1443–1459.
- Deza M., Deza E., Vidali J. Cones of weighted and partial metrics// Proc. Int. Conf. on Algebra, 2010. —Hackensack, New Jersey: World Scientific, 2012. — P. 177–197.
- Kirkland S. J., Neumann M. Group Inverses of M-Matrices and Their Applications. — CRC Press, 2012.
- Leighton T., Rivest R. L. The Markov chain tree theorem. Computer Science Technical Report MIT/LCS/TM-249. — Cambridge, Massachusetts: Laboratory of Computer Science, MIT, 1983.
- Meyer C. D., Jr. The role of the group generalized inverse in the theory of finite Markov chains// SIAM Rev. — 1975. — 17. — P. 443–464.
Дополнительные файлы
