On number of inaccessible states in finite dynamic systems of complete graphs orientations

Finite dynamic systems of complete graphs orientations are considered. The states of such a system (r_Kn, a), n > 1, are all possible orientations of a given complete graph , 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, formulas for calculating the number of inaccessible and the number of accessible states in finite dynamic systems of complete graphs orientations are given. Namely, in the considered system (r_Kn, a), n > 1, the state G £ r_Kn is inaccessible if and only if in this digraph G there is no source and there is a sink. In the finite dynamic system (r_Kn, a), n > 1, the number of inaccessible states is n(2^{(ra-1)(ra-2)/2} - (n - 1)2^{(n-2)(ra-3)/2}) and the number of accessible states is 2^n(n-1)/2 - Ц2^{(га-1)(га-2)/2} - (n - 1)2^(n-2)(^n-3)^/2). The corresponding table is given for the finite dynamic systems of complete graphs orientations with the number of vertices from 2 to 10.

Keywords

Authors

References