On the number of attractors in finite dynamic systems of complete graphs orientations

Finite dynamic systems of complete graphs orientations are considered. The states of such a system (Г_Кп, a), n > 1, are all possible orientations of a given complete graph K_n, and evolutionary function a transforms a given state (tournament) ~G by reversing all arcs in ~G that enter into sinks, and there are no other differences between the given G and the next a( G) states. In this paper, the number of attractors in finite dynamic systems of complete graphs orientations is counted. Namely, in the considered system (Г_Кп, a), 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

Authors

References