|
This article is cited in 2 scientific papers (total in 2 papers)
Applied Theory of Coding, Automata and Graphs
On the number of attractors in finite dynamic systems of complete graphs orientations
A. V. Zharkova Saratov State University, Saratov
Abstract:
Finite dynamic systems of complete graphs orientations are considered. The states of such a system $(\Gamma_{K_n},\alpha)$, $n>1$, are all possible orientations of a given complete graph $K_n$, and evolutionary function $\alpha$ transforms a given state (tournament) $\vec G$ by reversing all arcs in $\vec G$ that enter into sinks, and there are no other differences between the given $\vec G$ and the next $\alpha(\vec G)$ states. In this paper, the number of attractors in finite dynamic systems of complete graphs orientations is counted. Namely, in the considered system $(\Gamma_{K_n},\alpha)$, $n>1$, the total number of attractors (basins) is $2^{(n-1)(n-2)/2}(2^{n-1}-n)+(n-1)!$, wherein the number of attractors of length $1$ is $2^{(n-1)(n-2)/2}(2^{n-1}-n)$ and of length $n$ is $(n-1)!$. The corresponding tables are given for the finite dynamic systems of orientations of complete graphs with the number of vertices from two to ten inclusive.
Keywords:
attractor, complete graph, evolutionary function, finite dynamic system, graph, graph orientation, tournament.
Citation:
A. V. Zharkova, “On the number of attractors in finite dynamic systems of complete graphs orientations”, Prikl. Diskr. Mat. Suppl., 2018, no. 11, 106–109
Linking options:
https://www.mathnet.ru/eng/pdma415 https://www.mathnet.ru/eng/pdma/y2018/i11/p106
|
|