Graph models occupy an important place in tasks related to information protection and information security, including in the construction of models and methods for managing the continuous operation and recovery of systems, and countering denial of service. We consider a finite dynamical system (Γkn, α), n ⩾ 1, the states of which are all possible orientations of the complete graph Kn, and the evolution function is specified as follows: the dynamic image of the digraph is a digraph obtained from the original one by reorienting all the arcs included in the sinks; there are no other differences between the original digraph and its image. Formulas are obtained for calculating the number of cyclic (belonging to attractors) states of the system; states that are not cyclical; attractors of the system, including various types. The corresponding tables are given for n from 1 to 20 inclusive.
Download file
Counter downloads: 70
- Title Number of attractors and cyclic states in finite dynamic systems of complete graphs orientations
- Headline Number of attractors and cyclic states in finite dynamic systems of complete graphs orientations
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 63
- Date:
- DOI 10.17223/20710410/63/5
Keywords
attractor, complete graph, cybersecurity, cyclic state, evolutionary function, fault-tolerance, finite dynamic system, graphAuthors
References
Григорчук Р. И., Некрашевич В. В., Суща,некий В. И. Автоматы, динамические системы и группы // Труды МИАН. 2000. Т. 231. С. 134-214.
Barbosa V. С. An Atlas of Edge-Reversal Dynamics. London: Chapman&Hall/CRC, 2001. 372 p.
Салий В. H. Об одном классе конечных динамических систем // Вестник Томского госуниверситета. Приложение. 2005. N814. С. 23-26.
Osipenko G. Dynamical Systems, Graphs, and Algorithms. Berlin; Heidelberg: Springer Verlag, 2007. 300 p.
Щербина О. А. Методологические аспекты динамического программирования // Динамические системы. 2007. Вып.22. С. 21-36.
Zavlanos М. М. and Pappas G. J. A dynamical systems approach to weighted graph matching // Automatica. 2008. V.44. No'll. P.2817-2824.
Macauley M. and Mortveit H. S. Cycle equivalence of graph dynamical systems // Nonlinearity. 2009. V.22. No. 2. P.421-436.
Kuhlman C. J., Kumar V. S. A., Marathe M. V., et al. A general-purpose graph dynamical system modeling framework // Proc. 2011 Winter Simulation Conf. Phoenix, USA, 2011. P.296-308.
Ara Р. and Exel R. Dynamical systems associated to separated graphs, graph algebras, and paradoxical decompositions // Adv. Math. 2014. V. 252. P.748-804.
Abdelhamid S. H. E., Kuhlman C. J., Marathe M. V., et al. GDSCalc: a web-based application for evaluating discrete graph dynamical systems // PLoS ONE. 2015. No. 10 (8). 24p. https: //journals.plos.org/plosone/article?id=10.1371/journal.pone.0133660.
Aledo J. A., Martinez S., and Valverde J. C. Graph dynamical systems with general Boolean states // Appl. Math. & Inform. Sci. 2015. V.9. No. 4. P.1803-1808.
Кадыров А. А., Кадыров А. А. Концептуальные основы общей теории дискретных динамических, релейных и логико-динамических систем на базе физической декомпозиции и графовых моделей // Вестник Волгогр. гос. ун-та. Сер. 10. Иннов. деят. 2015. №2(17). С.80-89.
Волгина М. А. Формализация информационных потоков графовых моделей динамических систем // Альманах современной науки и образования. 2015. №3(93). С. 23-26.
Aledo J. A., Diaz L. G., Martinez S., and Valverde J. C. Coexistence of periods in parallel and sequential boolean graph dynamical systems over directed graphs // Math. 2020. No. 8 (10). P. 1812-1825.
Gadouleau M. On the influence of the interaction graph on a finite dynamical system // Natural Computing. 2020. No. 19. P. 15-28.
Жаркова А. В. О количестве циклических состояний в конечных динамических системах ориентаций полных графов // Компьютерные науки и информационные технологии: Материалы Междунар. науч. конф. Саратов, 2018. С. 149-151.
Жаркова А. В. О количестве аттракторов в конечных динамических системах ориентаций полных графов j j Прикладная дискретная математика. Приложение. 2018. №11. С. 106-109.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, Физматлит, 1997. 368 с.
Власова А. В. Аттракторы в динамических системах двоичных векторов. Деи. в ВИНИТИ 23.06.2010. №392-В2010. 19 с.
Жаркова А. В. Аттракторы и циклические состояния в конечных динамических системах ориентаций полных графов // Прикладная дискретная математика. 2023. №59. С. 80-87.
Number of attractors and cyclic states in finite dynamic systems of complete graphs orientations | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 63. DOI: 10.17223/20710410/63/5
Download full-text version
Counter downloads: 101