Эффективный алгоритм поиска финальных вершин на обобщенном функциональном графе

О. В. Зубков

Иркутский государственный университет

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

Ключевые слова: дискретная динамическая система, функциональный граф, сложность алгоритма

УДК: 519.17

MSC: 68W40

DOI: 10.36535/2782-4438-2025-238-59-68

 Англоязычная версия: Journal of Mathematical Sciences (New York), 2025, 291:3, 391–399