Эффективный алгоритм поиска финальных вершин на обобщенном функциональном графе
- Авторы: Зубков О.В.1
-
Учреждения:
- Иркутский государственный университет
- Выпуск: Том 238 (2025)
- Страницы: 59-68
- Раздел: Статьи
- URL: https://journal-vniispk.ru/2782-4438/article/view/312514
- DOI: https://doi.org/10.36535/2782-4438-2025-238-59-68
- ID: 312514
Цитировать
Полный текст
Аннотация
В работе введены в рассмотрение 2-исходящие графы, обобщающие функциональные графы и моделирующие дискретные динамические системы специального вида. Классифицированы вершины и дуги 2-исходящего графа, определены пути на этих графах и доказаны некоторые свойства этих путей. В итоге построен эффективный алгоритм, который с линейной сложностью строит финальные вершины для путей, начинающихся в каждой из вершин 2-исходящего графа и доказана его корректность.
Ключевые слова
Об авторах
Олег Владимирович Зубков
Иркутский государственный университеткандидат физико-математических наук, доцент
Список литературы
- Быков И. C., “Функционирование дискретной динамической системы циркулянтного типа с пороговыми функциями в вершинах”, Прикл. дискр. мат., 26:4 (2014), 84–95
- Евдокимов А. А., Пережогин А. Л., “Дискретные динамические системы циркулянтного типа с линейными функциями в вершинах сети”, Дискр. анал. исслед. опер., 18:3 (2011), 39–48
- Парфиненко А. C., Пережогин А. Л., “Функциональный граф линейной дискретной динамической системы с двумя доминирующими вершинами”, Дискр. анал. исслед. опер., 25:4 (2018), 81–96
- Harary F., “The number of functional digraphs”, Math. Ann., 139 (1959), 203–210
Дополнительные файлы
