Остовные леса и специальные числа

Обложка

Цитировать

Полный текст

Аннотация

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

Об авторах

Елена Ивановна Деза

Московский педагогический государственный университет

Автор, ответственный за переписку.
Email: elena.deza@gmail.com
Россия, Москва

Список литературы

  1. Воробьев Н. Н. Числа Фибоначчи. — М.: Наука, 1978.
  2. Деза Е. И., Мханна Б. О специальных свойствах некоторых квазиметрик// Чебышев. сб. — 2020. —21, №1. — С. 145–164.
  3. Деза Е. И., Мханна Б. Вопросы перечисления остовных лесов некоторых графов// Чебышев. сб. —2021. — 22, №3. — С. 77–99.
  4. Chebotarev P. A graph theoretic interpretation of the mean first passage times/ arXiv: math/0701359 [math.PR].
  5. Chebotarev P. Spanning forest and the Golden ratio// Discr. Appl. Math. — 2008. — 156. — P. 813–821.
  6. Chebotarev P., Agaev R. Forest matrices around the Laplacian matrix// Lin. Alg. Appl. — 2002. — 356.— P. 253–274.
  7. Chebotarev P., Deza E. Hitting time quasi-metric and its forest representation// Optim. Lett. — 2020. — 14.— P. 291–307.
  8. Chebotarev P. Yu., Shamis E. V. On proximity measures for graph vertices// Automat. Remote Control.— 1998. — 59. — P. 1443–1459.
  9. 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.
  10. Kirkland S. J., Neumann M. Group Inverses of M-Matrices and Their Applications. — CRC Press, 2012.
  11. 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.
  12. 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.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Деза Е.И., 2023

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».