Number of attractors and cyclic states in finite dynamic systems of complete graphs orientations

A. V. Zharkova

Prikladnaâ diskretnaâ matematika, no. 1 (2024), pp. 91-101

Résumé

Graph models occupy an important place in information security tasks, including the construction of models and methods for managing the continuous operation of systems and system recovery, countering denials of service. Finite dynamic systems of complete graphs orientations are considered. States of a dynamic system $(\Gamma_{K_n},\alpha)$, $n \geq 1$, are all possible orientations of the complete graph ${K_n}$, and evolutionary function transforms the graph orientation by reversing all the arcs that enter into sinks, and there are no other differences between the given and the next digraphs. Formulas are obtained for counting the number of cyclic (belonging to attractors) system states and the number of states that are not cyclic (not belonging to attractors), namely, the number of states belonging to attractors is $1$, if $n=1$; $2^{{(n-1)(n-2)}/{2}}(2^{n-1}-n)+n!$, if $n>1$, the number of states not belonging to attractors is $0$, if $n=1$; $n \cdot 2^{{(n-1)(n-2)}/{ 2}} - n!$, if $n>1$. Formulas are obtained for counting the number of attractors of the system, including various types, namely, the number of attractors of length $1$ is $1$, if $n=1$; $2^{{(n-1)(n-2)}/{2}}(2^{ n-1}-n)$, if $n>1$, the number of attractors of length $n$ is $(n-1)!$, the number of attractors (basins) is $1$, if $n=1$; $2^{{(n-1)(n-2)}/{2 }}(2^{n-1}-n)+(n-1)!$, if $n>1$. The corresponding tables are given for $n=1,\ldots,20$.

Détail

Keywords: attractor, complete graph, cybersecurity, cyclic state, evolutionary function, fault-tolerance, finite dynamic system, graph.