An efficient algorithm for finding final vertices in a generalized functional graph
- Authors: Zubkov O.V.1
-
Affiliations:
- Irkutsk State University
- Issue: Vol 238 (2025)
- Pages: 59-68
- Section: Articles
- URL: https://ogarev-online.ru/2782-4438/article/view/312514
- DOI: https://doi.org/10.36535/2782-4438-2025-238-59-68
- ID: 312514
Cite item
Full Text
Abstract
In the paper, 2-outgoing graphs are introduced into consideration, generalizing functional graphs and modeling discrete dynamic systems of a special type. The vertices and arcs of a 2-outgoing graph are classified, paths on these graphs are defined, and some properties of these paths are proved. As a result, an efficient algorithm is constructed that, with linear complexity, constructs final vertices for paths starting at each of the vertices of a 2-outgoing graph, and its correctness is proven.
About the authors
Oleg Vladimirovich Zubkov
Irkutsk State UniversityCandidate of physico-mathematical sciences, Associate professor
References
- Быков И. 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
Supplementary files
