On indices of states 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 algorithm for calculating indices of states in finite dynamic systems of complete graphs orientations is proposed. Namely, in the considered system (Г_Кп, a), n > 1, the index of the state G G Г_Кп is 0 if and only if it hasn't a sink or its indegrees vector (d^-(v₁), d^-(v₂),... ,d^-(v_n)) is a permutation of numbers {0,1,... ,n - 1}. If these conditions for this state G are not met, then its index is f, where f is the power of the largest set of the form {n - 1, n - 2,..., n - f} С {d^-(v₁ ),d^-(v₂),... ,d^-(v_n)}. The maximal index of the states in the system is found: it is equal to 0 for n = 2 and n - 3 for n > 2. The corresponding table is given for the finite dynamic systems of orientations of complete graphs with the number of vertices from 2 to 7.

Keywords

Authors

References